Module 2 – Stack and Queues
Stack
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This
means that the last element added to the stack is the first one to be removed. Imagine a stack
of plates: you can only add or remove plates from the top.
Key characteristics and operations of a stack
• LIFO Principle: The core principle governing a stack's behaviour.
• Push: An operation to add an element to the top of the stack.
• Pop: An operation to remove and return the element from the top of the stack.
• Peek (or Top): An operation to view the top element of the stack without removing it.
• isEmpty: A function to check if the stack contains any elements.
• Size: A function to return the number of elements currently in the stack.
Stacks can be implemented using
Department of CSE P a g e 1 | 25
• Arrays:
A fixed-size array can be used, with a pointer (often called "top") indicating the index of the top
element.
• Linked Lists:
Each element in the stack is a node in a linked list, with new elements added to the head (top)
and removed from the head.
Operations on Stack using Arrays
A stack can be implemented using an array where we maintain:
• An integer array to store elements.
• A variable capacity to represent the maximum size of the stack.
• A variable top to track the index of the top element. Initially, top = -1 to indicate an empty
stack.
Push Operation
Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
• Before pushing the element to the stack, we check if the stack is full.
• If the stack is full (top == capacity-1), then Stack Overflows and we cannot insert the
element to the stack.
• Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is
inserted at top position.
• The elements can be pushed into the stack till we reach the capacity of the stack.
Push Algorithm
Step 1: if top == MAX_SIZE - 1
printf("Stack Overflow! Cannot push %d.\n", element);
Goto Step 4
Step 2: else top++; // Increment top
Step 3: stack[top] = element; // Place the element at the new top
printf("Element %d pushed to stack.\n", element);
Step 4: Stop
Department of CSE P a g e 2 | 25
Pop Operation
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.
• Before popping the element from the stack, we check if the stack is empty.
• If the stack is empty (top == -1), then Stack Underflows and we cannot remove any
element from the stack.
• Otherwise, we store the value at top, decrement the value of top by 1 (top = top – 1) and
return the stored top value.
Pop Algorithm
Step 1: if top == -1
printf("Stack Underflow\n");
return -1; // Indicate underflow
gotoStep 4
Step 2: SET VALUE = STACK[TOP]
Step 3: top--; // Decrement top
Step 4: Stop
Peek Algorithm
Step 1: IF TOP = -1
PRINT "STACK IS EMPTY"
Go to Step 3
Step 2: RETURN STACK[TOP]
Step 3: END
Department of CSE P a g e 3 | 25
Applications of Stacks:
Function calls: Stacks are used to keep track of the return addresses of function calls, allowing
the program to return to the correct location after a function has finished executing.
Recursion: Stacks are used to store the local variables and return addresses of recursive
function calls, allowing the program to keep track of the current state of the recursion.
Expression evaluation: Stacks are used to evaluate expressions in postfix notation (Reverse
Polish Notation).
Syntax parsing: Stacks are used to check the validity of syntax in programming languages and
other formal languages.
Memory management: Stacks are used to allocate and manage memory in some operating
systems and programming languages.
Stack Program- Menu Driven
#include<stdio.h>
#include<stdlib.h>
#define size 4
int top=-1,s[size],ele;
void push() {
if(top==size-1){
printf("Stack overflow");
return;}
printf("Enter element to be inserted:");
scanf("%d",&ele);
s[++top]=ele; }
void pop() {
if(top==-1)
printf("Stack underflow");
return;
printf("Popped element is:%d",s[top--]); }
Department of CSE P a g e 4 | 25
void display() {
if(top==-1)
printf("Stack empty");
return;
for(int i=top;i>=0;i--
printf("%d\n",s[i]);
int main() {
int ch;
for(;;)
printf("
\[Link]
\[Link]
\[Link]
\[Link]
\n");
printf("Enter choice:");
scanf("%d",&ch);
switch(ch)
case 1:
push();
break;
case 2:
Department of CSE P a g e 5 | 25
pop();
break;
case 3:
display();
break;
default:
exit(0);
return 0;
Expression Evaluation:
Infix expressions: An infix expression is a mathematical expression where operators are placed
between their operands, such as 𝐴 + 𝐵 or 3 + 4 ∗ 5
This is the most common notation for humans, but it requires computers to follow operator
precedence rules (like PEMDAS/BODMAS) and handle parentheses to evaluate it correctly.
Postfix Expression: A postfix expression, also known as Reverse Polish Notation (RPN), is a
mathematical notation where the operator follows its operands. It is often used in computers
because it can be evaluated efficiently using a stack without the need for parentheses. For
example, the infix expression "5 + 2" is written as "52 +" in postfix notation
How it Works:
• Operators follow operands: In a postfix expression, operators are written after the
values they operate on.
• No parentheses needed: Parentheses are not required because the order of operations
is determined by the position of the operators.
• Evaluation with a stack: To evaluate a postfix expression, you read it from left to right.
• If a value (operand) is encountered, push it onto a stack.
• If an operator is encountered, pop the top two operands from the stack, perform
the operation, and push the result back onto the stack.
Department of CSE P a g e 6 | 25
• Final result: When you reach the end of the expression, the final result will be the single
value remaining on the stack.
Example:
Postfix Expression Evaluation
Initialize an empty stack .
Scan the expression: from left to right, one token at a time.
If the token is an operand: (a number), push it onto the stack.
If the token is an operator: (+, -, \*, /):
Department of CSE P a g e 7 | 25
• Pop the top two operands from the stack. The first one popped is the second operand
(e.g., in 𝑎 − 𝑏, 𝑎 is popped first, then
• Perform the operation:
𝑜𝑝𝑒𝑟𝑎𝑛𝑑2 operator 𝑜𝑝𝑒𝑟𝑎𝑛𝑑1
𝑜𝑝𝑒𝑟𝑎𝑛𝑑2 operator 𝑜𝑝𝑒𝑟𝑎𝑛𝑑1
• Push the result back onto the stack.
Repeat: until the end of the expression is reached.
The final result: is the only value left on the stack
Recursion in C
Recursion is a method where a function calls itself to solve a problem by breaking it down into
smaller, identical subproblems. This continues until a "base case" is reached, a condition that
stops the function from calling itself, which is essential to prevent an infinite loop. It's used in
programming, particularly for data structures like trees and for algorithms, as it can lead to
more elegant and readable code
Department of CSE P a g e 8 | 25
How it works
• Recursion helps in logic building. Recursive thinking helps in solving complex problems
by breaking them into smaller subproblems.
• Recursive solutions work as a a basis for Dynamic Programming and Divide and
Conquer algorithms.
• Certain problems can be solved quite easily using recursion like Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.
Factorial of a Number
The factorial of a number n (where n >= 0) is the product of all positive integers from 1 to n. To
compute the factorial recursively, we calculate the factorial of n by using the factorial of (n-1).
The base case for the recursive function is when n = 0, in which case we return 1.
Department of CSE P a g e 9 | 25
#include <stdio.h>
int fact(int n)
// Base Condition
if (n == 0)
return 1;
return n * fact(n - 1);
int main() {
printf("Factorial of 5 : %d\n", fact(5));
return 0;
Towers of Hanoi
Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C) and N disks.
Initially, all the disks are stacked in decreasing value of diameter i.e., the smallest disk is placed
on the top and they are on rod A. The objective of the puzzle is to move the entire stack to
another rod (here considered C), obeying the following simple rules:
• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.
Follow the steps below to solve the problem:
• Create a function towerOfHanoi where pass the N (current number of
disk), from_rod, to_rod, aux_rod.
• Make a function call for N - 1 th disk.
• Then print the current the disk along with from_rod and to_rod
• Again make a function call for N - 1 th disk.
Department of CSE P a g e 10 | 25
//Program for Towers of Hanoi
#include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 0) {
return;
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
// Driver code
int main() {
int N = 3;
// A, B and C are names of rods
towerOfHanoi(N, 'A', 'C', 'B');
return 0;
Department of CSE P a g e 11 | 25
Output:
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
Fibonacci Series
The Fibonacci series is a sequence where each number is the sum of the two preceding ones,
typically starting with 0 And 1. The sequence begins 0,1,1,2,3,5,8,13, . ..
and continues infinitely. The mathematical formula is represented as below
Department of CSE P a g e 12 | 25
//Program for Fibonacci Series using recursion
#include <stdio.h>
// Recursive function to calculate the nth Fibonacci number
int fibonacci(int n) {
// Base cases
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
// Recursive case: sum of the two preceding numbers
else {
return (fibonacci(n - 1) + fibonacci(n - 2));
}
}
int main() {
int n, i;
printf("Enter the number of terms for the Fibonacci series: ");
scanf("%d", &n);
printf("Fibonacci Series: ");
// Loop to print the first 'n' Fibonacci numbers
for (i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
printf("\n");
return 0;
}
Department of CSE P a g e 13 | 25
Linear Queues
"Queues" can refer to a line of people waiting for a service or, in computer science, a linear data
structure that follows the First-In, First-Out (FIFO) principle. In this data structure, elements are
added at one end (the rear) and removed from the other (the front), similar to a waiting line. This
is used in many applications, such as managing tasks in an operating system or handling print
jobs.
A data structure: An ordered collection of items where the first item to be added is the first to
be removed (FIFO).
• Enqueue: The operation of adding an element to the rear (back) of the queue.
• Dequeue: The operation of removing an element from the front (head) of the queue.
• Examples:
o Print queues: A list of documents waiting to be printed.
o Task scheduling: An operating system uses queues to manage and schedule
processes.
o Breadth-First Search (BFS): An algorithm that uses a queue to explore nodes in
a graph level by level.
Key characteristics and operations:
• FIFO Principle: Elements are added at the "rear" (or "back") and removed from the
"front."
• Enqueue: The operation of adding an element to the rear of the queue.
• Dequeue: The operation of removing an element from the front of the queue.
Department of CSE P a g e 14 | 25
• Peek/Front: An operation to view the element at the front of the queue without removing
it.
• isEmpty: A function to check if the queue contains any elements.
• isFull: A function to check if the queue has reached its maximum capacity (if
implemented with a fixed-size array).
• Implementation: Queues can be implemented using either arrays or linked lists in C
Algorithm to insert item thru REAR( linear/Single queue using Arrays)
Algorithm ENQUEUE(QUEUE, FRONT, REAR, MAX_SIZE, ITEM)
1. IF REAR == MAX_SIZE - 1 THEN
PRINT "OVERFLOW: Queue is full."
RETURN
2. IF FRONT == -1 THEN
SET FRONT = 0
SET REAR = 0
3. ELSE
SET REAR = REAR + 1
4. SET QUEUE[REAR] = ITEM
5. RETURN
Algorithm to delete an item thru REAR( linear/Single queue using
Arrays)
Step 1: If front = Null then print “UNDERFLOW” and return
Step 2: Set item = Queue[front]
Step 3: If front = rear then Set front = Null and rear = Null Else if front = N then set front = 1 Else
Set front = front + 1 End if
Step 4; stop
Disadvantages of a linear queue
• Wasted space: After elements are removed, the space at the front of the array becomes
unused. The queue is considered full once the rear reaches the last position, preventing
new insertions even though there is available space at the front.
• Fixed size: In its common array-based implementation, a linear queue has a fixed size.
This can limit its use if you don't know the maximum number of elements beforehand.
Department of CSE P a g e 15 | 25
• Inefficient memory usage: The combination of fixed size and wasted space at the front
makes linear queues inefficient for memory usage, especially when dealing with a large
number of elements that are frequently added and removed.
• Potential for overflow: A linear queue can overflow and be unable to accept new items
even when the total number of elements is less than the array's capacity, because
the rear has reached the end of the array
Circular Queue
A Circular Queue is also known as a Ring Buffer which overcomes the limitations of a Linear
Queue by connecting the end of the queue back to the beginning, forming a circle. This circular
structure ensures that once the rear reaches the end, it can wrap around and use any available
space at the front of the queue. Like a Linear Queue, elements are added at the rear and
removed from the front, but the key difference lies in the efficient reuse of space.
Department of CSE P a g e 16 | 25
Operations of Circular Queue
It contains two types of operations in the circular queue:
• Insertion (Enqueue): The Enqueue operation adds an element to the rear of the queue.
• Deletion (Dequeue): The Dequeue operation removes an element from the front of the
queue.
Advantages of Circular Queue
Here are the advantages of the circular queue:
• Efficient space utilization, as the queue reuses empty spaces from removed elements.
• Prevents the queue from becoming full in advance.
• Better suited for scenarios where continuous insertion and deletion are needed.
Key Differences Between Linear Queue and Circular Queue
Department of CSE P a g e 17 | 25
Why is the Circular Queue more efficient than a Linear Queue?
The Circular Queue is more efficient because it avoids wasting space. As elements are removed
from the front, the rear pointer can move back to the front of the queue and reuse that space,
leading to better memory usage.
Can a Circular Queue have an overflow condition?
Yes, a Circular Queue can have an overflow condition, which occurs when the queue is full, and
the rear pointer is equal to the front pointer. This indicates that no more elements can be added.
//Program to implement Circular Queue – Menu Driven
#include<stdio.h>
#include<stdlib.h>
#define qs 4
int front=-1,rear=-1,i;
int q[qs];
void addq()
int elem;
printf("Enter element to be entered:");
scanf("%d",&elem);
if ((rear+1)%qs==front)
printf("Queue overflow\n");
return;
if (front==-1 && rear==-1)
front=0;
rear=0;
Department of CSE P a g e 18 | 25
}
else
rear=(rear+1)%qs;
q[rear]=elem;
void deleteq()
if (front==-1 && rear==-1)
printf("Queue underflow\n");
return;
else if(front ==rear)
printf("Element is:%d\n",q[front]);
front=-1;
rear=-1;
else
printf("Element is:%d\n",q[front]);
front=(front+1)%qs;
void display()
Department of CSE P a g e 19 | 25
if (front==-1 && rear==-1)
printf("Queue empty\n");
return;
else
printf("Elements are:\n");
for( i=front;i!=rear;)
printf("%d\n",q[i]);
i=(i+1)%qs;
printf("%d\n",q[i]);
void main()
int ch;
for(;;)
printf("[Link]\[Link]\[Link]\[Link]\n");
printf("Enter choice:");
scanf("%d",&ch);
switch(ch)
case 1:
addq();
Department of CSE P a g e 20 | 25
break;
case 2:
deleteq();
break;
case 3:
display();
break;
default:
printf("Exited");
exit(0);
Department of CSE P a g e 21 | 25
Priority Queue
A priority queue is a type of queue where each element is associated with a priority value, and
elements are served based on their priority rather than their insertion order.
• Elements with higher priority are retrieved or removed before those with lower priority.
Department of CSE P a g e 22 | 25
• When a new item is added, it is inserted according to its priority.
• Assigning Priority Value
• Generally, the value of the element itself is considered for assigning
the priority. For example,
• The element with the highest value is considered the highest priority
element. However, in other cases, we can assume the element with
the lowest value as the highest priority element.
• We can also set priorities according to our needs.
Applications of Priority Queue in Data Structure
When to use Priority Queues
Prefer priority queues when your application wants to provide preference to certain tasks. Also,
use priority queues when you have limited resources shared by multiple tasks.
Realtime Applications
• CPU Scheduling & Interrupt Handling – Operating systems use priority queues to
execute high-priority tasks first. So, the interrupt requests are enqueued with high
priority.
• Load Balancing is another application of priority queues. This helps to distribute the
load based on priorities.
• Huffman Coding – A data compression algorithm that requires a priority queue to work.
Department of CSE P a g e 23 | 25
Double -Ended Queue.
Deque or Double Ended Queue is a generalized version of Queue data structure that allows
insert and delete at both ends.
• Deque can act as both Stack and Queue
• It is useful in many problems where we need to have a subset of all operations also like
insert/remove at front and insert/remove at the end.
• It is typically implemented either using a doubly linked list or circular array.
• It combines the behaviour of both queues (FIFO) and stacks (LIFO).
Types of Deques
1. Input-Restricted Deque
• Insertion allowed only at one end (usually rear)
• Deletion allowed at both ends
2. Output-Restricted Deque
• Deletion allowed only at one end (usually front)
• Insertion allowed at both ends
Department of CSE P a g e 24 | 25
Real-World Examples / Applications
• Undo/Redo functionality (insert/delete from both ends)
• Browser history
• Job scheduling
• Palindrome checking (using both ends)
• Sliding window problems in algorithms (e.g., max/min in window)
Department of CSE P a g e 25 | 25