Data Structures
Unit-3.1
Stacks
and
Queues
Stack and Queue
• In Array and List, Insertion and Deletion can be
done at any position – Beginning, End, Middle
• Need Data structures in which insertion and
deletion takes places only at ends.
• Stack and Queue fulfils this demand
Data Structures 2
Stack
• A stack is a linear data structure in which addition
or deletion takes place at the same end.
• This end is called top of the stack.
• Last In First Out (LIFO)
Data Structures 3
Stack ADT
• Data
Data/Information of element
Address of next node in the list
Data Structures 4
• Operations
Push(Element):
Add an element to the top
Pop():
Remove the element from the top
Peek()
See what is the element in the top
isEmpty()
Check if the stack is empty
Data Structures 5
• Stack Overflow
• If stack is full and there is no space available to
insert new data in stack, this situation is stack
overflow
• Stack Underflow
• If there is no element in the stack to delete, this
situation is called stack underflow
Data Structures 6
Implementation of Stack using Array
• MAXSTACK represents size of stack
• TOP represents location of top of the stack
• Size of stack is fixed.
• It can’t be modified dynamically.
Data Structures 7
struct stack
{
int A[size];
int top;
};
void init_stack(struct stack *);
void push(struct stack *, int item);
int pop(struct stack *);
Data Structures 8
void init_stack(struct stack *s)
{
s → top = -1;
}
Data Structures 9
void push(struct stack *s, int item)
{
if (s→top == size-1)
{
print(“Stack is Full”);
return;
}
s → top ++;
s → a[s → top] = item;
}
Data Structures 10
int pop(struct stack *s)
{
int data;
if (s→top == -1)
{
print(“Stack is Empty”);
return;
}
data= s → a[s → top];
s → top--;
return data;
}
Data Structures 11
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
i=pop(&s);
Data Structures 12
Implementation of Stack using Linked List
Data Structures 13
struct node
{
int data;
struct node *link;
};
void push(struct node**, int item);
int pop(struct node **);
void del_stack(struct node **);
Data Structures 14
void push(struct node **top, int item)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if (temp == NULL)
{
print(“Stack is Full”);
}
temp → data=item;
temp → link= *top;
*top=temp;
}
Data Structures 15
int pop(struct node **top)
{
struct node *temp;
int item;
if (*top== NULL)
{
print(“Stack is Empty”);
return;
}
temp=*top;
item= temp→ data;
*top=(*top) → link;
free(temp);
return item;
}
Data Structures 16
void del_stack(struct node **top)
{
struct node *temp;
if(*top==NULL)
return;
while(*top!=NULL)
{
temp=*top;
*top=(*top) → link;
free(temp);
}
}
Data Structures 17
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
i=pop(&s);
Data Structures 18
Stack - Applications
• String Reversal
1 Create an empty stack.
2One by one push all characters of string to stack.
3] One by one pop all characters from stack and put
them back to string.
Data Structures 19
• Parenthesis Checking
• The algorithm checks for balanced parenthesis.
1] When any open symbol i.e. ‘(‘, ‘{‘, ‘[‘ is
encountered, it will be pushed in the stack.
2] If any close symbol i.e. ‘)’, ‘}’, ‘]’ is encountered,
any of the three can happen
2 a] The TOS (Top Of Stack) is checked, if the
encountered close symbol matches with its open
symbol, then open symbol which is at TOS is popped
out.
Data Structures 20
• Parenthesis Checking
2 b] The TOS (Top Of Stack) is checked, if the
encountered close symbol does not match with its open
symbol, then “-1” is returned as there is no matching
symbol.
2 c] The TOS (Top Of Stack) is checked, if the stack is
empty, then “-1” is returned as there is no open symbol
in the stack.
Data Structures 21
• Syntax Parsing
• Many compilers use a stack for parsing the syntax
of expressions, program blocks etc. before
translating into low level code.
• Checking Palindromes
Data Structures 22
• Backtracking
• Backtracking is used in algorithms in which there
are steps along some path (state) from some starting
point to some goal.
• Find a path from one point in a graph (roadmap) to
another point.
• Play a game in which there are moves to be made
(chess).
Data Structures 23
• There are choices to be made among a number of
options.
• Weneed some way to remember these decision
points in case we want/need to come back and try
the alternative
• Stack can be used as part of the solution.
• Recursion is another, typically more favoured,
solution, which is actually implemented by a stack
Data Structures 24
• Expression Evaluation
• Polish Notations – The process of writing the
operators of an expression either before their
operands or after them is called the polish notation.
• Polish notation was introduced by Jan Lukasiewicz.
• The main property of Polish Notation is that, the
order in which operations are to be performed is
ascertained by the position of the operators and
operands in the expression.
Data Structures 25
• The complex arithmetic expressions can be
converted into polish strings using stacks.
• They can be executed in two operands and an
operator form.
• The notation refers to these complex arithmetic
expressions in three forms:
– Prefix Notation
– Postfix Notation
– Infix Notation
Data Structures 26
• Prefix Notation
• If the operator symbols are placed before its
operands, then the expression is in Prefix Notation
• Prefix Notation
• If the operator symbols are placed after its operands,
then the expression is in Postfix Notation
• Infix Notation
• If the operator symbols are placed between the
operands, then the expression is in Infix Notation
Data Structures 27
Data Structures 28
• Evaluation of Postfix Expression
Data Structures 29
• Evaluation of Prefix Expression
Data Structures 30
Data Structures 31
Data Structures 32
Data Structures 33
Data Structures 34
Data Structures
Unit-2
Queues
Queue
• Queue is a linear list of elements in which deletion
of an element can take place only at one end, called
the front.
• And insertion can take place only at the other end,
called the rear.
• First element in the queue is the first one to be
removed.
• FIFO lists
Data Structures 36
• Example
• People waiting in queue to purchase ticket
• Print Queue
• Processes waiting to get CPU
Data Structures 37
Queue ADT
• Data
Data/Information of element
Address of next node in the list
Data Structures 38
• Operations
EnQueue(Element):
Add an element at the end of queue
DeQueue():
Remove the first element in the queue
Retrieve()
Retrieve the first element in the queue
isEmpty()
Check if the queue is empty
isFull()
Check if the queue is full
Data Structures 39
Implementation of Queue using Array
• Size of queue using array is fixed.
• It can’t be modified dynamically.
Data Structures 40
void enqueue(int *a, int item, int *pfront, int *prear)
{
if (*prear == MAX-1)
{
print(“Queue is Full”);
}
else
{
(*prear)++;
a[*prear]=item;
if(*pfront==-1)
*pfront=0;
41
} Data Structures
void dequeue(int *a, int *pfront, int *prear)
{
int data;
if (*pfront == -1)
{
print(“Queue is Empty”);
return NULL;
}
else
{
data=a[*pfront];
a[*pfront]=0;
Data Structures 42
if(*pfront==*prear)
*pfront=*prear=-1;
else
(*pfront)++;
return data;
}
}
Data Structures 43
Call-
enqueue(a, 9, &front, &rear);
enqueue(a, 12, &front, &rear);
enqueue(a, 14, &front, &rear);
dequeue(a, &front, &rear);
dequeue(a, &front, &rear);
dequeue(a, &front, &rear);
Data Structures 44
Implementation of Queue using Linked List
• No restrictions on number of elements it can hold.
• Elements are allocated dynamically.
Data Structures 45
Struct node
{
int data;
struct node *next;
};
struct queue
{
struct node *front;
struct node *rear;
}; Data Structures 46
void initqueue(struct queue *);
void enqueue(struct queue *, int);
int dequeue(struct queue *);
void delallqueue(struct queue *);
Data Structures 47
void initqueue(struct queue *q)
{
q → front = q → rear=NULL;
}
Data Structures 48
void enqueue(struct queue *q, int item)
{
struct node *temp;
temp=(struct node*) malloc(sizeof(struct node));
if(temp==NULL)
{
print(“Queue is Full);
return;
}
Data Structures 49
else
{
temp →data=item;
temp →next=NULL;
}
Data Structures 50
if(q →front==NULL)
{
q →rear=q →front=temp;
}
else
{
q → rear → next=temp;
q → rear = q → rear → next;
}
}
Data Structures 51
int dequeue(struct queue *);
{
struct node *temp;
int item;
if(q →front==NULL)
{
Print(“Queue is Empty”);
return NULL;
}
Data Structures 52
else
{
item=q →front →data;
temp=q →front;
q →front=q →front →next;
free(temp);
return item;
}
Data Structures 53
void delallqueue(struct queue *q)
{
struct node *temp;
if (q →front==NULL)
return;
while(q →front !=NULL)
{
temp=q →front;
q →front=(q →front) →next;
free(temp);
}
}
Data Structures 54
Call-
enqueue(&a, 10);
enqueue(&a, 15);
enqueue(&a, 20);
dequeue(&a);
dequeue(&a);
dequeue(&a);
Data Structures 55
Circular Queue
• Better Utilization of Space
Data Structures 56
void insertqueue (int *a, int item, int *pfront, int *prear)
{
if((*prear==MAX-1 && *pfront==0) ||
(*prear+1==*pfront))
{
print("Queue is Full");
}
else if(*prear==MAX-1)
{
*prear=0;
a[*prear]=item;
}
Data Structures 57
else
{
(*prear)++;
a[*prear]=item;
}
if(*pfront==-1)
{
*pfront=0;
}
}
Data Structures 58
int deletequeue(int *a, int *pfront, int *prear)
{
int data;
if(*pfront==-1)
{
print("Queue is Empty");
return NULL;
}
Data Structures 59
else
{
data=a[*pfront];
a[*pfront=0;
if(*pfront==*prear)
{
*pfront=-1;
*prear=-1;
}
Data Structures 60
else if(*pfront==MAX-1)
{
*pfront=0;
}
else
{
(*pfront)++;
}
return data
}
}
Data Structures 61
Call-
insertqueue(a, 9, &front, &rear);
insertqueue(a, 12, &front, &rear);
insertqueue(a, 14, &front, &rear);
deletequeue (a, &front, &rear);
deletequeue (a, &front, &rear);
deletequeue (a, &front, &rear);
Data Structures 62
Priority Queue
• It is a collection of elements where each element is
assigned a priority and the order in which elements
are deleted and processed is determined from the
following:
• An element of higher priority is processed before
any element of lower priority.
• Two elements with the same priority are processed
according to the order in which they are added to
the queue.
• E.g. Time-sharinDgatasSytsrutcetumres. 63
• e.g. Time-sharing system.
• Programs of high priority are processed first
• Programs with same priority form a standard queue.
Data Structures 64
• Priority queue can be represented in memory by
means of one-way list.
• Each node in the list contains three items of
information-
– Information field - INFO
– Priority number - PRNO
– Link - NEXT
Data Structures 65
Data Structures 66
Array Implementation of Priority Queue
struct data
{
int item;
int priority;
int order;
};
struct pqueue
{
struct data d[MAX]
int front;
int rear;
}
Data Structures 67
void initpqueue(struct pqueue *pq)
{
int i;
pq →front= →rear=-1;
for(i=0 to MAX-1)
{
pq →d[i].item=0;
pq →d[i].priority=0;
pq →d[i].order=0;
}
}
Data Structures 68
void add (struct pqueue *pq, struct datadt)
{
struct data temp;
int i, j;
if (pq →rear==MAX-1)
{
Print(“Queue is Full.”);
return;
}
pq →rear++;
pq →d[pq →rear]=dt;
Data Structures 69
for(i=pq →front; i<pq →rear; i++)
{
for(j=i+1; j<=pq →rear; j++)
{
if(pq →d[i].priority>pq →d[j].priority)
{
temp=pq →d[i];
pq →d[i]=pq →d[j];
pq →d[j]=temp;
}
Data Structures 70
else
{
if(pq →d[i].priority==pq →d[j].priority)
{
if(pq →d[i].order>pq →d[j].order
{
temp=pq →d[i];
pq →d[i]=pq →d[j];
pq →d[j]=temp;
}
}
} }}}Data Structures 71
struct data delete(struct pqeueue *pq)
{
int dd;
struct data t;
dd=[Link];
[Link]=0;
[Link]=0;
if(pq →front==-1)
{
print(“Queue is Empty”);
return t;
} Data Structures 72
t=pq →d[pq →front];
if(pq →front==pq →rear)
{
pq →front==pq →rear=-1;
}
else
{
pq →front++;
}
return t;
} Data Structures 73
Applications of Queue
• Resource sharing like printer and CPU
– Job scheduling
• Asynchronous data transfer (file IO, pipes, sockets)
• Call Centre Phone System
• Breadth First Search and Traversal uses queue
Data Structures 74
Applications of Circular Queue
• Traffic Light Functioning
• Page Replacement Algorithms
Data Structures 75
Applications of Priority Queue
• Prim's Algorithm to find minimum cost spanning
tree
• Dijkstra's Algorithm to find shortest path.
• Priority queues can be used in heap sort
• Priority queues can be used in operating system for
load balancing
• Priority ques are used in Huffman codes for data
compression
Data Structures 76