DATA STRUCTURE • BCS301

Unit 2: Stacks
Abstract data type • Push & Pop • Array & Linked-List
Implementations of Stack • Expressions • Recursion

TOP

LIFO 40

Last In → First Out 30

20

10

40 leaves first

Ananjay Kumar Singh

Assistant Professor • Department of Data Science

Galgotias College of Engineering and Technology

START HERE 2

Learning outcomes

By the end of the lecture, students should be able to:

• Explain stack as an ADT and apply LIFO correctly.

• Implement push, pop, peek, isEmpty and isFull using arrays and linked nodes in C.

• Use stacks to understand infix, prefix and postfix notation and evaluate postfix expressions.

• Explain recursion using base case, recursive case and the call stack.

• Solve problems with recursive and iterative binary search, Fibonacci and Tower of Hanoi.

• Compare tradeoffs in clarity, time, memory and stack-overflow risk.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
ROADMAP 3

What we will cover

Stack fundamentals Implementations

01 02
ADT, LIFO and primitive operations Array and linked-list stacks in C

Expressions Evaluation
03 04
Infix, prefix, postfix and conversion Step-by-step postfix evaluation

Recursion Problem solving

05 06
Principles, call stack, tail recursion Binary search, Fibonacci and Tower of Hanoi

Trade-offs
07
When iteration or recursion is preferable

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
FUNDAMENTALS 4

Stack as an Abstract Data Type

• ADT means what operations do, not how PUBLIC OPERATIONS

data is stored.
push(x) insert x at top
• LIFO the most recently inserted item is
removed first.
pop() remove and return top
• Top the only end through which normal stack
insertion and deletion occur.
peek() read top without removing

isEmpty() test whether stack has no items

isFull() test capacity for fixed array

size() number of stored items

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
FUNDAMENTALS 5

LIFO: one picture tells the rule

TOP
If we push 10, then 20, then 30, the next pop returns 30.
30

Push 10 Push 20 Push 30 Pop → 30

TOP TOP TOP TOP 20

10 20 30 20
10
10 20 10

10

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PRIMITIVE OPERATIONS 6

Push and Pop

PUSH(x) POP()

1 Check overflow (array stack).

1 Check underflow (empty stack).

2 Read the item at TOP.

2 Move TOP one position upward.

3 Move TOP one position downward.

3 Store x at TOP.
TOP
4 Return the saved item.

30

20 Example: pop() returns 30

10

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RUNNING EXAMPLE 7

Trace the stack after every operation

Start push(10) push(20) push(30) pop() → 30 push(40)

TOP TOP TOP TOP TOP TOP

10 20 30 20 40
10 20 10 20
→ → → 10 → → 10

Key idea: every operation changes only the TOP; arbitrary middle access is not a stack operation.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
IMPLEMENTATION 8

Array-based stack in C

// C IMPLEMENTATION
#include <stdio.h> How TOP works
#define MAX 100

typedef struct { top = -1 empty

int data[MAX];
int top;
} Stack; push(10) → top = 0
void init(Stack *s) { s->top = -1; }
push(20) → top = 1
void push(Stack *s, int x) {
if (s->top == MAX - 1) {
printf("Overflow\n"); return; pop() → returns 20
}
s->data[++s->top] = x;
}
Fixed capacity: MAX elements
int pop(Stack *s) {
if (s->top == -1) {
printf("Underflow\n"); return -1;
} push / pop / peek: O(1)
return s->data[s->top--];
}

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
IMPLEMENTATION 9

Array stack: helpers and edge cases

//HELPER FUNCTIONS
• Overflow push is attempted when top == MAX - 1.
int peek(Stack *s) {
if (s->top == -1) return -1;
return s->data[s->top]; • Underflow pop or peek is attempted when top ==
-1.
}
• Complexity push, pop and peek are O(1).
int isEmpty(Stack *s) {
return s->top == -1;
}
• Memory O(MAX) reserved, even if only a few items
are used.
int isFull(Stack *s) {
return s->top == MAX - 1;
}

