CHAPTER 4

Stack and Queues

Think of a stack like a pile of pancakes.
In a pile of pancakes, the pancakes are both added and removed from the top. So when removing a
pancake, it will always be the last pancake you added. This way of organizing elements is called LIFO:
Last In First Out.

Basic operations we can do on a stack are:

• Push: Adds a new element on the stack.
• Pop: Removes and returns the top element from the stack.
• Peek: Returns the top element on the stack. This is used to get the top most element of the stack
• isEmpty: Checks if the stack is empty.
• isFull(), This is used to check whether stack is full or not
• Size: Finds the number of elements in the stack.

Stacks can be implemented by using arrays or linked lists.

Stacks can be used to implement undo mechanisms, to revert to previous states, to create algorithms for
depth-first search in graphs, or for backtracking.
Address(index) of
an element

1. . Top
2. .
3. .
4. .
 STACK DATA STRUCTURE
Implementation

2/25/2026 COLLECTED BY Eng A4K 4

Stack is a linear data structure which follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or
FILO(First In Last Out).
There are many real-life examples of a stack. Consider an example of plates
stacked over one another in the canteen. The plate which is at the top is the
first one to be removed, i.e. the plate which has been placed at the
bottommost position remains in the stack for the longest period of time.
So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last
Out) order.
Deletion(pop) and insertion(push) happens on the same end.

Implementation of Stack Data Structure:

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and
Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size.

2/25/2026 COLLECTED BY Eng A4K 5

Mainly the following three basic operations are performed in the stack:

Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are
pushed. If the stack is empty, then it is said to be an Underflow condition.
Peek or Top: Returns top element of stack.
isEmpty: Returns true if stack is empty, else false.

Applications of stack:

✓ Balancing of symbols
✓ Infix to Postfix /Prefix conversion
✓ Redo-undo features at many places like editors, photoshop.
✓ Forward and backward feature in web browsers
✓ Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
✓ Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and
sudoku solver
✓ In Graph Algorithms like Topological Sorting and Strongly Connected Components

2/25/2026 COLLECTED BY Eng A4K 6

Implementing Stack using Arrays

