Unit 2: Stacks and queues
Data Structures notes · PTU syllabus (BSIT302/BSBC302)
On this page
Unit summary
Stacks and queues control the order in which data is processed. This unit covers the basics of stacks and queues, recursion, Polish notation, circular queues and priority queues.
After this unit you can
- Implement stacks and their operations
- Explain recursion using the stack
- Convert and evaluate Polish notation
- Implement queues, circular queues and priority queues
PTU syllabus topics
- Basics of stacks and queues
- recursion
- Polish notation
- circular queues
- priority queues
Order
LIFO: last in, first out
FIFO: first in, first out
Operations
push, pop
enqueue, dequeue
Access point
One end (top)
Two ends (front and rear)
Uses
Recursion, undo, expression evaluation
Printing, scheduling, buffering
Topic 1
Stacks: 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
Recursion
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.
Topic 4
Polish notation and infix-to-postfix conversion
- 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 5
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 6
Queues: definition and representation
A queue is a linear data structure that follows FIFO (First In, First Out). Insertion (enqueue) happens at the REAR; deletion (dequeue) happens at the FRONT.
- Array representation: QUEUE[MAX] with FRONT and REAR (both −1 when empty).
- Linked representation: a linked list with pointers to the front and rear nodes; insert at the rear, delete from the front.
Principle
LIFO
FIFO
Insertion
At TOP (PUSH)
At REAR (enqueue)
Deletion
At TOP (POP)
At FRONT (dequeue)
Example
Undo history
Printer jobs
Topic 7
Circular queue
A circular queue connects the last position back to the first, so freed spaces are reused. Positions move with modulo arithmetic:
- REAR = (REAR + 1) mod MAX, FRONT = (FRONT + 1) mod MAX
- Full when (REAR + 1) mod MAX = FRONT; empty when FRONT = −1.
Example
With MAX = 5, after inserting 5 items and deleting 2, a simple queue says it is full, but a circular queue can store 2 more by wrapping REAR to positions 0 and 1.
Topic 8
Priority queues and deques
- Deque (double-ended queue): insertion and deletion at both ends. Input-restricted deque: insert at one end only; output-restricted deque: delete at one end only.
- Priority queue: each element has a priority; the highest-priority element is removed first, and equal priorities follow FIFO. It can be implemented with an ordered list, multiple queues (one per priority) or a heap.
Simple queue
FIFO, insert at rear, delete at front
Circular queue
Reuses freed space with wrap-around
Deque
Insert and delete at both ends
Priority queue
Highest priority served first
Key terms
- Stack
- LIFO linear structure
- Queue
- FIFO linear structure
- Postfix notation
- Operators after operands (reverse Polish)
- Circular queue
- Queue whose last position connects to the first
- Priority queue
- Queue served by priority
Quick revision
- Stack: PUSH, POP, PEEK; overflow and underflow.
- Recursion uses the run-time stack; base case.
- Infix, prefix, postfix; conversion with a stack; evaluation.
- Queue: enqueue, dequeue; circular queue formulas.
- Priority queue and deque.
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.Distinguish stack and queue.
- Q2.What is stack overflow?
- Q3.Convert A + B × C to postfix.
- Q4.Evaluate the postfix 2 3 4 × +.
- Q5.Why is a circular queue better than a linear queue?
- Q6.What is a priority queue?
Long-answer questions
- Q1.Explain stack operations with algorithms.
- Q2.Explain recursion and the role of the stack.
- Q3.Convert an infix expression to postfix and evaluate it (numerical).
- Q4.Explain circular queues and priority queues.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures, or to ask about studying B.Sc IT at Synetic.