CS102: PROGRAMMING AND DATA STRUCTURE
LECTURE 23: ABSTRACT DATA TYPE
DR. ARIJIT ROY
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
INDIAN INSTITUTE OF TECHNOLOGY PATNA
Slide Courtesy : Prof. Indranil Sengupta and Dr. Palash Dey, IIT Kharagpur 1
DEFINITION
➢ An abstract data type (ADT) is a specification of a set of data and the set of operations
that can be performed on the data.
➢ Such data type is abstract in the sense that it is independent of various concrete
implementations.
➢ Some examples follow.
EXAMPLE 1: COMPLEX NUMBERS
struct cplx {
float re; Structure
float im; definition
}
typedef struct cplx complex;
complex add (complex a, complex b);
complex sub (complex a, complex b); Function
complex mul (complex a, complex b); prototypes
complex div (complex a, complex b);
complex read();
void print (complex a);
add
sub
mul COMPLEX
NUMBER
div
read
print
EXAMPLE 2 : SET MANIPULATION
struct node {
int element; Structure
struct node *next; definition
}
typedef struct node set;
set union (set a, set b);
set intersect (set a, set b);
Function
set minus (set a, set b);
prototypes
void insert (set a, int x);
void delete (set a, int x);
int size (set a);
UNION
intersect
minus
Set
insert
delete
size
EXAMPLE 3 :: LAST-IN-FIRST-OUT STACK
Assume:: stack contains integer elements
void push (stack s, int element);
/* Insert an element in the stack */
int pop (stack s);
/* Remove and return the top element */
void create (stack s);
/* Create a new stack */
int isempty (stack s);
/* Check if stack is empty */
int isfull (stack s);
/* Check if stack is full */
PUSH
pop
create
STACK
isempty
isfull
VISUALIZATION OF A STACK
In Out
C B A B C
CONTD.
• We shall later look into two different ways of implementing stack:
– Using arrays
– Using linked list
EXAMPLE 4: FIRST-IN-FIRST-OUT QUEUE
Assume:: queue contains integer elements
void enqueue (queue q, int element);
/* Insert an element in the queue */
int dequeue (queue q);
/* Remove an element from the queue */
queue *createq();
/* Create a new queue */
int isempty (queue q);
/* Check if queue is empty */
int size (queue q);
/* Return the no. of elements in queue */
ENQUEUE
dequeue
create
QUEUE
isempty
size
VISUALIZATION OF A QUEUE
Out
In
B A
C B A
STACK AND QUEUE IN MORE DETAILS
Ref: Western Michigan University
WHAT IS A STACK
➢ Stack of Books
STACKS
➢ What is a Stack?
➢ A stack is a data structure of ordered items such that items can be inserted and
removed only at one end.
➢ What can we do with a stack?
➢ push - place an item on the stack
➢ peek - Look at the item on top of the stack, but do not remove it
➢ pop - Look at the item on top of the stack and remove it
STACKS
➢ A stack is a LIFO (Last-In/First-Out) data structure
➢ A stack is sometimes also called a pushdown store.
➢ What are some applications of stacks?
➢ Program execution
➢ Infix to postfix conversion
➢ Evaluating postfix expressions
➢ Matching Parenthesis
STACKS
➢ Problem:
➢ What happens if we try to pop an item off the stack when the stack is empty?
➢ This is called a stack underflow.
➢ The pop method needs some way of telling us that this has happened.
USING A ISTACK
➢ A balance of braces.
➢ (()) balanced braces
➢ ()(()()))) not balanced braces
➢ How can you use Istack to check a brace is balanced or not?
IMPLEMENTING A STACK
➢ There are two ways we can implement a stack:
➢ Using an array
➢ Using a linked list
➢ Implementing a stack using an array is fairly easy.
➢ The bottom of the stack is at data[0]
➢ The top of the stack is at data[numItems-1]
➢ push onto the stack at data[numItems]
➢ pop off of the stack at data[numItems-1]
IMPLEMENTING A STACK
➢ Implementing a stack using a linked list isn’t that bad either…
➢ Store the items in the stack in a linked list
➢ The top of the stack is the head node, the bottom of the stack is the end of the list
➢ push by adding to the front of the list
➢ pop by removing from the front of the list
REVERSING A WORD
➢ We can use a stack to reverse the letters in a word.
➢ How?
➢ Read each letter in the word and push it onto the stack
➢ When you reach the end of the word, pop the letters off the stack and print them out
WHAT IS A QUEUE?
QUEUES
➢ What is a queue?
➢ A data structure of ordered items such that items can be inserted only at one end
and removed at the other end.
➢ Example
➢ A line at the supermarket
➢ What can we do with a queue?
➢ Enqueue - Add an item to the queue
➢ Dequeue - Remove an item from the queue
➢ These ops are also called insert and getFront in order to simplify things.
QUEUES
➢ What can we do with a queue?
➢ Enqueue - Add an item to the queue
➢ Dequeue - Remove an item from the queue
➢ These ops are also called insert and getFront in order to simplify things.
➢ A queue is called a FIFO (First in-First out) data structure.
➢ What are some applications of queues?
➢ Round-robin scheduling in processors
➢ Input/Output processing
➢ Queueing of packets for delivery in networks
IMPLEMENTING A QUEUE
➢ Just like a stack, we can implementing a queue in two ways:
➢ Using an array
➢ Using a linked list
➢ Using an array to implement a queue is significantly harder than using an array to
implement a stack. Why?
➢ Unlike a stack, where we add and remove at the same end, in a queue we add to
one end and remove from the other.
IMPLEMENTING A QUEUE
➢ There are two options for implementing a queue using an array:
➢ Option 1:
➢ Enqueue at data[0] and shift all of the rest of the items in the array down to make
room.
➢ Dequeue from data[numItems-1]
IMPLEMENTING A QUEUE
➢ Option 2
➢ Enqueue at data[rear+1]
➢ Dequeue at data[front]
➢ The rear variable always contains the index of the last item in the queue.
➢ The front variable always contains the index of the first item in the queue.
➢ When we reach the end of the array, wrap around to the front again.
IMPLEMENTING A QUEUE
➢ Implementing a queue using a linked list is still easy:
➢ Front of the queue is stored as the head node of the linked list, rear of the queue is
stored as the tail node.
➢ Enqueue by adding to the end of the list
➢ Dequeue by removing from the front of the list.
THANK YOU!
ATTENDANCE
30