Subject Name: Data Structures

Subject Code: BE03000081

Semester: 3 (Bachelor of Engineering – GTU)
Unit: Section 2 – LINEAR DATA STRUCTURE Stack
Prepared by: Prof. RR Keshwala
Academic Year: 2025–2026

Stack: Stack-Definitions & Concepts, Operations On Stacks, Applications of Stacks, Polish Expression,
Reverse Polish Expression And Their Compilation, Recursion, Tower of Hanoi

🔷 What is a Stack?
A Stack is a type of linear data structure that allows operations only at one end — referred to as the
top of the stack. It organizes data in a Last In, First Out (LIFO) manner.
🔸 LIFO Meaning:
 The last element inserted (pushed) into the stack will be the first one to be removed
(popped).
 Think of stacking trays: You can only remove the top tray. You can’t directly remove one in
the middle or bottom.

🔍 Why Use a Stack?

Stacks are widely used in both real-life systems and computer science because:
 They help manage function calls in programming (call stack).
 They are ideal for undo/redo, backtracking, and expression evaluation.
 They simplify problems that require reversing, tracking nested structures, or recursion.

🧠 Key Properties of Stack

Property Description
LIFO Last-in element is the first-out
Top Pointer Keeps track of the top-most element
Access Limit Access allowed only from the top
Overflow Happens if you try to push into a full stack (in array-based stack)
Underflow Happens if you try to pop from an empty stack

🔸 Stack Structure Visually:

Let’s say we push three elements:
Push(10)
Push(20)
Push(30)
📦 The stack now looks like:
| 30 | ← Top (last inserted, first out)
| 20 |
| 10 |
Now we call Pop():
 It removes 30, the top element
New state:
| 20 | ← Now Top
| 10 |
✅ Real-Life Analogies of Stack

Here are real-world examples to help visualize stack behavior:

1️⃣ Stack of Plates / Dishes
 In a cafeteria, plates are stacked.
 When someone takes a plate, they take the topmost one.
 You cannot remove a plate from the middle.
📌 Behavior: LIFO
Last plate placed → first to be taken

2️⃣ Books Piled on a Table

 Books are added one on top of another.
 To get a book at the bottom, you must first remove the ones above it.
📌 Behavior: LIFO

3️⃣ Undo Feature in Text Editors

 Every time you type, an action is pushed into the undo stack.
 When you press “Undo,” the last typed action is reversed.
📌 Behavior: LIFO
Last operation → first to be undone

4️⃣ Call Stack in Programming

 When functions are called, their state is saved in a stack.
 The most recent function call is returned first when complete.
📌 Behavior: LIFO

5️⃣ Browser History (Back Button)

 When you visit pages, URLs are stored in a stack.
 Clicking "Back" returns you to the last visited page.
📌 Behavior: LIFO

📚 Summary:
Feature Stack
Structure Type Linear
Principle LIFO (Last In First Out)
Access Point Only from Top
Examples Undo, Back button, Call Stack, Plates, Books

✅ 1. Characteristics / Features of a Stack

No Characteristic Description
 .
1. LIFO Principle Stack works on Last In First Out logic: the most recently added
element is removed first.
2. One-End Access All operations (insertion, deletion, access) happen at one end —
called the Top.
3. Top Pointer Stack maintains a special pointer called Top that always points to
the most recent element.
4. Restricted Operations You can’t insert/remove elements from arbitrary positions — only
the top element is accessible.
5. Linear Structure Stack is a linear structure where elements are arranged in
sequence.
6. Overflow & - Overflow occurs when you try to push into a full stack.
Underflow - Underflow occurs when you pop from an empty stack.
7. Efficient Memory Especially when implemented using a dynamic structure like a
Usage linked list.
8. Recursion and Stacks are fundamental to supporting recursive calls and
Backtracking backtracking algorithms.
9. Used in Expression Used in conversion (infix-postfix) and evaluation (postfix) of
Handling expressions.
10. Support for Abstract Stack is a classic example of an Abstract Data Type (ADT) —
ADT implementation can vary (array/linked list).