else { int main() {

/* C++ program to implement basic stack a[++top] = x; Stack s;
operations */ cout << x << " pushed into stack\n"; [Link](10);
#include <iostream> return true; } } [Link](20);
#include<cstdlib> int Stack::pop() { [Link](30);
using namespace std; if (top < 0) { cout << [Link]() << " Popped
#define MAX 1000 cout << "Stack Underflow"; from stack \n ";
class Stack { return 0; } return 0;
int top; else { }
public: int x = a[top--];
int a[MAX]; // Maximum size of Stack return x; } }
Stack() { top = -1; } bool Stack::isEmpty() {
bool push(int x); return (top < 0); }
int pop(); // Driver program to test above functions
int peek();
bool isEmpty();
};
bool Stack::push(int x) {
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
}
2/25/2026 COLLECTED BY Eng A4K 7
 Output :
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack

Reasons to implement stacks using arrays(Pros):-

✓ Memory Efficient: Array elements do not hold the next elements address like linked list nodes do.
✓ Easier to implement and understand: Using arrays to implement stacks require less code than using
linked lists, and for this reason it is typically easier to understand as well.
✓ Easy to implement. Memory is saved as pointers are not involved.

A reason for not using arrays to implement stacks (cons):-

✓ Fixed size: An array occupies a fixed part of the memory. This means that it could take up more
memory than needed, or if the array fills up, it cannot hold more elements.
✓ It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.

2/25/2026 COLLECTED BY Eng A4K 8

Implementing Stack using Linked List

// C++ program for linked list implementation of stack stackNode->next = *root;

#include <iostream> *root = stackNode;
#include<cstdlib> cout << data << " pushed to stack\n";
using namespace std; }
class StackNode {// A structure to represent a stack int pop(StackNode** root) {
public: int INTMIN;
int data; if (isEmpty(*root))
StackNode* next; return INTMIN;
}; StackNode* temp = *root;
StackNode* newNode(int data) { *root = (*root)->next;
StackNode* stackNode = new StackNode(); int popped = temp->data;
stackNode->data = data; free(temp);
stackNode->next = NULL; return popped;
return stackNode; }
} int peek(StackNode* root) {
int isEmpty(StackNode* root) { int INTMIN;
return !root; if (isEmpty(root))
} return INTMIN;
void push(StackNode** root, int data) { return root->data;
StackNode* stackNode = newNode(data); }

2/25/2026 COLLECTED BY Eng A4K 9

int main() { Output:
StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
10 pushed to stack
push(&root, 30); 20 pushed to stack
cout << pop(&root) << " popped from stack\n"; 30 pushed to stack
cout << "Top element is " << peek(root) << endl; 30 popped from stack
return 0; Top element is 20
}

A reason for using linked lists to implement stacks(pros):

Dynamic size: The stack can grow and shrink dynamically, unlike with arrays.

Reasons for not using linked lists to implement stacks(cons):

Extra memory: Each stack element must contain the address to the next element (the next linked list
node). This is it requires extra memory due to involvement of pointers
Readability: The code might be harder to read and write for some because it is longer and more complex.

2/25/2026 COLLECTED BY Eng A4K 10

Stack in C++ STL

Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element
is added at one end and (top) an element is removed from that end only.

The functions associated with stack are:

empty() – Returns whether the stack is empty
size() – Returns the size of the stack
top() – Returns a reference to the top most element of the stack
push(g) – Adds the element ‘g’ at the top of the stack
pop() – Deletes the top most element of the stack

2/25/2026 COLLECTED BY Eng A4K 11

// CPP program to demonstrate working of STL stack cout << "\[Link]() : ";
#include <iostream> [Link]();
#include <stack> showstack(s);
using namespace std; return 0;
void showstack(stack <int> s) { }
while (![Link]()) {
cout << '\t' << [Link]();
[Link]();
}
cout << '\n';
}
int main () {
stack <int> s;
[Link](10);
[Link](30);
[Link](20);
[Link](5); Output:
[Link](1); The stack is : 1 5 20 30 10
cout << "The stack is : "; [Link]() : 5
showstack(s); [Link]() : 1
cout << "\n [Link]() : " << [Link](); [Link]() : 5 20 30 10
cout << "\n [Link]() : " << [Link]();

2/25/2026 COLLECTED BY Eng A4K 12

List of functions of Stack in STL:

✓ stack::top()
✓ stack::empty() and
stack::size()
✓ stack::push() and
stack::pop()
✓ stack::swap()
✓ stack::emplace()

2/25/2026 COLLECTED BY Eng A4K 13

 QUEUE DATA STRUCTURE
Implementation

2/25/2026 COLLECTED BY Eng A4K 14

A Queue is a linear structure which follows a particular order in which the operations are performed.
The order is First In First Out (FIFO).
A good example of a queue is any queue of consumers for a resource where the consumer that came first is
served first.
The difference between stacks and queues is in removing.
In a stack we remove the item the most recently added; in a queue, we remove the item the least recently
added.
Insertion/enqueue and deletion/dequeue happen on different ends.

Front Rear

2/25/2026 COLLECTED BY Eng A4K 15

Operation in Queue −
isFull(): This is used to check whether queue is full or not
isEmpry(): This is used to check whether queue is empty or not
insert(x)/ Enqueue(x) : This is used to add x into the queue at the rear end
delete()/ Dequeue() : This is used to delete one element from the front end of the queue
size(): this function is used to get number of elements present into the queue

Applications of Queue Data Structure

Queue is used when things don’t have to be processed immediately, but have to be processed in First
In First Out order like Breadth First Search. This property of Queue makes it also useful in following
kind of scenarios.
1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk
Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.

Implementation:
In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of
queue and rear points to last item.

enQueue() This operation adds a new node after rear and moves rear to the next node.
deQueue() This operation removes the front node and moves front to the next node.
2/25/2026 COLLECTED BY Eng A4K 16
Implement Queue using Array

Implementation Steps
Based on the below implementation. Here are the steps to implement queue using array:

1. Initialize Queue: Create an array queue[100] and set front and rear to -1 to indicate an empty
queue.
2. Predefine Input Values: Store input elements in input_values[] for insertion.
3. Insert Operation: Before inserting an element to the queue, check for overflow (rear == n - 1). If
queue is initially empty, set front = 0. And, insert next value from input_values[] into the queue
and increment rear.
4. Delete Operation Before deleting an element from the queue, check for underflow (front == -1 ||
front > rear). If valid, remove element at front and increment front.
5. Display Operation: For the display operation, check if queue is empty, show a message.
Otherwise, print elements from front to rear.
6. Main Function Execution: In the main() function, perform a sequence operations such as
insertion, deletion, and display to demonstrate queue functionality.

2/25/2026 COLLECTED BY Eng A4K 17

#include <iostream>
using namespace std;

int queue[100], n = 100, front = -1, rear = -1;

int input_values[] = {10, 20, 30, 40, 50};
int input_index = 0;
int total_inputs = sizeof(input_values) / sizeof(input_values[0]);

void Insert() {
if (rear == n - 1) {
cout << "Queue Overflow" << endl;
} else {
if (front == -1)
front = 0;
if (input_index < total_inputs) {
int val = input_values[input_index++];
cout << "Inserting element: " << val << endl;
rear++;
queue[rear] = val;
} else {
cout << "No more predefined elements to insert." << endl;
}
}
}
2/25/2026 COLLECTED BY Eng A4K 18
 void Delete() {
if (front == -1 || front > rear) {
cout << "Queue Underflow" << endl;
return;
} else {
cout << "Element deleted from queue is: " << queue[front] << endl;
front++;
}
}

void Display() {
if (front == -1 || front > rear)
cout << "Queue is empty" << endl;
else {
cout << "Queue elements are: ";
for (int i = front; i <= rear; i++)
cout << queue[i] << " ";
cout << endl;
}
}

2/25/2026 COLLECTED BY Eng A4K 19

 int main() {
Insert();
Insert();
Display();
Delete();
Display();
Insert();
Insert();
Insert();
Insert();
Display();
return 0;
}
output :
Inserting element: 10
Inserting element: 20
Queue elements are: 10 20
Element deleted from queue is: 10
Queue elements are: 20
Inserting element: 30
Inserting element: 40
Inserting element: 50
No more predefined elements to insert.
Queue elements are: 20 30 40 50

2/25/2026 COLLECTED BY Eng A4K 20

Reasons to implement queues using arrays(pros):

• Memory Efficient: Array elements do not hold the next elements address like linked list nodes do.
• Easier to implement and understand: Using arrays to implement queues require less code than
using linked lists, and for this reason it is typically easier to understand as well.

Reasons for not using arrays to implement queues(cons):

• Fixed size: An array occupies a fixed part of the memory. This means that it could take up more
memory than needed, or if the array fills up, it cannot hold more elements. And resizing an array
can be costly.
• Shifting cost: Dequeue causes the first element in a queue to be removed, and the other elements
must be shifted to take the removed elements' place. This is inefficient and can cause problems,
especially if the queue is long.
• Alternatives: Some programming languages have built-in data structures optimized for queue
operations that are better than using arrays.

2/25/2026 COLLECTED BY Eng A4K 21

/* A CPP program to demonstrate linked list based implementation of queue */

// A utility function to create an empty queue

#include <iostream>
Queue* createQueue() {
using namespace std;
Queue* q = new Queue();
// A linked list (LL) node to store a queue entry
q->front = q->rear = NULL;
struct QNode {
return q;
int key;
}
QNode* next;
// The function to add a key k to q
};
void enQueue(Queue* q, int k) {
/* The queue, front stores the front node of LL and
// Create a new LL node
rear stores the last node of LL */
QNode* temp = newNode(k);
struct Queue {
// If queue is empty, then new node is front and rear both
QNode *front, *rear;
if (q->rear == NULL) {
};
q->front = q->rear = temp;
// A utility function to create a new linked list node.
return;
QNode* newNode(int k) {
}
QNode* temp = new QNode();
// Add the new node at the end of queue and change rear
temp->key = k;
q->rear->next = temp;
temp->next = NULL;
q->rear = temp;
return temp;
}
}
// Function to remove a key from given queue q
QNode* deQueue(Queue* q) {
// If queue is empty, return NULL.
if (q->front == NULL)

2/25/2026 COLLECTED BY Eng A4K 22

 // Driver code
return NULL;
int main() {
// Store previous front and move front one node ahead
Queue* q = createQueue();
QNode* temp = q->front;
enQueue(q, 10);
delete(temp);
enQueue(q, 20);
q->front = q->front->next;
enQueue(q, 30);
// If front becomes NULL, then change rear also as NULL
enQueue(q, 40);
if (q->front == NULL)
enQueue(q, 50);
q->rear = NULL;
QNode* n = deQueue(q);
return temp;
if (n != NULL)
}
cout << "Dequeued item is " << n->key;
return 0;
}

Output:
Dequeued item is 10

2/25/2026 COLLECTED BY Eng A4K 23

Reasons for using linked lists to implement queues(pros):

Dynamic size: The queue can grow and shrink dynamically, unlike with arrays.
No shifting: The front element of the queue can be removed (dequeue) without having to shift other
elements in the memory.

Reasons for not using linked lists to implement queues(cons):

Extra memory: Each queue element must contain the address to the next element (the next linked list
node).
Readability: The code might be harder to read and write for some because it is longer and more
complex.

2/25/2026 COLLECTED BY Eng A4K 24

Queue implementation in C++ STL
#include <iostream>
#include <queue>
using namespace std;

int main(){
queue<int> q;
[Link](10); A queue is a container adapter that stores elements in
[Link](5); FIFO (First In, First Out) order.

// Accessing the front and back elements

cout << "Front element: " << [Link]() << endl;
cout << "Back element: " << [Link]() << endl;

// Removing an element from the front

[Link]();

cout << "Front element after pop: " << [Link]() << endl;
return 0;
}
Output
Front element: 10
Back element: 5
Front element after pop: 5
2/25/2026 COLLECTED BY Eng A4K 25
Important notes in the implementation of queue in STL

Syntax
Queue is defined as the std::queue class template inside <queue> header file.
queue<T> q;
where,
T: DataType of elements in the queue.
q: Name assigned to the queue.
Basic Operations
Here are the basic operations that can be performed on a queue:

2/25/2026 COLLECTED BY Eng A4K 26

1. Inserting Elements
New elements can only be inserted at back of the queue using push() function.
The process of inserting elements in a queue is also called enqueue.
#include <iostream>
#include <queue>
using namespace std;

int main(){
queue<int> q;

// Pushing elements into the queue

[Link](3);
[Link](4);
[Link](5);

return 0;
}

2/25/2026 COLLECTED BY Eng A4K 27

2. Accessing Elements
Only the front and back elements of the queue can be accessed by using front() and back() functions
respectively.
#include <iostream>
#include <queue>
using namespace std;

int main(){
queue<int> q;
[Link](3);
[Link](4);
[Link](5);

// Accessing the front and back elements

cout << [Link]() << endl;
cout << [Link]();

return 0;
}

Output
3
5
2/25/2026 COLLECTED BY Eng A4K 28
3. Deleting Elements
• Elements can only be deleted from the front of the queue using the pop() function.
• The process of deleting elements from a queue is also called dequeue.

#include <iostream>
#include <queue>
using namespace std;

int main(){
queue<int> q;
[Link](3);
[Link](4);
[Link](5); Output
45
// Deleting elements from the front of the queue
[Link]();
Note: To delete an element from the middle of a
queue, you must traverse the queue, which
while (![Link]()){
takes O(n) time in the worst case.
cout << [Link]() << " ";
[Link]();
}
return 0;
}
2/25/2026 COLLECTED BY Eng A4K 29
4. empty()
This checks whether the queue is empty.
It returns true if the queue has no elements; otherwise, it returns false.

#include <iostream>
#include <queue>
using namespace std;

int main(){

queue<int> q;
if ([Link]()){
cout << "Queue is empty " << endl;
}
[Link](100);
if (![Link]()){
cout << "Queue is not empty. Front element: " << [Link]() << endl;
}
return 0;
}
Output
Queue is empty
Queue is not empty. Front element: 100
2/25/2026 COLLECTED BY Eng A4K 30
5. Size of queue
The size() function in a queue returns the number of elements currently in the queue.
It helps to determine how many items are stored without modifying the queue.

#include <iostream>
#include <queue>
using namespace std;

int main(){

queue<int> q;
[Link](10);
[Link](5);
cout << "Size of queue: " << [Link]() << endl;
[Link]();
cout << "Size of queue: " << [Link]() << endl;
return 0;
}

Output
Size of queue: 2
Size of queue: 1

2/25/2026 COLLECTED BY Eng A4K 31

Traversal(pseudo traversal)
Since only the front and back element can be accessed in a queue, we cannot directly traverse it.
On the other hand, we can create a copy of the queue, access the front element, and then delete it, and
continue this process until the copied queue is empty, we can effectively traverse all the elements of the
queue.

#include <iostream>
#include <queue> Output
using namespace std; 345
int main(){
queue<int> q;
[Link](3);
[Link](4);
[Link](5);
// Create a copy
queue<int> temp(q);
while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}
return 0;
}

