DATSTRUCTURES AND ALGORITHMS
UNIT 2 – STACK AND QUEUE
STACK
Stack is a linear data structure and it is very much useful in various applications
of computer.
E.g Trains in Railway yard, Goods in cargo, Plates on a tray.
Definition : Stack is an ordered collection of homogeneous data element where the
insertion and deletion operations take place at one end only.
The insertion and deletion operations in case of stack is
specially termed as PUSH and POP respectively.
And the position of the stack where these operations are
performed is known as TOP of the stack
An element in a stack is termed as ITEM.
The maximum number of elements that a stack can
accommodate is termed as SIZE.
Stack can be represented in the memory in two way
i) one dimensional array ii) Single Linked List
Basic operations to manipulate stack are
PUSH : Insert an item into stack
POP : Remove an item from stack
Input : The new element ITEM to be pushed on it.
Output: Stack with newly pushed item
Algorithm:
1. IF TOP >=SIZE the
Print “Stack is Full”
2. Else
TOP = TOP +1
A[TOP] = ITEM
3. End if
4. Stop
Input : Stack with elements
Output: Removes an ITEM from TOP
Algorithm:
1. IF TOP < 1
Print “Stack is empty”
2. Else
ITEM=A[TOP]
TOP = TOP -1
3. End if
4. Stop
Input: Stack with elements
Output: Find the stack is empty or not
A Singly Linked List Structure whose pointer to the header is known as stack head and TOP is
the pointer of the first node.
1. Ptr = Stack_HEAD Link
2. If (PTR= Null) then
print “Stack is empty”
3. Else
node count = 0
a. While (ptr ≠ Null) do
node count = nodecount+1
b. ptr = ptr Link
4. End while
5. Print” The item at the front is “TOP DATA” stack contains “node count”
no.of.items
6. End IF
7. Stop
TO FIND THE STATUS
1. IF TOP < 1 then
print “Stack is empty”
2. Else
1. If(TOP > =size) then
Print “Stack is Full”
3. Else
Print “The Element at TOP is”, A[TOP]
free=(SIZE-TOP)/Size*100
Print % of free stack is”, Free
4. Endif
Endif
5. stop
Define Stack using Linked List
Input : ITEM is the element to be inserted
Output : Single Linked List with newly inserted ITEM
Datastructure: Linked List pointer to header is known from STACK_HEAD and TOP is the
pointer to the first node.
Steps:
1. new = GETNODE(NODE)
2. new.DATA = ITEM
3. new.LINK = TOP
4. TOP = new
5. STACK_HEAD.LINK = TOP
6. Stop
Applications of STACK
A classical application deals with evaluation of arithmetic expression
Some machines used built-in Stack hardware called “Stack machines”.
Another important application of stack is during the execution of recursive programs
Evaluation of STACK
An arithmetic expression consists of operands and operators.
Operands are variables or constants and operators are various types like arithmetic,
Unary, binary operator %remainder, relational operators and Boolean operators.
( A +B*C / D - E^F * G
2
1
3
5 4
6
Evaluating the expression is the order of evaluation
[i] ^
[ii] * /
[iii] + -
<, <= , < > ,>=
AND, OR, XOR
1. Precedence and associativity Rules
2. Parenthesized version of expression
3. ((A+B) * ((C/D) – (E ^ (F *G)))
4. Whatever we specify the order of evaluations the problem is
i) Scanning the expression Left to Right Repeatedly.
ii) How compiler generate correct code for given expression especially for parenthesized
expression. This problem could be solved with 2 ways.
iii) conversion of given expression into special Notation
iv) Production of object code using stack.
Notation for arithmetic expressions
There are three notations to represent an arithmetic expressions are infix, prefix
and Postfix.
The conventional way of writing an expression is called infix for e.g
A+B C-D E*F G/H
Infix : A +(B*C)/D
Prefix : + /*ADBC
Postfix: BCDA */+
a-(b*c-d)/e
Char Stack Postfix
notation
a -
a
- -
a
( ( a
b (- ab
* *( - ab
c *( -
abc
- -(- abc*
d -(-
abc*d
) -
abc*d-
Infix Prefix
Postfix
(A + B)*C/D /*+ ABCD
AB+C*D/
Queue
Queue is a simple but very powerful data structure to solver numerous computer Applications
e.g Queue of customer, Traffic passing at turning point.
Definition: Queue is linear data structure with ordered collection of homogeneous data elements.
Where insertion (ENQUEUE) and deletion(DEQUEUE) operations take place at two ends called
REAR and FRONT.
Elements in a queue are termed as ITEM.
The number of elements that a queue can accommodate is termed as LENGTH
Data in a queue is processed in the same order as it was entered ie First-in-First-out
Representation of Queues:
1. Using an array first kind of representation uses one dimensional array, where queue of fixed
size.
2. Using Linked list, Doubly Linked list provides a queue whose size can vary during processing
queue.
Three state of queue is as follows:
Queue is empty:
FRONT = 0
REAR = 0
Queue is Full:
REAR = N
FRONT = 1
Queue contains Element >= 1
FRONT <= REAR
No.of.element = REAR – FRONT + 1
Insert an element into a queue
Input: an element ITEM that has to be inserted
Output: The ITEM added the REAR of the Queue
Steps:
1. IF(REAR = N)then
PRINT “Queue is full”
Exit
2. Else
If(REAR=0) and (FRONT=0)
i) FRONT = 1
ii) Endif
iii) REAR = REAR+1
iv) Q[REAR] = ITEM
3. Endif
4. stop
Delete a element in the a queue
1. If (FRONT = 0) then
Print “Queue is empty”
Exit
2. Else
1. ITEM = Q[FRONT]
2. If (FRONT = REAR)
3. REAR = 0
FRONT = 0
3. ELSE
FRONT = FRONT +1
4. END IF
5 ENDIF
4. STOP.
Operations of QUEUE
Fron Rea
1. ENQUEUE t r
2. DEQUEUE
3. EMPTY 2 4 1 3 6 5
4. Front
Implementation of QUEUE 0 1 2 3 4 5 6 7 8
Array Implementation 9 10
e.G int A[10]
Let us say we want to insert no.5 to the Queue.
We will increment the rear. After insertion new rear Index is 7 and value
By increasing front I have discarded Index 2 from the queue don’t bother about the value in
the cell.
Queue using Singly linked list.
Front will always point the starting position of the Queue.
Rear will always point the last element of the Queue
If the queue is full we need larger array to fill the elements is costly hence we nee Linked
list.
Avoid blocking large amount of memory
You can do the Enqueue operation on Head side and Dequeue
operation on tail side .
Struct node{
int data;
Struct Node* link;
};
Struct Node* Front = Null;
Struct Node* rear = Null;
Void Enqueue( int x){
Struct Node* temp= (struct Node*)malloc(sizeof(struct Node*));
Temp data = x;
Temp next= Null;
If(front= = null && Rear = = null){
Fornt = rear = temp;
Return;
}
Rear next = temp;
Rear = temp;
}
fro rear
nt
0 0 Enqueue
1
ear tem
r 0 Inset couldn’t done is
1 p
fro 0 0 100 2 cases
n1t Enqueu Queue is empty
0 Front and Rear = Null
10 e2
2
0 0
m p
te
20
0
10
02
4 0 Enqueu
200 e4
Void dequeue()
{
If (front = = Null)
return;
Qnode* temp = front;
Front = front next;
// If front becomes Nulll change the rear also Null
if(front = = Null)
rear = = Null;
delete(temp);
}
};
Int main()
{ Queue q;
q. enqueuer(10);
q. enqueuer(20);
q.dequeuer(0);
q.dequeuer();
cout<<Queue fornt “<<(q.front) data endl;
cout<<Queue rear “<<(q.rear) data;
}
Circular Queue
Procedure: CQINSERT(F,R,Q,N,Y)
Given pointers to the front and rear of circular queue.
F & R a Vector Q consisting of n elements and an element y, this procedure inserts y at the
rear of queue.
Intially F and R are set to zero.
Step-1: [REAR rear pointer?]
If R = N
then R 1
else R R + 1
Step-2: [Overflow?]
If F = R
then write(‘overflow’)
Return
Step-3:
[Insert element]
Q[R] y
Step – 5:
[ Is Front pointer properly set?]
If F=0
then F 1
Return
Function: CQDELETE(F,R,Q,N)
Given ‘F’ AND ‘R’ pointers to the front and rear of circular queue respectively, and
a vector queue consisting of ‘N’ elements, this function deletes and returns the elements of ‘Q’
‘y’ is a temporary variable.
Step – 1:
[Underflow?]
If F = 0
then write(‘UNDERFLOW’)
Return(0)
Step-2:
[Delete element]
y Q[F]
Circular Queue is a linear data structure in which the operations are
performed based on FIFO (First In First Out) principle and the last position
is connected back to the first position to make a circle. It is also
called ‘Ring Buffer’.
Rear pointer can point to the beginning of the
Queue when it reaches and of the Queue.
Adv: Empty space can be filled again using
rear pointer.
Intially front = Rear = 0
Rear = 7
rear = rear +1 Mod n
7+ 1 mod 8
8 mod 8
0
Operations on Circular Queue
Front: Get the front item from queue.
Rear: Get the last item from queue.
enQueue(value) This function is used to insert an element into the circular queue. In a circular
queue, the new element is always inserted at Rear position.
Steps:
Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 &&
front != 0) if it is true then set rear=0 and insert element.
deQueue() This function is used to delete an element from the circular queue. In a circular
queue, the element is always deleted from front position.
Steps:
1. Check whether queue is Empty means check (front==-1).
2. If it is empty then display Queue is empty. If queue is not empty then step 3
3. Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it
is true then set front=0 and return the element.
#include<iostream.h> Else
#include<stdlib.h> { if (front = = -1)
Class circular_queue front = 0;
{ rear = (rear + 1) % 5;
int a[5], front,rear; a[rear] = x;
Public: cout<<“front “<<front<<“
circular _queue(0 rear:”<<rear<<endl;
}}
{
void del()
front = -1; { if (front = = -1)
rear = -1; {cout<<“Queue is full”<<endl;
} return;}
Void insert(int x) Else
{ { if (front = = rear)
if(front = = 0 && rear = = 4) { front = -1;
{ rear = -1;
cout<<“Queue is full”<<endl; }
Else
return;
{
} front= (front+1) % 5: }
Elseif(front = = rear+1){ }
cout<<“Queue is full”<<endl; }
return;
Void display()
{ int I;
if(front = = -1)
{
cout<<“Queue is empty”<<endl;
return;}
Else
for (I = front; i!= rear; i=(i+1)%5)
{ cout<<a[i]<<“->>”; }
cout<<a[i]<<endl; } };
int main()
{ int ch; int item; circular_queue q:
Cin >> item;
sqitch(ch)
{
Case1 : q.insert;
Case2 : q.delete;
Case1 : q.desplay;
Case1 : q.exit;}
return;
}
fron Rea
Step 3: t r
[Queue empty?] Deleti Deleti
If F = R on
Inserti on
Inserti
then F R 0 on on
Return(y)
Step 4: A deque
[ Increment front pointer] structure
If F = N
then F 1
else F F + 1
Return(y)
Dequeue
The expansion for “Dequeue” is Double ended queue.
Another variation of the queue is known as “Dequeue”.
Unlike a queue in deque, both the insertion and deletion operation can be made at either
end of the structure.
fron Rea
t r
Deleti Deleti
on on
There are 2 known variations deque Inserti
Input restricted deque on
Ouput restricted deque Input restricted
deque
Input restricted deque:
It is a deque which allows insertion at one end(say rear end) only.
But allows deletion at both ends.
Output restricted deque
It is a deque where deletion takes place at one end only(say front) only.
but allows insertions at both ends.
fron Rea
t r
Deleti
on Inserti
Inserti
on
on
Output restricted
Deque
