Unit 2 of 4 · B.Sc IT Sem 3

Unit 2: Stacks and queues

Data Structures notes · PTU syllabus (BSIT302/BSBC302)

5 min read8 topics10 exam questions
On this page
  1. Unit summary
  2. Stacks: definition and representation
  3. Stack operations
  4. Recursion
  5. Polish notation and infix-to-postfix conversion
  6. Evaluating a postfix expression
  7. Queues: definition and representation
  8. Circular queue
  9. Priority queues and deques
  10. Key terms
  11. Quick revision
  12. Important questions

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
1

Topic 1

Stacks: definition and representation

A stack can be represented using an array (with a TOP index and a fixed size) or a linked list (dynamic size, with TOP pointing to the first node). 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.

Example

Everyday stacks: a pile of plates, the browser back button and the undo feature in a word processor all work LIFO — the most recent item is the first one removed.

Exam tip

Learn both conditions: overflow (TOP = MAX − 1) and underflow (TOP = −1).

2

Topic 2

Stack operations

The two main operations are PUSH (insert at the top) and POP (remove from the top), plus PEEK (view the top element without removing it).

ProcessPUSH(ITEM) using an array
  1. 1Check overflow

    If TOP = MAX − 1, print "Overflow" and stop

  2. 2Increase TOP

    TOP = TOP + 1

  3. 3Insert

    STACK[TOP] = ITEM

ProcessPOP() using an array
  1. 1Check underflow

    If TOP = −1, print "Underflow" and stop

  2. 2Take the item

    ITEM = STACK[TOP]

  3. 3Decrease TOP

    TOP = TOP − 1

Other operations: PEEK (read the top without removing it), isEmpty and isFull. All are O(1).

Example

Tracing a stack (MAX = 3): PUSH 10, PUSH 20, POP (returns 20), PUSH 30, PUSH 40, PUSH 50 → overflow, because the stack already holds 10, 30 and 40.

Exam tip

Always check overflow before PUSH and underflow before POP.

3

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.

Key formulasClassic recursive definitions
  • 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.

Example

Tracing the call stack for fact(3): fact(3) is pushed, it calls fact(2), which calls fact(1). fact(1) returns 1, fact(2) returns 2 × 1 = 2, and fact(3) returns 3 × 2 = 6 as each call is popped off the stack.

Exam tip

Recursion needs a base case; each call uses stack space, so very deep recursion can cause stack overflow.

4

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.

ProcessInfix to postfix using a stack
  1. 1

    Scan left to right

  2. 2

    Operand

    Send to output

  3. 3

    Left bracket

    Push

  4. 4

    Operator

    Pop operators of higher or equal precedence to output, then push it

  5. 5

    Right bracket

    Pop to output until the left bracket

  6. 6

    End

    Pop all remaining operators

Example

A + B × C → A B C × +, because × has higher precedence than +. (A + B) × C → A B + C ×.

5

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.

SymbolActionStack
5Push5
3Push5, 3
+Pop 3 and 5, push 88
2Push8, 2
×Pop 2 and 8, push 1616

So 5 3 + 2 × = 16.

Example

*Evaluating 5 3 + 8 2 − :** push 5, push 3; '+' pops 3 and 5, pushes 8; push 8, push 2; '−' pops 2 and 8, pushes 6; '*' pops 6 and 8, pushes 48. The result is 48.

Exam tip

For binary operators, the second popped value is the left operand: A − B means pop B first, then A.

6

Topic 6

Queues: definition and representation

In an array queue, REAR marks where the next element is inserted and FRONT where the next is deleted. A simple array queue wastes space after deletions, which is solved by a circular queue, where REAR wraps around: REAR = (REAR + 1) mod MAX. 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.
ComparisonStack vs queue
Stack
Queue

Principle

LIFO

FIFO

Insertion

At TOP (PUSH)

At REAR (enqueue)

Deletion

At TOP (POP)

At FRONT (dequeue)

Example

Undo history

Printer jobs

Example

Circular queue (MAX = 5): after inserting 10, 20, 30, 40, 50 and deleting 10 and 20, a simple queue would say 'full'. A circular queue wraps REAR to index 0 and inserts 60 into the freed space.

Exam tip

Circular queue full condition: (REAR + 1) mod MAX = FRONT.

7

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.

8

Topic 8

Priority queues and deques

In a priority queue, each element has a priority, and the element with the highest priority is removed first (ties are served FIFO).

  • 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.
ClassificationTypes of queue
Queues
  • 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

Example

Priority queue in a hospital: patients are seen by urgency, not arrival time — a critical patient who arrives later is treated before a patient with a minor injury who arrived earlier.

Exam tip

Priority queues are usually implemented with a heap for efficiency.

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

  1. Q1.Distinguish stack and queue.
  2. Q2.What is stack overflow?
  3. Q3.Convert A + B × C to postfix.
  4. Q4.Evaluate the postfix 2 3 4 × +.
  5. Q5.Why is a circular queue better than a linear queue?
  6. Q6.What is a priority queue?

Long-answer questions

  1. Q1.Explain stack operations with algorithms.
  2. Q2.Explain recursion and the role of the stack.
  3. Q3.Convert an infix expression to postfix and evaluate it (numerical).
  4. 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.

WhatsApp us