Chapter 4

Stack and Queue

4.1. Stack
• Stacks are linear lists, in which insertion and deletion occur at the same end.
• All deletions and insertions occur at one end of the stack known as
the TOP.
• Data going into the stack first, leaves out last. Stacks are also known
as LIFO data structures (Last-In, First-Out).
Basic Stack Operations
• Push – Adds an item to the top of a stack.
• Pop – Removes an item from the top of the stack and returns it to the user.
• Peek – Copies the top item of the stack and returns it to the user; the item is
not removed, hence the stack is not altered.
Stack: a more restricted List with the following constraints:
• Elements are stored by order of insertion from "bottom" to "top“.
• Items are added to the top.
• 10/29/2023
Only the last element added onto the stack (the top element) can 1be
accessed or removed.
 stack

10/29/2023 2
 Example of stack

10/29/2023 3
• Implementation of Stack:
• There are two ways to implement a stack
 Using array
 Using linked list

10/29/2023 4
Source code for array implementation of Stack operations (PUSH and POP )
#include<iostream.h> int pop()
#define size 10 {
int Stack[size]; if(top == -1)
{
int top = -1;
cout<<"\n Stack is empty."<<endl;
int push(int x) return -1;
{ }
if(top == size) int t = Stack[top];
cout<<"\n Stack is full."<<endl; top--;
return t;
else
}
{ void display()
top++; {
Stack[top] = x; int t=top;
} while(t != -1)
{
}
cout<<Stack[t]<<endl;
t--;
}
10/29/2023 5
}
int main() for(int k=1;k<=s; k ++)
{ {
t=pop();
int s; if(k==1)
int a[10]; cout<<"1st popped element is : "<<t<<endl;
cout<<"How many elements do u else if(k==2)
want to store in a stack (<10):"; cout<<"2nd popped element is :
cin>>s; "<<t<<endl;
else if(k==3)
cout<<"\n\t Enter:\n"; cout<<"3rd popped element is : "<<t<<endl;
for(int i=0;i<s; i ++) else
{ cout<<k<<"th popped element is :
cout<<"\t\t element "<<(i+1)<<" :"; "<<t<<endl;
cin>>a[i]; }
}
push(a[i]);
}
cout<<"\n The stack is:"<<endl;
display();
int t;
10/29/2023 6
Infix to Postfix Conversion
• Infix is a natural way of expressing mathematical
expression.
• There are other ways of representing the same
expression:
• Prefix: + a b
• Postfix: a b +
• In high level languages, infix notation cannot be
used to evaluate expressions.
• We must analyze the expression to determine the
order in which we evaluate it.
• A common technique is to convert an infix
notation into postfix notation, then evaluating it.
10/29/2023 7
Rules:
• Operands immediately go directly to output.
• Operators are pushed into the stack (including parenthesis)
• Check to see if stack top operator is less than current operator
• If the top operator is less than, push the current operator onto stack
• If the top operator is greater than (or equal to) the current, pop top
operator and append on postfix notation, push current operator onto
stack.
• If we encounter a right parenthesis, pop from stack until we get
matching left parenthesis.
• Do not output parenthesis.
• Precedence Priority of operators:
• Priority 4: ‘(‘ - only popped if a matching ‘)’ is found.
• Priority 3: All unary operators (-, sin, cosin,….)
• Priority 2: / *
• Priority 1: + -
Exampl
10/29/2023 1: A + B * C - D / E 8
10/29/2023 9
 Exampl 3: a + b * c + ( d * e + f ) * g

Exercise
10/29/2023
:a+b*c+(d*e+f)*g 10
Postfix Evaluation Psuedocode
Operand: push Operator:
pop 2 operands, do the math,
push result back onto stack:
123+*

