Module 2: Stack and Queue

1. STACK AND ITS IMPLEMENTATION

1. What is Stack in Data Structure?

A stack is a linear data structure that follows the LIFO principle, meaning Last In,
First Out.
This means that the last element added (pushed) to the stack is the first one to be
removed (popped).
Real-life Example:
• A pile of plates: You add plates on top and remove the top one first.
• Browser back button: Stores the history in a stack and goes back step by step.
3. Representation of Stack
Stacks can be represented in two ways:
a) Using Arrays:
• A fixed-size stack using a linear array.
• A top pointer tracks the top of the stack.
b) Using Linked List:
• Dynamic size; nodes are linked.
• The top points to the latest pushed node.
4. Basic Stack Operations
Operation Description
push(x) Add element x to the top
pop() Remove and return the top element
peek() or top() Return the top element without removing
isEmpty() Check if stack is empty
isFull() (only for array-based) Check if stack is full

Push Operation on Stack

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
Algorithm for Push Operation:
Algorithm:
Algorithm PUSH(stack[], top, MAX, item):
1. if top = = MAX - 1:
2. print "Stack Overflow"
3. else:
4. top ← top + 1
5. stack[top] ← item
Step-by-step Explanation:
1. We check whether the stack is full by comparing top with MAX - 1.
o MAX is the maximum capacity of the stack.
o If top == MAX - 1, there's no space left to insert a new item.
2. If the stack is full, we print "Stack Overflow". This means we cannot push more
items.
3. Otherwise:
o We increase the top index by 1 (top = top + 1), to point to the next available
space.
 o We place the new item at that position: stack[top] = item.
Algorithm:
Algorithm POP(stack[], top):
1. if top = = -1:
2. print "Stack Underflow"
3. else:
4. item ← stack[top]
5. top ← top - 1
6. return item
Step-by-step Explanation:
1. First, we check if the stack is empty by checking if top == -1.
o If yes, we print "Stack Underflow", which means there is nothing to remove.
2. If the stack is not empty:
o We store the top element in a variable called item.
o Then we reduce top by 1 (top = top - 1) to remove that element.
o Finally, we return the stored item as the popped value.

▶ top() Operation (also called peek())

Algorithm:
Algorithm TOP(stack[], top):
1. if top == -1:
2. print "Stack is Empty"
3. else:
4. return stack[top]
Step-by-step Explanation:
1. We first check if the stack is empty by checking top == -1.
o If true, it means there's no element in the stack. So, we print "Stack is
Empty".
2. If not empty:
o We return the value at the top index of the stack without removing it.
Algorithm:
Algorithm isEmpty(top):
1. if top == -1:
2. return true
3. else:
4. return false
Step-by-step Explanation:
1. A stack is empty when the top index is -1.
2. If top == -1, we return true, meaning stack is empty.
3. If top != -1, we return false, meaning there are elements in the stack.
▶ isFull() Operation
Algorithm:
Algorithm isFull(top, MAX):
1. if top == MAX - 1:
2. return true
3. else:
4. return false
Step-by-step Explanation:
1. A stack is full when the top index is equal to MAX - 1.
o MAX is the maximum size of the array.
2. If top == MAX - 1, we return true, meaning stack is full.
3. Otherwise, we return false.
• Complexity Analysis of Operations on Stack Data Structure:

Operations Time Complexity Space Complexity

push() O(1) O(1)

pop() O(1) O(1)

top() or peek() O(1) O(1)

isEmpty() O(1) O(1)

isFull() O(1) O(1)

Advantages of Stacks
1. Simplicity: Easy to understand and implement for many basic tasks.
2. Efficiency: Push and pop are fast, done in constant time (O(1)).
3. LIFO Behavior: Useful for tasks like function calls and expression evaluation.
4. Memory Efficient: Stores only pushed elements, using limited memory.

Disadvantages of Stacks
1. Limited Access: Only the top element can be accessed directly.
2. Overflow Risk: Exceeding capacity causes data loss.
3. No Random Access: Cannot access elements in any position.
4. Fixed Size: Limited capacity if using arrays or predefined size.

Applications of Stack (in short):

1. Function Call Management:
Tracks active function calls using the call stack.
 2. Expression Evaluation:
Used to evaluate and convert infix, postfix, and prefix expressions.
3. Undo Mechanism:
Helps implement undo/redo operations in editors.
4. Backtracking:
Used in maze solving, puzzles, and recursive algorithms.
5. Browser History Navigation:
Helps manage back/forward navigation.
✅ 6(a). Stack Implementation Using Array (with comments)
#define MAX 100 // Define the maximum size of the stack
int stack[MAX]; // Declare the stack array
int top = -1; // Initialize top to -1 to indicate an empty stack