2/25/2026 COLLECTED BY Eng A4K 32

All Member Functions
Following is the list of all member functions of std::queue class in C++:

Functions Description

front() Access the front element of the queue.

back() Access the end element of the queue.

empty() Check whether a queue is empty or not.

size() Returns the number of elements in the queue.

push() Adding an element at the back of the queue.

push_range() Adding multiple elements at the end of queue.

emplace() Add the constructs element in top of the queue.

pop() Delete the front element of the queue.

swap() Swap two queues.

2/25/2026 COLLECTED BY Eng A4K 33

 SUMMERY ON
FIFO vs LIFO
DATA HANDLING IN STACK and QUEUE DS

2/25/2026 COLLECTED BY Eng A4K 34

 FIFO
FIFO is an abbreviation for first in, first out. It is a method for handling data structures where the first
element is processed first and the newest element is processed last.

Real life example:

2/25/2026 COLLECTED BY Eng A4K 35

In this example, following things are to be considered:

There is a ticket counter where people come, take tickets and go.
People enter a line (queue) to get to the Ticket Counter in an organized manner.
The person to enter the queue first, will get the ticket first and leave the queue.
The person entering the queue next will get the ticket after the person in front of him
In this way, the person entering the queue last will the tickets last
Therefore, the First person to enter the queue gets the ticket first and the Last person to enter the queue
gets the ticket last.