10/29/2023 11
Postfix Evaluation
Consider the postfix expression:
6523+8*+3+*
Algorithm:
initialise stack to empty;
while (not end of postfix expression) {
get next postfix item;
if(item is value)
push it onto the stack;
else if(item is binary operator) {
pop the stack to x;
pop the stack to y;
perform y operator x;
push the results onto the stack;
} else if (item is unary operator) {
pop the stack to x;
perform operator(x);
push the results onto the stack
10/29/2023 12
 4.2. Queue
• Queue is a linear data structure and an abstract data type
which is defined using some basic data type in programming
languages.
• Like the stack, the queue is a list-like structure that provides
restricted access to its elements.
• Queue elements may only be inserted at the back (called an
enqueue operation) and removed from the front (called a
dequeue operation).
• Queues operate like standing in line at a movie theater ticket
counter. If nobody cheats, then newcomers go to the back of
the line.
• The person at the front of the line is the next to be served.
Thus, queues release their elements in order of arrival.
• A queue a “FIFO” list, which stands for “First-In, First-
Out.”
10/29/2023 13
• A queue data structure is implemented using an array or
a linked-list type in a programming language.
• There are two pointers that mark both ends of a queue.
• Front
• Rear
• A queue works on FIFO principle, First In, First
out, any element that goes first must come out first.
• A queue is an ordered collection of items where an item
is inserted at one end and usually called REAR or
TAIL, and an item is removed from the other end,
usually called FRONT or HEAD of the queue.
• So, a queue is a dynamic list with limited across to
elements.
10/29/2023 14
 Dequeue Enqueue

Front Rear
Fundamental operations on queue
• There are 3 operations performed on a queue
– Enqueue (Insert)– insert element at the rear of the
queue.
– Dequeue (Delete)– remove elements from the front of
the queue.
– Display – display elements of queue.

When an item is taken from the queue, it always

New people must enter the queue at the rear. it is usually comes from the front. it is usually called a dequeue
10/29/2023 15
called an enqueue operation. operation.
1. Enqueue Operation
• The enqueue operation is performed in rear end
of the queue.
• You cannot insert into queue data structure if
queue is full.
• When the queue has space, the enqueue
operation insert an element and update the ‘rear’
pointer by incrementing it.

10/29/2023 16
• Q [1] = 44 and front = 1, Q [3] = 66 and rear = 4
• We will insert element 77 at the rear end of the queue,
i.e., Q [4] = 77.
• New status of the queue after enqueue operation will
be following.

10/29/2023 17
2. Dequeue Operation
• Dequeue operation removes an element from the
front of the queue. But the queue must not be
empty for dequeue operation to work. An
element from the front is removed and ‘front’
pointer is updated.
• For example:- Consider the status of a queue
given below

10/29/2023 18
• Q [1] = 34 and front = 1
• You decided to delete Q [1], after deletion front
=1+1=2
• The current queue is shown in following
diagram,

10/29/2023 19
Example:
Operation Content of queue
Enqueue(B) B
Enqueue(C) B, C
Dequeue() C
Enqueue(G) C, G
Enqueue (F) C, G, F
Dequeue() G, F
Enqueue(A) G, F, A
Dequeue() F, A
10/29/2023 20
3. Display Operation
• This is a simple operation where we traverse
through the entire queue and display the list of
elements.
• This function is the same for both array and
linked-list implementation of a queue data
structure.

10/29/2023 21
Queue Empty and Queue full Scenario
• Before inserting or deleting from queue we must
check for two conditions
– Is the queue empty?
– Is the queue full?
• Let’s see each scenario in more detail.
Queue Empty Scenario
• When queue is initiated both front = rear = 1,
but after that when front==rear then it means that
the queue is empty and we cannot delete from
the queue because that will be an underflow.
10/29/2023 22
• For example, Consider an array based empty
queue, where front = rear = 1.

We inserted 55
Q [1] = 55, rear = 1 + 1 = 2, front = 1
This is shown in the following diagram.

10/29/2023 23
• We inserted another element 66, now the queue is
• Q [2] = 66, rear = 2 + 1 = 3, front = 1

Now, let’s start deleting all the elements.

Delete the first element 55. Then the queue status is as follows.
Rear = 3, front = 1 + 1 = 2 and Q [2] = 66
The element Q [1] = 55 is deleted.

Next, we delete the element Q [2] = 66. The status of the queue after deletion is shown below.

Now, front = 2 + 1 = 3, rear = 3 and

since,
Front == rear
The queue is empty
10/29/2023 24
Queue Full Scenario
• To insert into a queue, you need to check if the queue is full, so
when the front == rear + 1, then the queue is full. Any attempt to
insert a new element will result in queue overflow.
• For example, Current status of a queue is as follows

In the diagram above,

Q [1] = 44 and front = 1. Also Q [4] = 77 and rear = 5
Now we want to insert a new element 88 at Q [5].
The new status of the queue will be
Q 10/29/2023
[1] = 44 and front = 1, Q [5] = 88 and rear + 1 = 5 + 1 = 6 25
• This is shown in the queue data structure diagram below.

Now finally, you will insert at Q [6] = 99. The status of the queue becomes
Q [1] = 44 and front = 1, Q [6] = 99 and rear + 1 = 6 + 1 = 7.

The rear value is greater than queue length. Then

rear + 1 = 7 mod 6 = 1
But, front = rear + 1 = 1
Then the queue is full and we cannot insert more elements.
10/29/2023 26
10/29/2023 27
Types of Queues in Data Structure
 Queue is an important structure for storing and
retrieving data and hence is used extensively among
all the data structures.
 Queue, just like any queue (queues for bus or tickets
etc.) follows a FIFO mechanism for data retrieval
which means the data which gets into the queue first
will be the first one to be taken out from it, the second
one would be the second to be retrieved and so on.
 There are four types of Queue:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double Ended Queue)
10/29/2023 28
1. Simple Queue
• Simple queue defines the simple operation of queue in
which insertion occurs at the rear of the list and deletion
occurs at the front of the list.

 As is clear from the name itself, simple queue lets us perform the
operations simply. i.e., the insertion and deletions are performed
likewise.
 Insertion occurs at the rear (end) of the queue and deletions are
performed at the front (beginning) of the queue list.
10/29/2023 29
• C++ Program to Implement Simple Queue using Array
#include <iostream> void Delete() {
using namespace std; if (front == - 1 || front > rear) {
int queue[100], front = - 1, rear = - 1; cout<<"Queue Underflow ";
return ;
void Insert() { } else {
int val; cout<<"Element deleted from queue is
if (rear == n - 1) : "<< queue[front] <<endl;
cout<<"Queue Overflow"<<endl; front++;;
else { }
if (front == - 1) }
front = 0;
cout<<"Insert the element in queue"<<endl; void Display() {
cin>>val; if (front == - 1)
rear++; cout<<"Queue is empty"<<endl;
queue[rear] = val; else {
} cout<<"Queue elements are : ";
} for (int i = front; i <= rear; i++)
cout<<queue[i]<<" ";
cout<<endl;
}
}
10/29/2023 30
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete(); case 3: Display();
break; break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
10/29/2023
} 31
2. Circular Queue
• In a circular queue, all nodes are treated as circular. Last node is
connected back to the first node.
• Circular queue is also called as Ring Buffer.
• Circular queue contains a collection of data which allows
insertion of data at the end of the queue and deletion of data at the
beginning of the queue.

 The above figure shows the structure of circular queue. It stores