void push(int x) {
if(top == MAX - 1) { // Check if the stack is full
printf("Stack Overflow"); // Print overflow message
return; // Exit without pushing
}
stack[++top] = x; // Increment top and insert the new element at top position
}

int pop() {
if(top == -1) { // Check if the stack is empty
printf("Stack Underflow"); // Print underflow message
return -1; // Return error value
}
return stack[top--]; // Return the top element and then decrement top
}

✅ 6(b). Stack Implementation Using Linked List (with comments)

struct Node {
int data; // Data field to store the stack element
struct Node* next; // Pointer to the next node
};

struct Node* top = NULL; // Initialize top pointer to NULL (stack is empty)

void push(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
for new node
newNode->data = x; // Assign the value to data field
newNode->next = top; // Point the new node to the current top
top = newNode; // Update top to the new node
}

int pop() {
if(top == NULL) { // Check if the stack is empty
printf("Stack Underflow"); // Print underflow message
 return -1; // Return error value
}
int x = top->data; // Store the top node's data
struct Node* temp = top; // Create a temporary pointer to top node
top = top->next; // Move top to the next node
free(temp); // Free memory of the removed node
return x; // Return the popped value
}

2. QUEUE, CIRCULAR QUEUE, DEQUEUE

1. What is a Queue?
A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle,
where the first element inserted is the first one to be removed, just like a line at a ticket
counter.

3. Types of Queues
1. Simple Queue: Insertion happens at rear and deletion at front (standard FIFO).
2. Circular Queue: Last position connects back to the first to make full use of space (avoids
wasted space in linear queue).
3. Priority Queue: A priority queue is a special queue where the elements are accessed
based on the priority assigned to them. They are of two types:
• Ascending Priority Queue: In Ascending Priority Queue, the elements are arranged
in increasing order of their priority values. Element with smallest priority value is
popped first.
• Descending Priority Queue: In Descending Priority Queue, the elements are arranged
in decreasing order of their priority values. Element with largest priority is popped first
4. Double-Ended Queue (Deque): In a double-ended queue the insertion and deletion
operations, both can be performed from both ends. They are of two types:
• Input Restricted Queue: This is a simple queue. In this type of queue, the input can
be taken from only one end but deletion can be done from any of the ends.
• Output Restricted Queue: This is also a simple queue. In this type of queue, the
input can be taken from both ends but deletion can be done from only one end.
 5. Basic Operations on Queue

Operation Description
Adds an element to the end (rear) of the queue. If the queue is full, an
enqueue(x)
overflow error occurs.
Removes the element from the front of the queue. If the queue is empty, an
dequeue()
underflow error occurs.
peek() / front() Returns the element at the front without removing it.
isEmpty() Returns true if the queue is empty, otherwise false.
isFull() Returns true if the queue is full, otherwise false.
size() Returns the number of elements in the queue.

Complexity Analysis of Operations on Queue

Operations Time Complexity Space Complexity

enqueue O(1) O(1)

Simple array: O(n)

O(1)
dequeue Circular Array: O(1)

front O(1) O(1)

size O(1) O(1)

isEmpty O(1) O(1)

isFull O(1) O(1)

9. Applications of Queue (One-line Description)

1. Job Scheduling in Operating Systems:
Queues manage processes waiting for CPU time in a first-come, first-served manner.
2. Print Queue in Printers:
Print tasks are lined up in a queue and processed in the order they are received.
3. Task Management in Multi-processing:
Queues help coordinate and execute multiple tasks or threads efficiently.
4. Customer Service Queues:
Customers are served in the order they arrive, following the FIFO principle.
5. Data Streaming / Buffer Handling:
Queues temporarily hold incoming data packets before processing them sequentially.
 Advantages of Queue
1. FIFO Order:
Ensures fair processing by serving elements in the order they arrive.
2. Efficient Resource Management:
Useful for managing tasks like CPU scheduling, disk scheduling, and printing.
3. Prevents Overloading:
Helps control data flow in real-time systems like networks or streaming.
4. Supports Multi-threading:
Queues help coordinate tasks between producer and consumer threads.
5. Easy Implementation:
Simple to implement using arrays or linked lists.
Disadvantages of Queue
1. Fixed Size (Array-based):
In static arrays, the queue has limited capacity unless implemented as circular.
2. No Random Access:
You cannot access or modify elements in the middle directly.
3. Shifting Problem (Linear Queue):
Frequent dequeue() operations may waste space if not using circular queue.
4. Slower than Stack for LIFO:
For tasks requiring last-in-first-out, stack is more efficient than queue.