✅ 2. Terminology Used in Stacks

Term Description
Stack A linear data structure that follows the LIFO principle.
Top The pointer/index referring to the current last element (or where the next
will be pushed).
Push() Operation to insert an element at the top of the stack.
Pop() Operation to remove and return the topmost element.
Peek() / Top() Returns the top element without removing it.
isEmpty() Returns true if the stack has no elements.
isFull() Used in array-based stacks — returns true if the stack has reached its
maximum capacity.
Overflow Condition when trying to push onto a full stack (array version).
Underflow Condition when trying to pop from an empty stack.

💡 Simple Visual Example:

Imagine this stack:
Push(10)
Push(20)
Push(30)
Stack looks like:
| 30 | ← Top
| 20 |
| 10 |
 Top = 2 (if 0-based index)
 Peek() returns 30
  Pop() removes 30, Top now points to 20

✅ Summary Points:
 Stack is a restricted access structure with operations only at one end.
 Most operations are O(1) in time complexity.
 Very useful for language parsing, algorithm design, and system-level programming.

📘 2. Stack Operations (With Algorithmic Steps)

All stack operations act on one end: the top of the stack.

✅ List of Basic Stack Operations:

Operation Purpose
Push Insert an element on the top
Pop Remove and return top element
Peek View top element without removing
isEmpty Check if the stack is empty
isFull Check if the stack is full (for array)

✅ 1. Push Operation
🔸 Goal: Insert a new element at the top of the stack.

 If Top == MAX - 1, the stack is full ⇒ Overflow

🔹 Conditions:

 Else, increment top and insert the element

📌 Algorithm:
Push(Stack, value)
1. if (top == MAX - 1)
2. print "Stack Overflow"
3. else
4. top = top + 1
5. Stack[top] = value

✅ 2. Pop Operation
🔸 Goal: Remove the topmost element and return it.

 If Top == -1, the stack is empty ⇒ Underflow

🔹 Conditions:

 Else, return and remove the top element

📌 Algorithm:
Pop(Stack)
1. if (top == -1)
2. print "Stack Underflow"
3. else
4. value = Stack[top]
5. top = top - 1
6. return value

✅ 3. Peek / Top Operation

🔸 Goal: Return the top element without removing it.
📌 Algorithm:
Peek(Stack)
1. if (top == -1)
2. print "Stack is Empty"
3. else
4. return Stack[top]

✅ 4. isEmpty Operation
🔸 Goal: Check whether the stack is empty.
📌 Algorithm:
isEmpty()
1. return (top == -1)

✅ 5. isFull Operation
🔸 Goal: Check whether the stack is full (array implementation only).
📌 Algorithm:
isFull()
1. return (top == MAX - 1)

✅ Example Trace:
Let’s say:
MAX = 5
Stack initially: [ ] → top = -1
Operations:
Push(10) → Stack: [10] → top = 0
Push(20) → Stack: [10, 20] → top = 1
Peek() → returns 20
Pop() → Stack: [10] → top = 0
isEmpty() → false

🧠 Summary Table
Operation Time Complexity Space Complexity
Push O(1) O(1)
Pop O(1) O(1)
Peek O(1) O(1)
isEmpty O(1) O(1)
isFull O(1) O(1)

📘 Stack Implementation Using Array (C Program)

✅ Features:
 Fixed size array (MAX)
 Stack operations: push, pop, peek, isEmpty, isFull
 Menu-driven interface
✅ 📄 C Code:
#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1;
// Function to check if stack is empty
int isEmpty() {
return (top == -1);
}
// Function to check if stack is full
int isFull() {
return (top == MAX - 1);
}
// Function to push an element onto the stack
void push(int value) {
if (isFull()) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
top++;
stack[top] = value;
printf("%d pushed to stack.\n", value);
}
}

// Function to pop the top element