→ : What should TOP contain after push(5), push(8), pop()?

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
IMPLEMENTATION 10

Linked-List stack in C
// POINTER-BASED IMPLEMENTATION
#include <stdlib.h>
Top node changes
typedef struct Node {
int data;
struct Node *next;
} Node; 20
30
typedef struct {
Node *top;
} Stack;

void init(Stack *s) { s->top = NULL; } 20 10

void push(Stack *s, int x) {

Node *n = malloc(sizeof *n);
if (n == NULL) return;
n->data = x; 10 NULL
n->next = s->top;
s->top = n;
}

int pop(Stack *s) {

if (s->top == NULL) return -1; top → 30 → 20 → 10 → NULL
Node *t = s->top;
int x = t->data;
s->top = t->next;
free(t);
return x;
}

DATA STRUCTURE • BCS301 • Unit 2: Stacks

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology
RUNNING EXAMPLE 11

Linked-List stack: push and pop

Push inserts at the front; pop removes the front. Both are O(1).

Before push(30) pop() → 30

top top top

10 NULL 30 10 10 20

20 10 10 NULL 20 NULL

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
IMPLEMENTATION 12

Array vs Linked-List stack

Feature Array stack Linked-List stack

Storage Contiguous array Heap-allocated nodes

Capacity Fixed / bounded Grows until memory is exhausted

Overflow At MAX capacity malloc failure

Memory overhead Low Extra pointer per node

push / pop O(1) O(1)

Implementation Simpler More pointer management

Best fit Known / bounded size Variable size

Both provide the same stack ADT; only the storage strategy changes.
Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
APPLICATION 13

Infix, prefix and postfix expressions

INFIX PREFIX POSTFIX

(A + B) * C *+ABC AB+C*

operator between operands operator before operands operator after operands

Why use postfix?

• Parentheses are unnecessary during evaluation.

• Operator precedence is already encoded in the order.

• A stack can evaluate it with a simple left-to-right scan.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
APPLICATION 14

Infix → postfix: precedence rules

The stack temporarily holds operators while operands go directly to the output.

Priority Operator Associativity

• Operand send directly to output.