4. Representation of Queue

Queues can be implemented using:

• Arrays (fixed size)
• Linked Lists (dynamic size)

Basic Operations of Queue with Algorithm & Explanation

1. Enqueue(x) – Insert element at rear

Algorithm:
plaintext
CopyEdit
Algorithm ENQUEUE(queue[], front, rear, MAX, x):
1. if rear == MAX - 1:
2. print "Queue Overflow"
3. else if front == -1 and rear == -1:
4. front ← 0
5. rear ← 0
6. queue[rear] ← x
7. else:
8. rear ← rear + 1
9. queue[rear] ← x
Explanation:
• Line 1: Check if the queue is full.
• Line 2: If full, print "Overflow" and exit.
• Line 3: If queue is empty (front and rear are -1), set both to 0.
• Line 4–5: Initialize front and rear pointers.
• Line 6: Insert the first element at index 0.
 • Line 7: Else, move rear to the next position.
• Line 9: Insert the element at new rear.
2. Dequeue() – Remove element from front
Algorithm:
Algorithm DEQUEUE(queue[], front, rear):
1. if front == -1:
2. print "Queue Underflow"
3. else if front == rear:
4. item ← queue[front]
5. front ← rear ← -1
6. return item
7. else:
8. item ← queue[front]
9. front ← front + 1
10. return item
Explanation:
• Line 1: Check if queue is empty.
• Line 2: If yes, print "Underflow".
• Line 3: If only one element is present,
• Line 4: Store that element.
• Line 5: Reset both front and rear to -1.
• Line 6: Return the removed item.
• Line 7: Else, store the front element.
• Line 9: Move front ahead by 1.
• Line 10: Return the dequeued item.
3. Peek() / Front() – View front element without removing
Algorithm:
Algorithm PEEK(queue[], front):
1. if front == -1:
2. print "Queue is Empty"
3. else:
4. return queue[front]
Explanation:
• Line 1: Check if queue is empty.
• Line 2: Print message if empty.
• Line 4: Else, return the frontmost item.
4. isEmpty()
Algorithm:
Algorithm isEmpty(front):
1. if front == -1:
2. return true
3. else:
4. return false
Explanation:
• If front == -1, the queue is empty.
• Return true or false accordingly.
 5. isFull() (for array)
Algorithm:
Algorithm isFull(rear, MAX):
1. if rear == MAX - 1:
2. return true
3. else:
4. return false
Explanation:
• If rear has reached the maximum size, return true for full.
• Otherwise, return false.
6. size() – Return number of elements
Algorithm:
Algorithm size(front, rear):
1. if front == -1:
2. return 0
3. else:
4. return (rear - front + 1)
Explanation:
• If front == -1, the queue is empty.
• Else, size is calculated as (rear - front + 1).

Queue Using Array (C Language)

c
CopyEdit
#include <stdio.h>
#define MAX 100

int queue[MAX]; // Array to store queue elements

int front = -1; // Index of front element
int rear = -1; // Index of rear element

// Enqueue operation
void enqueue(int x) {
if(rear == MAX - 1) { // Check if queue is full
printf("Queue Overflow\n");
return;
}
if(front == -1 && rear == -1) { // First element insertion
front = rear = 0;
} else {
rear++; // Move rear forward
}
queue[rear] = x; // Insert the element at rear
}

// Dequeue operation
int dequeue() {
if(front == -1) { // Check if queue is empty
printf("Queue Underflow\n");
 return -1;
}
int item = queue[front]; // Store the front element
if(front == rear) { // Only one element left
front = rear = -1; // Reset queue
} else {
front++; // Move front forward
}
return item; // Return dequeued item
}

// Peek operation
int peek() {
if(front == -1) { // Check if queue is empty
printf("Queue is Empty\n");
return -1;
}
return queue[front]; // Return front element
}

// isEmpty operation
int isEmpty() {
return front == -1; // True if front is -1
}

// isFull operation
int isFull() {
return rear == MAX - 1; // True if rear reaches max size
}

// size operation
int size() {
if(front == -1) // If queue is empty
return 0;
return rear - front + 1; // Total number of elements
}

Queue Using Linked List (C Language)

c
CopyEdit
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data; // Data of the node
struct Node* next; // Pointer to next node
};

struct Node* front = NULL; // Pointer to front of queue