int pop() {
if (isEmpty()) {
printf("Stack Underflow! Cannot pop.\n");
return -1;
} else {
int val = stack[top];
top--;
printf("Popped element: %d\n", val);
return val;
}
}
// Function to peek at top element
int peek() {
if (isEmpty()) {
printf("Stack is empty.\n");
return -1;
} else {
return stack[top];
}
}
// Function to display stack elements
void display() {
if (isEmpty()) {
printf("Stack is empty.\n");
} else {
printf("Stack elements (Top to Bottom):\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
}
}

// Menu-driven main
int main() {
int choice, value;

while (1) {
printf("\n--- Stack Operations ---\n");
printf("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
printf("Top element is: %d\n", peek());
break;
case 4:
display();
break;
case 5:
return 0;
default:
printf("Invalid choice!\n");
}
}
return 0;
}

🧪 Sample Output:
--- Stack Operations ---
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to push: 10
10 pushed to stack.

Enter your choice: 1

Enter value to push: 20
20 pushed to stack.

Enter your choice: 3

Top element is: 20

Enter your choice: 2

Popped element: 20

Enter your choice: 4

Stack elements (Top to Bottom):
10

✅ Key Notes:
 Stack size is fixed (MAX)
 Overflow occurs if top == MAX - 1
 Underflow if top == -1
 Array index starts from 0
 top tracks the position of the last inserted element

📘 Applications of Stack (With Real-Life and Programming Use Cases)

Stacks are not just theoretical—they are used everywhere in programming, systems, and logic
building.

✅ 1. Expression Conversion
One of the most common uses of stack is converting infix expressions (like A + B) into:
 Postfix (Reverse Polish Notation): A B +
 Prefix (Polish Notation): + A B
Stacks help manage operator precedence and parentheses efficiently.

✅ 2. Postfix Expression Evaluation

Once an expression is in postfix form, you can evaluate it easily using a stack.
Example:
Postfix: 2 3 4 * +
Evaluate using stack step-by-step.
✅ 3. Balanced Parentheses Check
Stacks are ideal for checking if a string like [(a+b) + {c*d}] has properly matched and nested brackets
(( ), { }, [ ]).
📌 Works well because of LIFO: the last opening bracket must be matched first.
✅ 4. Function Call Management (Call Stack)
In recursion or nested function calls:
 Each function call is pushed onto the call stack
 On return, the function is popped
💡 The entire concept of recursion is built on stack logic.
✅ 5. Undo/Redo Operations
Text editors, drawing apps, and IDEs use stacks to:
 Push every user action
 On undo, pop the last action and reverse it
 Redo actions can be stored in a second stack
✅ 6. Backtracking Algorithms
Used in:
 Maze solving
 Pathfinding (DFS)
 Puzzle solvers (e.g., Sudoku)
Backtracking uses stack to store decisions and backtrack when needed.
✅ 7. Tower of Hanoi
A classic recursive problem where disks are moved between rods.
 Recursive calls form a call stack.
 Stack logic helps track current and pending moves.
✅ 8. String Reversal
Push each character into stack → pop and print → reversed string.
✅ 9. Browser History Navigation
 Push URLs as you browse
 Pop to go back to previous pages (Back button)
✅ 10. Memory Management
Stacks are used in stack-based memory allocation (local variables, function calls, etc.)

✅ Summary Table:
Application Area Role of Stack
Expression Conversion Manage operator precedence
Expression Evaluation Compute result of postfix/prefix
Parenthesis Matching Validate nested symbols
Function Call Stack Track function execution
Undo/Redo Operations Manage user action history
Backtracking Algorithms Explore, revert decisions
Tower of Hanoi Recursive simulation
String Reversal In-place reversal using LIFO
Browser Navigation Maintain navigation flow
Memory Management System-level stack frames

📘 Recursion – Detailed Explanation

🔷 What is Recursion?
Recursion is a programming technique where a function calls itself directly or indirectly to solve a
problem.
✅ “A recursive function solves a problem by breaking it down into smaller subproblems, each of the
same type.”

📌 Basic Structure of a Recursive Function:

void recursiveFunction() {
if (base_condition) {
// Stop the recursion
return;
} else {
// Smaller problem
recursiveFunction();
}
}
✅ Key Terms in Recursion:
Term Meaning
Recursive The condition where the function calls itself
Case
Base Case The stopping condition that ends recursion
Call Stack A stack that keeps track of function calls during recursion

🔄 How Recursion Works Internally

Every time a function calls itself:
 The current state is pushed onto the call stack
 When the base case is met, function calls start returning (popping) from the stack
So recursion uses a stack implicitly, even if you don’t declare one.

✅ Simple Example: Factorial of a Number (n!)

int factorial(int n) {
if (n == 0) return 1; // Base case
else return n * factorial(n-1); // Recursive call
}
🧪 Example: factorial(4)

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
=4*3*2*1*1
= 24
Each call is added to the call stack, and then returns in LIFO order.

✅ Real-Life Analogies
 Analogy How it relates to recursion
Russian Dolls A doll inside a doll inside a doll...
Folding clothes Finish the last one first, then go back
Google Maps path tracing Goes deeper until destination, then returns back through path
Function calls in programs Stack of function calls, return one-by-one

✅ Types of Recursion
Type Example
Direct A function calls itself directly
Indirect A → B → A pattern of calls
Tail Recursion Recursive call is the last operation in function
Non-Tail Recursion There’s more to compute after the recursive call

✅ Advantages of Recursion
 Makes code simpler and elegant (especially for problems like tree traversal, backtracking,
etc.)
 Reduces the need for manual stack management
 Naturally matches divide-and-conquer problems (e.g., Merge Sort)

❗ Disadvantages of Recursion
 Memory usage increases due to the call stack
 If base case is missing or wrong, it leads to infinite recursion → stack overflow
 Can be slower than iteration for simple problems

✅ When to Use Recursion

Use recursion when:
 Problem can be broken into smaller subproblems
 You know the base case
 The recursive relationship is easy to define
Examples:
 Factorial, Fibonacci
 Tower of Hanoi
 Tree Traversal (Inorder, Preorder, Postorder)
 Graph algorithms (DFS)
 Expression evaluation
 Backtracking (Sudoku, N-Queens)

🧠 Summary:
Feature Recursion
Needs base case? ✅ Yes
Uses call stack? ✅ Yes
Elegant for? Divide-and-conquer, tree problems, backtracking
Can be replaced by? Iteration (in many cases)
✅ C Program: Factorial Using Recursion

#include <stdio.h>

// Recursive function to calculate factorial

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

int main() {
int num;

// Input from user

printf("Enter a number to calculate factorial: ");
scanf("%d", &num);

if (num < 0) {
printf("Factorial is not defined for negative numbers.\n");
} else {
int result = factorial(num);
printf("Factorial of %d is: %d\n", num, result);
}
return 0;
}

🔍 Sample Output:
Enter a number to calculate factorial: 5
Factorial of 5 is: 120

📌 Key Notes:
 Base case: When n == 0 or n == 1, return 1.
 Recursive call: n * factorial(n-1) reduces the problem until it hits the base case.
 This implementation uses the call stack implicitly to hold intermediate computations.

📘 Difference Between Recursion and Iteration

Feature Recursion Iteration
Definition A function calls itself Repeats a block of code using
loops
Flow control Uses function calls and call stack Uses looping constructs like for,
while
 Base/Exit Needs a base case to stop recursion Needs a loop termination
condition condition
Memory usage More (due to call stack) Less (memory-efficient)
Speed Often slower due to repeated function Generally faster
calls
Simplicity Elegant for complex problems (trees, Better for simple counting
backtracking) problems
Overhead Function call overhead present No function overhead
Example Factorial using f(n) = n*f(n-1) for(i=1;i<=n;i++) result *= i;

🔔 Conclusion:
 Recursion is great when the problem has a recursive structure (trees, backtracking, divide-
and-conquer).
 Iteration is better for tasks with clear repetition and performance concerns.

✅ Now: Recursive Program Example – Fibonacci Series

📌 What is Fibonacci Series?

It’s a sequence where:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
So:

F(0), F(1), F(2), F(3), F(4), F(5), ...

= 0, 1, 1, 2, 3, 5, ...

📄 C Program: Print First N Fibonacci Numbers Using Recursion

#include <stdio.h>

// Recursive function to return nth Fibonacci number

int fibonacci(int n) {
if (n == 0)
return 0; // Base case
else if (n == 1)
return 1; // Base case
else
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}

int main() {
int n;

printf("Enter number of terms: ");

scanf("%d", &n);
 printf("Fibonacci series (first %d terms):\n", n);
for (int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}

printf("\n");
return 0;
}

✅ Sample Output:
Enter number of terms: 6
Fibonacci series (first 6 terms):
011235

📌 Explanation:
 Base cases: fibonacci(0) = 0, fibonacci(1) = 1
 Recursive call: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
Each call breaks the problem into smaller subproblems, until it reaches the base case.

📘 Tower of Hanoi

🧩 What is the Tower of Hanoi?

The Tower of Hanoi is a mathematical puzzle where you are given:
 3 rods: Source (A), Auxiliary (B), Destination (C)
 n disks: All disks are different sizes, initially placed on rod A in decreasing size (largest at
bottom)

🎯 Objective:
Move all n disks from Source (A) to Destination (C) using Auxiliary (B), following 3 rules:
✅ Rules:
1. Only one disk can be moved at a time.
2. You can only move the top disk from a stack.
3. No disk may be placed on top of a smaller disk.

🧠 Logic & Recursion Insight

 To move n disks from A to C:
1. Move n-1 disks from A → B (using C)
2. Move disk n from A → C (direct move)
3. Move n-1 disks from B → C (using A)
This recursive pattern continues until n = 1 (base case).

🧾 Algorithm for Tower of Hanoi:

TOH(n, Source, Auxiliary, Destination)
1. If n == 1:
- Move disk 1 from Source to Destination
2. Else:
 a. TOH(n-1, Source, Destination, Auxiliary)
b. Move disk n from Source to Destination
c. TOH(n-1, Auxiliary, Source, Destination)

✅ C Program: Tower of Hanoi Using Recursion

#include <stdio.h>

void towerOfHanoi(int n, char from_rod, char aux_rod, char to_rod) {

if (n == 1) {
printf("Move disk 1 from %c to %c\n", from_rod, to_rod);
return;
}

towerOfHanoi(n - 1, from_rod, to_rod, aux_rod); // Step 1

printf("Move disk %d from %c to %c\n", n, from_rod, to_rod); // Step 2
towerOfHanoi(n - 1, aux_rod, from_rod, to_rod); // Step 3
}

int main() {
int n;
printf("Enter number of disks: ");
scanf("%d", &n);

printf("Steps to solve Tower of Hanoi for %d disks:\n", n);

towerOfHanoi(n, 'A', 'B', 'C'); // A=source, B=auxiliary, C=destination

return 0;
}

📌 Example Output (for n = 3):

Enter number of disks: 3
Steps to solve Tower of Hanoi for 3 disks:
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

🔢 Number of Moves:
For n disks, the minimum number of moves required is:
📍 Formula:
Moves = 2ⁿ − 1
🔸 Example:
 For n = 3 → 2³ − 1 = 7 moves
 For n = 4 → 15 moves
 For n = 5 → 31 moves
🔄 How Stack is Used Internally
Each recursive call is pushed onto the call stack.
As the base case is reached (n = 1), the function starts returning and executing the moves.
This simulates the exact behavior of a manual stack.

🧠 Applications of Tower of Hanoi

 Recursive algorithm training
 Understanding call stack behavior
 Disk scheduling simulations
 Problem-solving in AI (planning, backtracking)