an element in a circular way and performs the operations
according to its FIFO structure.
10/29/2023 32
• A program to implement circular queue in C++ is
given as follows −
if (front == -1) {
#include <iostream> front = 0;
using namespace std; rear = 0;
int cqueue[5]; }
int front = -1, rear = -1, n=5; else {
if (rear == n - 1)
void insertCQ(int val) { rear = 0;
if ((front == 0 && rear == n-1) else
|| (front == rear+1)) { rear = rear + 1;
cout<<"Queue Overflow \n"; }
return; cqueue[rear] = val ;
} }
10/29/2023 33
 cout<<"Queue is empty"<<endl;
void deleteCQ() {
return;
if (front == -1) {
}
cout<<"Queue Underflow\n";
cout<<"Queue elements are :\n";
}
if (f <= r) {
cout<<"Element deleted from queue is :
while (f <= r){
"<<cqueue[front]<<endl;
cout<<cqueue[f]<<" ";
if (front == rear) {
f++;
front = -1;
}
rear = -1;
} else {
}
while (f <= n - 1) {
else {
cout<<cqueue[f]<<" ";
if (front == n - 1)
f++;
front = 0;
}
else
f = 0;
front = front + 1;
while (f <= r) {
}
cout<<cqueue[f]<<" ";
}
f++;
void displayCQ() {
}
int f = front, r = rear;
}
if (front == -1)
cout<<endl;
{ 10/29/2023 34
}
int main() { case 2:
int ch, val; deleteCQ();
cout<<"1)Insert\n"; break;
cout<<"2)Delete\n";
case 3:
cout<<"3)Display\n";
cout<<"4)Exit\n"; displayCQ();
do { break;
cout<<"Enter choice : "<<endl; case 4:
cin>>ch; cout<<"Exit\n";
switch(ch) { break;
case 1:
default: cout<<"Incorrect!\
cout<<"Input for insertion:"<<endl;
cin>>val; n";
insertCQ(val); }
break; } while(ch != 4);
return 0;
10/29/2023 } 35
3. Priority Queue
• Priority queue contains data items which have some preset
priority. While removing an element from a priority queue, the
data item with the highest priority is removed first.
• In a priority queue, insertion is performed in the order of arrival
and deletion is performed based on the priority.

10/29/2023 36
 Cont….