struct Node* rear = NULL; // Pointer to rear of queue
// Enqueue operation
void enqueue(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
newNode->data = x; // Store data
newNode->next = NULL; // Set next as NULL

if(front == NULL && rear == NULL) { // If queue is empty

front = rear = newNode; // First node becomes front and rear
} else {
rear->next = newNode; // Link new node at rear
rear = newNode; // Update rear
}
}

// Dequeue operation
int dequeue() {
if(front == NULL) { // Check if queue is empty
printf("Queue Underflow\n");
return -1;
}
int x = front->data; // Store front data
struct Node* temp = front; // Temporary pointer to delete front
front = front->next; // Move front to next node
if(front == NULL) rear = NULL; // If queue becomes empty, reset rear
free(temp); // Free memory
return x; // Return dequeued item
}

// Peek operation
int peek() {
if(front == NULL) { // Check if queue is empty
printf("Queue is Empty\n");
return -1;
}
return front->data; // Return front element
}

// isEmpty operation
int isEmpty() {
return front == NULL; // True if front is NULL
}

// size operation
int size() {
int count = 0;
struct Node* temp = front; // Start from front
while(temp != NULL) {
count++; // Count nodes
temp = temp->next; // Move to next
 }
return count; // Return total count
}

Recursion VS Iteration

SR
Recursion Iteration
No.

Terminates when the base case becomes Terminates when the loop condition
1)
true. becomes false.

Logic is built using iterating over

2) Logic is built in terms of smaller problems.
something.

Every recursive call needs extra space in Every iteration does not require any
3)
the stack memory. extra space.

4) Smaller code size. Larger code size.

 What is Recursion?
Recursion is a programming technique where a function calls itself to solve a smaller subproblem of the
original task.
Key Properties:
• Each recursive call has its own execution context (stack frame).
• Base condition is essential to terminate recursion.
• Can be direct (calls itself) or indirect (calls another function that calls it).

Example: Factorial using Recursion

c
CopyEdit
int factorial(int n) {
if (n == 0 || n == 1)
return 1; // Base case
return n * factorial(n - 1); // Recursive call
}

Disadvantages:
• High memory usage due to call stack.
• Slower for large inputs (risk of stack overflow).
• Harder to debug and trace.

Advantages:
• Elegant and clean code for problems with recursive structure (e.g., trees, backtracking).
• Reduces code complexity for divide-and-conquer problems.

What is Iteration?
Iteration refers to repeating a block of code using loops (for, while, do-while) until a condition is met.

Example: Factorial using Iteration

c
CopyEdit
int factorial(int n) {
int result = 1;
for(int i = 1; i <= n; i++) {
result *= i;
}
return result;
}

Advantages:
• Faster and memory-efficient (no stack usage).
• Better for performance in large input cases.

Disadvantages:
• Sometimes more complex logic for tree-based or recursive-like problems.
• Less readable in problems naturally recursive (e.g., DFS, Fibonacci).

When to Use Recursion?

Use recursion when:
• The problem can be broken into smaller subproblems.
• The solution naturally fits tree, graph, or divide-and-conquer structure.
• Problems like:
o Factorial, Fibonacci, Tower of Hanoi
o Tree traversal (Inorder, Preorder, Postorder)
o DFS (Graph traversal), Backtracking (N-Queens, Maze)
 When to Use Iteration?
Use iteration when:
• The task involves repeated execution of a simple task.
• Memory and performance are critical.
• Problems like:
o Sum of array
o Searching/Sorting (linear or binary)
o Simple loops like counting, multiplication, etc.

Recursion is when a function calls itself.