High ^ Right-to-left
• ( push onto operator stack.
Medium * / Left-to-right
• ) pop until ( is removed.
Low + - Left-to-right

• Operator pop operators of higher precedence; for equal

precedence, respect associativity.

Example: A + B * C → ABC*+ because * has higher precedence than +

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RUNNING EXAMPLE 15

Infix → postfix, step by step

Example: (A + B) * C
Token Output Operator stack

( (

A A (

+ A (+

B AB (+

) AB+

* AB+ *

C AB+C *

end AB+C*

Final postfix: AB+C* Important cue: ask yourself why + waits behind (

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
APPLICATION 16

Evaluate postfix expressions with a stack

Example: 5 6 2 + *

Token Action Stack after

action

5 push 5 [5]

6 push 6 [5, 6]

2 push 2 [5, 6, 2]

+ pop 2, 6 → 8; push 8 [5, 8]

* pop 8, 5 → 40; push 40 [40]

Result = 40

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
IMPLEMENTATION 17

Postfix evaluation in C

// SINGLE-DIGIT OPERANDS
• Important-→ this compact example
int evaluatePostfix(const char *exp) { accepts single-digit operands.
Stack s; init(&s);

for (int i = 0; exp[i] != '\0'; i++) { • For 25 3 + tokenize the expression instead
if (isdigit((unsigned char)exp[i])) { of reading one character at a time.
push(&s, exp[i] - '0');
} else {
int b = pop(&s); • Operator order for subtraction/division, first
int a = pop(&s); pop is b and second pop is a; compute a op b.
switch (exp[i]) {
case '+': push(&s, a + b); break;
case '-': push(&s, a - b); break; Complexity O(n) time and O(n) auxiliary
•
case '*': push(&s, a * b); break; stack space.
case '/': push(&s, a / b); break;
}
}
}
return pop(&s);
}

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
APPLICATION 18

Prefix expressions: the matching idea

Prefix is also stack-friendly. Scan from right to left.

Example: * + 2 3 4 • Prefix operator comes before operands.

4 push
• Evaluation scan right-to-left; operand → push;
operator → pop two, compute, push.
3 push
• Postfix scan left-to-right with the same stack
pattern.
2 push

• Takeaway prefix and postfix remove the need to

+ 2+3=5 manage parentheses during evaluation.

* 5×4=20
Both notations are useful applications of the stack ADT.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RECURSION 19

Principles of recursion

• Base case the simplest case with a direct answer.

Factorial example

• Recursive case solve a smaller version of the same

problem. int fact(int n)

• Progress each call must move toward the base case. {

if (n <= 1) return 1;

• Call stack each active call gets its own stack frame. return n * fact(n - 1);
}

fact(4) → 4×fact(3) → 4×3×fact(2) → 24

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RECURSION 20

Call stack: factorial(4)

Calls are pushed; returns happen in reverse order.

TOP
Unwinding

1
fact(4) 4 × 6 = 24

fact(3) 3×2=6

fact(2) 2×1=2

24

fact(1) return 1

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RECURSION 21

Tail recursion

• Definition the recursive call is the final operation of //TAIL CALL //Rec. CALL
the function. long long factTail (int n, long long acc)

• Accumulator carries the partial result so no work int fact(int n)

{
remains after the recursive call.
if (n <= 1) return acc;
{
• Optimization some compilers can transform tail calls, if (n <= 1) return 1;
but C does not guarantee tail-call optimization. return factTail(n - 1, n * acc);
}
• Practical point tail recursion can often be rewritten return n * fact(n - 1);
directly as a loop. // factTail (5, 1) → 120 }

factTail(5,1) → factTail(4,5) → … → 120

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RECURSION 22

Removing recursion

“Removal” means replacing recursive control flow with a non-recursive approach.

1 Direct iteration Replace the recursive relation with a loop.

2 Explicit stack Store pending states yourself when recursion has hidden state.

3 Different algorithm Choose an iterative algorithm when one exists.

4 Tail-call rewrite Convert tail recursion to a loop; optimization is compiler-dependent.

Note: memorization improves a recursive algorithm; it does not by itself remove recursion.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PROBLEM SOLVING 23

Binary search —> recursive

Precondition: the array must be sorted.

//RECURSIVE IMPLEMENTATION IN C
Search 70
int binarySearchRec(int a[], int low, int high, int key)
{
if (low > high) return -1; 10 20 30

int mid = low + (high - low) / 2;

40 50 60
if (a[mid] == key) return mid;

if (a[mid] > key) 70 80 90

return binarySearchRec(a, low, mid - 1, key);

return binarySearchRec(a, mid + 1, high, key); 50 → go right → 70 ✓

}
Time O(log n) • Space O(log n)

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PROBLEM SOLVING 24

Binary search — iterative

//ITERATIVE IMPLEMENTATION IN C
• Same search time O(log n).
int binarySearchIter(int a[], int n, int key)
{
int low = 0, high = n – 1; • Less auxiliary memory O(1) instead of O(log n)
call-stack space.
while (low <= high) • Practical choice often preferred for simple binary
{ search in C.
int mid = low + (high - low) / 2;

if (a[mid] == key) return mid; low ≤ high → inspect mid → discard half

if (a[mid] > key) high = mid – 1;

else low = mid + 1;

}
return -1;
}

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
COMPARISON 25

Binary search: recursion vs iteration

Aspect Recursive Iterative

Time O(log n) O(log n)

Auxiliary space O(log n) call stack O(1)

Code idea Smaller subproblem via call Loop with low/high

When useful Elegant recursive structure Memory-efficient implementation

Same algorithmic idea; different control flow.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PROBLEM SOLVING 26

Fibonacci —> naive recursion

// FIB. IN RECURSIVE C
Repeated work in fib(5)
int fibRec(int n)
fib(5)
{
if (n <= 1) return n;
fib(4) fib(3)
return fibRec(n - 1) + fibRec(n - 2);
}
fib(3) fib(2) fib(2) fib(1)

Time O(2^n) • Space O(n)

Repeated sub-problems make

naive recursion inefficient.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PROBLEM SOLVING 27

Fibonacci —> iteration and memorization

//FIB. ITERATIVE C
Two better choices

int fibIter(int n)
Iteration O(n) time • O(1) space
{
if (n <= 1) return n;
int a = 0, b = 1; Memorization O(n) time • O(n) space
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b; b = c; Memorization keeps recursive structure while
} caching fib(k).
return b;
}
0 1 1 2 3 5 8 13 …

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PROBLEM SOLVING 28

Tower of Hanoi

Goal: move n disks from A to C using B.

Rules

• Move one disk at a time.

• Never place a larger disk on

a smaller disk.
• Use the auxiliary peg to
expose the next disk.

A B C

Recurrence: T(n) = 2T(n−1) + 1 Minimum moves = 2ⁿ − 1

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
PROBLEM SOLVING 29

Tower of Hanoi: recursive algorithm

//RECURSIVE ToH IN C
For n = 3
void hanoi(int n, char src, char aux, char dest)
{ 1. A → C

if (n == 1) 2. A → B
{
3. C → B
printf("Move disk 1 from %c to %c\n", src, dest);
return; 4. A → C
}
5. B → A
hanoi(n - 1, src, dest, aux);
6. B → C
printf("Move disk %d from %c to %c\n", n, src, dest);
7. A → C

hanoi(n - 1, aux, src, dest);

} 7 moves = 2³ − 1

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
TRADE-OFFS 30

Iteration vs recursion

Decision factor Recursion Iteration

Clarity Often concise for recursive structures Often straightforward for loops

Auxiliary memory Call-stack frames may grow Usually constant extra state

Call overhead Present for each recursive call No recursive call overhead

Overflow risk Deep recursion can overflow the call stack No recursion-depth risk

Natural fit Trees, divide-and-conquer, backtracking Simple scans, counters, performance-critical loops

Best question Is the problem naturally recursive? Can a loop express it more simply?

Neither is universally better: choose based on structure, memory, depth and clarity.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
DECISION GUIDE 31

When should you choose which?

Choose recursion when… Choose iteration when…

✓ the problem naturally breaks into smaller copies of ✓ a loop expresses the same logic clearly
itself

✓ the recursive structure improves readability ✓ memory is tight

✓ depth is bounded or carefully controlled ✓ recursion depth could become large

✓ backtracking / tree traversal is the natural model ✓ performance and predictable memory matter

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
RECAP 32

Key takeaways

• Stack ADT LIFO with push, pop, peek and state-check operations.

• Implementations Array = fixed capacity; linked = dynamic heap nodes.

• Expressions Infix needs precedence/parentheses; prefix and postfix encode order.

• Postfix evaluation scan left-to-right; operands push; operators pop two, compute, push.

• Recursion needs a base case, progress toward it and uses the call stack.

• Examples Binary search: O(log n); Fibonacci: iteration/memorization improve naive recursion; Hanoi: naturally recursive, 2ⁿ−1
moves.

• Trade-off recursion can improve structure; iteration usually reduces call-stack memory.

Remember: the right control structure is the one that makes correctness, cost and intent clear.

Ananjay Kumar Singh • Dept. of Data Science • Galgotias College of Engineering and Technology DATA STRUCTURE • BCS301 • Unit 2: Stacks
THANK YOU

Questions & Discussion

Stack → Expressions → Recursion → Problem solving

STACK EXPR.

LIFO Postfix

RECURSION TRADE-OFFS

Call stack Choose wisely Ananjay Kumar Singh

Assistant Professor • Department of Data Science

DATA STRUCTURE • BCS301 • Unit 2: Stacks