• A priority queue is a special type of queue in which each element is
associated with a priority and is served according to its priority. There
are two types of Priority Queues. They are:
• Ascending Priority Queue: Element can be inserted arbitrarily but only
smallest element can be removed.
For example, suppose there is an array having elements 4, 2, 8 in the same
order. So, while inserting the elements, the insertion will be in the same
sequence but while deleting, the order will be 2, 4, 8.
• Descending priority Queue: Element can be inserted arbitrarily but
only the largest element can be removed first from the given Queue.

For example, suppose there is an array having elements 4, 2, 8 in the same

order. So, while inserting the elements, the insertion will be in the same
sequence but while deleting, the order will be 8, 4, 2.

10/29/2023 37
//C++ Program to Implement Priority Queue
#include <iostream> //Insert into Priority Queue
void insert(int item, int priority)
#include <cstdio>
{
#include <cstring> node *tmp, *q;
#include <cstdlib> tmp = new node;
using namespace std; tmp->info = item;
struct node //Node Declaration tmp->priority = priority;
{ if (front == NULL || priority < front->priority)
int priority; {
int info; tmp->link = front;
struct node *link; front = tmp;
}
}; //Class Priority Queue
else
class Priority_Queue {
{ q = front;
private: while (q->link != NULL && q->link->priority <= prior-
node *front; ity)
public: q=q->link;
Priority_Queue() tmp->link = q->link;
{ q->link = tmp;
front = NULL; }
}
}
10/29/2023 38
//Delete from Priority Queue void display()
void del() {
node *ptr;
{ ptr = front;
node *tmp; if (front == NULL)
if(front == NULL) cout<<"Queue is empty\n";
cout<<"Queue Underflow\n"; else
else {cout<<"Queue is :\n";
cout<<"Priority Item\n";
{ while(ptr != NULL)
tmp = front; {
cout<<"Deleted item is: "<<tmp- cout<<ptr->priority<<" "<<
>info<<endl; ptr->info<<endl;
front = front->link; ptr = ptr->link;
}
free(tmp); }
} }
} };
//Print Priority Queue

10/29/2023 39
//Main case 2:
int main() pq.del();
{ break;
int choice, item, priority; case 3:
Priority_Queue pq; pq.display();
do break;
{ case 4:
cout<<"1.Insert\n"; break;
cout<<"2.Delete\n"; default :
cout<<"3.Display\n"; cout<<"Wrong choice\n";
cout<<"4.Quit\n"; }
cout<<"Enter your choice : "; }
cin>>choice; while(choice != 4);
switch(choice) return 0;
{ }
case 1:
cout<<"Input the item value to be added in the
queue : ";
cin>>item;
cout<<"Enter its priority : ";
cin>>priority;
pq.insert(item, priority);
break;
10/29/2023 40
4. Double Ended Queue (Dequeue)
• In Double Ended Queue, insert and delete operation can be
occur at both ends that is front and rear of the queue.

• The doubly ended queue or dequeue allows the insert and delete
operations from both ends (front and rear) of the queue.
• Queues are an important concept of the data structures and
understanding their types is very necessary for working
appropriately with them.

10/29/2023 41
#include<iostream>
#include <deque>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
deque<int> d;
deque<int>::iterator it;
int c, item;
while (1) {
cout<<"1.Size of the Deque"<<endl;
cout<<"2.Insert Element at the End"<<endl;
cout<<"3.Insert Element at the Front"<<endl;
cout<<"4.Delete Element at the End"<<endl;
cout<<"5.Delete Element at the Front"<<endl;
cout<<"6.Front Element at Deque"<<endl;
cout<<"7.Last Element at Deque"<<endl;
10/29/2023 42
cout<<"8.Display Deque"<<endl;
cout<<"9.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Size of the Deque: "<<d.size()<<endl;
break;
case 2:
cout<<"Enter value to be inserted at the end:;
cin>>item;
d.push_back(item);
break;
case 3:
cout<<"Enter value to be inserted at the front: ";
cin>>item;
d.push_front(item);
break;
case 4:
item = d.back();
d.pop_back();
cout<<"Element "<<item<<" deleted"<<endl;
10/29/2023 43
break;
case 5: case 8:
item = d.front(); cout<<"Elements of Deque: ";
d.pop_front(); for (it = d.begin(); it != d.end(); it++)
cout<<"Element "<<item<<" deleted"<<endl; cout<<*it<<" ";
break; cout<<endl;
case 6: break;
cout<<"Front Element of the Deque: "; case 9:
cout<<d.front()<<endl; exit(1);
break; break;
case 7: default:
cout<<"Back Element of the Deque: "; cout<<"Wrong Choice"<<endl;
cout<<d.back()<<endl; }
break; }
return 0;
}

10/29/2023 44