Principles:
- Base Case: Stops recursion
- Recursive Case: Calls itself (Recursion uses the call stack.)
Tail Recursion: Last action is the recursive call.
Tower of Hanoi: Puzzle with 3 rods and disks.
Move all disks from Source to Destination using rules.
- One disk at a time
- Smaller disk on top
Code:
def hanoi(n, source, auxiliary,
destination): if n == 1:
print(f"Move disk 1 from {source} to
{destination}") else:
hanoi(n - 1, source, destination, auxiliary)
print(f"Move disk {n} from {source} to
{destination}") hanoi(n - 1, auxiliary, source,
destination)

Eight Queens Puzzle: Place 8 queens on a chessboard such that none

attack each other. Solved using backtracking.

 1. Tower of Hanoi – Detailed Explanation

What is Tower of Hanoi?

It is a puzzle that involves:
• 3 rods (or pegs): Let’s name them A (source), B (auxiliary/helper), C (destination)
• N disks of different sizes stacked in decreasing order (largest at the bottom) on the
source rod

Goal:
Move all the disks from the source rod (A) to the destination rod (C) using the auxiliary
rod (B), following 3 rules:

Rules:
1. Only one disk can be moved at a time.
2. Only the topmost disk from a rod can be moved.
3. A larger disk can never be placed on top of a smaller disk.

Example: For 3 Disks

Let’s name disks D1 (smallest), D2, D3 (largest)
You need to move all disks from Rod A to Rod C, using Rod B as helper.

Steps:

Move No. Action

1 Move D1 from A → C

2 Move D2 from A → B

3 Move D1 from C → B

4 Move D3 from A → C

5 Move D1 from B → A

6 Move D2 from B → C

7 Move D1 from A → C

All disks are now on rod C, in correct order.

 General Formula:
To move n disks, the minimum number of steps required =
2ⁿ − 1
So:
• 3 disks → 2³ − 1 = 7 moves
• 4 disks → 2⁴ − 1 = 15 moves

Recursive Solution Logic:

To solve Tower of Hanoi recursively:
python
CopyEdit
def tower_of_hanoi(n, source, auxiliary, destination):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
tower_of_hanoi(n-1, source, destination, auxiliary)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n-1, auxiliary, source, destination)
Call it like:
python
CopyEdit
tower_of_hanoi(3, 'A', 'B', 'C')

2. Eight Queen Puzzle – Detailed Explanation

What is it?
The Eight Queen Puzzle is a classic problem in computer science and artificial intelligence.
You have to place 8 queens on an 8×8 chessboard such that:

No two queens can attack each other.

How does a Queen move in chess?

A Queen can move in:
• Any row
• Any column
• Any diagonal
So, if two queens are in the same row, column, or diagonal, they can attack each other.

Goal:
You must place 8 queens, one per row, so that:
• No two queens are in the same row
• No two queens are in the same column
• No two queens are in the same diagonal

Let’s Understand With a Smaller Version: 4×4

We will place 4 queens on a 4×4 board.

One valid solution:

css
CopyEdit
_Q__
___Q
Q___
__Q_
This means:
• Queen 1 is in Row 1, Column 2
• Queen 2 is in Row 2, Column 4
• Queen 3 is in Row 3, Column 1
• Queen 4 is in Row 4, Column 3

No two queens attack each other.

How to Solve (Algorithm):

Use Backtracking – a trial and error method.
Steps:
1. Start from row 0
2. Try to place a queen in each column
3. If it is safe, move to the next row
4. If placing the queen causes a conflict → go back (backtrack) and try a different
column
🔷 1. Tower of Hanoi – Python Code with Comments
python
CopyEdit
# Tower of Hanoi using recursion

def tower_of_hanoi(n, source, auxiliary, destination):

# If there is only one disk, move it directly from source to
destination
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return

# Step 1: Move (n-1) disks from source to auxiliary

tower_of_hanoi(n - 1, source, destination, auxiliary)

# Step 2: Move the remaining (largest) disk from source to destination

print(f"Move disk {n} from {source} to {destination}")

# Step 3: Move the (n-1) disks from auxiliary to destination

tower_of_hanoi(n - 1, auxiliary, source, destination)

# Call the function with 3 disks and rod names A, B, C

tower_of_hanoi(3, 'A', 'B', 'C')

✅ Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

🔷 2. N-Queens (4-Queen version) – Python Code with Comments

python
CopyEdit
# Check if placing a queen at (row, col) is safe
def is_safe(board, row, col, n):
# Check vertically upward (same column)
for i in range(row):
if board[i][col] == 1:
return False

# Check upper-left diagonal

for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i][j] == 1:
return False
 # Check upper-right diagonal
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
if board[i][j] == 1:
return False

return True # Safe to place queen

# Solve the N-Queens problem using backtracking

def solve_n_queens(board, row, n):
# Base case: If all queens are placed, print the solution
if row == n:
print_solution(board, n)
return

# Try placing queen in every column in the current row

for col in range(n):
if is_safe(board, row, col, n):
board[row][col] = 1 # Place the queen
solve_n_queens(board, row + 1, n) # Move to next row
board[row][col] = 0 # Backtrack (remove queen)

# Function to print the board

def print_solution(board, n):
for i in range(n):
row = ""
for j in range(n):
row += "Q " if board[i][j] == 1 else ". "
print(row)
print("\n")

# Main driver code

n = 4 # Change this to 8 for the Eight Queen Puzzle
board = [[0] * n for _ in range(n)] # Create n×n board filled with 0
solve_n_queens(board, 0, n)