Where is FIFO used:

Data Structures
Certain data structures like Queue and other variants of Queue uses FIFO approach for processing
data.
Disk scheduling
Disk controllers can use the FIFO as a disk scheduling algorithm to determine the order in which to
service disk I/O requests.
Communications and networking
Communication network bridges, switches and routers used in computer networks use FIFOs to hold
data packets en route to their next destination.

2/25/2026 COLLECTED BY Eng A4K 36

 LIFO
LIFO is an abbreviation for Last in, first out is same as fist in, last out (FILO). It is a method for handling data
structures where the last element is processed first and the first element is processed last.

Real life example:

2/25/2026 COLLECTED BY Eng A4K 37

 Below is a comparison of FIFO vs. LIFO:
FIFO LIFO
It stands for First-In-First-Out approach in It stands for Last-In-First-Out approach in
programming. programming.

In this, the new element is inserted below the In this, the new element is inserted above the
existing element, So that the oldest element can be existing element, So that the newest element can
at the top and taken out first. be at the top and taken out first.

Therefore, the First element to be entered in this Therefore, the First element to be entered in this
approach, gets out First. approach, gets out Last.

In computing, FIFO approach is used as an In computing, LIFO approach is used as a queuing

operating system algorithm, which gives every theory that refers to the way items are stored in
process CPU time in the order they arrive. types of data structures.

The data structure that implements FIFO is Queue. The data structure that implements LIFO is Stack.

2/25/2026 COLLECTED BY Eng A4K 38