Unit 3: Stacks and recursion
Data Structures-I notes · PTU syllabus (UGCC2506)
On this page
Unit summary
A stack is a list where items are added and removed only at one end, called the top — like a pile of plates. Stacks power function calls, undo, expression evaluation and recursion. This unit covers stack operations and representation, Polish notation, and recursion.
After this unit you can
- Represent a stack using an array and a linked list
- Write PUSH and POP algorithms with overflow and underflow checks
- Convert infix expressions to postfix and evaluate postfix expressions
- Explain recursion and the runtime stack, and solve factorial, GCD, Fibonacci and Towers of Hanoi
PTU syllabus topics
- Definition
- array and linked-list representation
- stack operations
- applications — arithmetic expressions
- Polish notation
- infix-to-postfix conversion
- postfix evaluation
- recursion definition
- recursive notation
- runtime stack
- applications (factorial, GCD, Fibonacci, Towers of Hanoi)
- 1Read A
Operand goes straight to output: A
- 2Read +
Push + on the stack
- 3Read B
Output: A B
- 4Read *
Higher precedence than +, push *
- 5Read C, then pop all
Output: A B C * +
Topic 1
Stack: definition and representation
A stack is a linear data structure that follows LIFO (Last In, First Out): the last element inserted is the first removed. Insertion is PUSH and deletion is POP, both at the TOP.
- Array representation: an array STACK[MAX] and a variable TOP (−1 when empty).
- Linked representation: each push adds a node at the start of a linked list; the list's head is TOP. No overflow until memory runs out.
Topic 2
Stack operations
- 1Check overflow
If TOP = MAX − 1, print "Overflow" and stop
- 2Increase TOP
TOP = TOP + 1
- 3Insert
STACK[TOP] = ITEM
- 1Check underflow
If TOP = −1, print "Underflow" and stop
- 2Take the item
ITEM = STACK[TOP]
- 3Decrease TOP
TOP = TOP − 1
Other operations: PEEK (read the top without removing it), isEmpty and isFull. All are O(1).
Topic 3
Polish notation and infix to postfix
- Infix: operator between operands — A + B
- Prefix (Polish): operator before operands — + A B
- Postfix (Reverse Polish): operator after operands — A B +
Postfix needs no brackets and is easy for a computer to evaluate with a stack.
- 1
Scan left to right
- 2
Operand
Send to output
- 3
Left bracket
Push
- 4
Operator
Pop operators of higher or equal precedence to output, then push it
- 5
Right bracket
Pop to output until the left bracket
- 6
End
Pop all remaining operators
Example
A + B × C → A B C × +, because × has higher precedence than +. (A + B) × C → A B + C ×.
Topic 4
Evaluating a postfix expression
Scan left to right: push operands; when an operator appears, pop two operands (the first popped is the right operand), apply the operator and push the result. The final value on the stack is the answer.
| Symbol | Action | Stack |
|---|---|---|
| 5 | Push | 5 |
| 3 | Push | 5, 3 |
| + | Pop 3 and 5, push 8 | 8 |
| 2 | Push | 8, 2 |
| × | Pop 2 and 8, push 16 | 16 |
So 5 3 + 2 × = 16.
Topic 5
Recursion and the runtime stack
Recursion is when a function calls itself. Each call is pushed onto the runtime (call) stack with its own parameters and local variables; when a call returns, its frame is popped.
Factorial
n! = n × (n − 1)!, with 0! = 1
GCD (Euclid)
GCD(a, b) = GCD(b, a mod b), with GCD(a, 0) = a
Fibonacci
F(n) = F(n − 1) + F(n − 2), with F(0) = 0, F(1) = 1
Towers of Hanoi
Moves = 2ⁿ − 1 for n discs
Towers of Hanoi: move n discs from peg A to peg C using B, never placing a larger disc on a smaller one. Move n − 1 discs from A to B, move the largest from A to C, then move n − 1 discs from B to C.
Exam tip
Recursion is elegant but uses extra stack memory; for Fibonacci, plain recursion is slow (O(2ⁿ)) because it repeats work.
Key terms
- Stack
- A LIFO list where insertion and deletion happen at the top
- Overflow
- Trying to push onto a full stack
- Underflow
- Trying to pop from an empty stack
- Postfix notation
- Writing the operator after its operands
- Runtime stack
- The stack that stores function call frames
Quick revision
- Stack = LIFO; PUSH and POP at TOP; both O(1).
- Overflow when TOP = MAX − 1; underflow when TOP = −1.
- Infix → postfix: operands out, operators via the stack by precedence.
- Postfix evaluation: push operands, pop two for each operator.
- Hanoi needs 2ⁿ − 1 moves.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a stack and its LIFO principle.
- Q2.What are overflow and underflow?
- Q3.Convert A + B × C − D to postfix.
- Q4.Why is postfix notation preferred for evaluation by computers?
- Q5.What is the runtime stack?
- Q6.How many moves does Towers of Hanoi need for 4 discs?
Long-answer questions
- Q1.Write algorithms for PUSH and POP using an array and a linked list.
- Q2.Explain the algorithm to convert an infix expression into postfix with a worked example.
- Q3.Evaluate the postfix expression 6 2 3 + − 3 8 2 / + × using a stack, showing each step.
- Q4.Explain recursion with the Towers of Hanoi problem.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures-I, or to ask about studying BCA at Synetic.