Stack, Queue, Priority Queue - StudyPulse
StudyPulse Logo
Sign Up
Boost Your VCE Scores Today with StudyPulse
8000+ Questions AI Tutor Help
Create Free Account Learn More
Home Subjects Algorithmics (HESS) Stack, queue, priority queue

Stack, Queue, Priority Queue

Algorithmics (HESS)

About these notes

Area of Study

Data modelling with abstract data types

Unit

Unit 3: Algorithmic problem-solving

Join StudyPulse

Sign up for a free account to access more study resources and track your progress.

Create Free Account Learn More
Get started in 60 seconds
StudyPulse

Stack, Queue, Priority Queue

Algorithmics (HESS)
01 May 2026

Stack, Queue, and Priority Queue ADTs

1. Stack ADT

A stack is a collection with LIFO (Last In, First Out) access: the most recently added element is the first to be removed.

Visualisation

Think of a stack of plates: you add plates to the top and remove from the top.

push(3)  →  [1, 2, 3]  ← top
push(5)  →  [1, 2, 3, 5]  ← top
pop()    →  [1, 2, 3]  (5 removed, returned)

Key Operations

Operator Signature Description
empty → Stack Create empty stack
push Stack × Element → Stack Add to top
pop Stack → Stack Remove top
top Stack → Element Peek at top
isEmpty Stack → Boolean Check if empty

Time Complexity

All core operations are $O(1)$.

Applications

  • Function call stack (recursion)
  • Undo/redo in text editors
  • Depth-First Search (DFS)
  • Expression evaluation (infix → postfix)
  • Backtracking algorithms

KEY TAKEAWAY: Whenever a problem requires reversing an order or tracking a nested/recursive structure, consider a Stack.

2. Queue ADT

A queue is a collection with FIFO (First In, First Out) access: the first element added is the first removed.

Visualisation

Think of a queue at a supermarket checkout — customers join at the rear, leave from the front.

enqueue(A) → [A]
enqueue(B) → [A, B]
enqueue(C) → [A, B, C]
dequeue()  → [B, C]  (A removed, returned)

Key Operations

Operator Signature Description
empty → Queue Create empty queue
enqueue Queue × Element → Queue Add to rear
dequeue Queue → Queue Remove from front
front Queue → Element Peek at front
isEmpty Queue → Boolean Check if empty

Time Complexity

All core operations are $O(1)$.

Applications

  • Breadth-First Search (BFS) — the core ADT used in BFS
  • Job scheduling / print queues
  • Network packet buffering
  • Level-order tree traversal

EXAM TIP: BFS requires a queue; DFS uses a stack (or recursion). Knowing which traversal uses which ADT is frequently tested.

3. Priority Queue ADT

A priority queue is a collection where each element has an associated priority, and elements with higher priority are removed first (regardless of insertion order).

Key Operations

Operator Signature Description
empty → PriorityQueue Create empty priority queue
insert PQueue × Element × Priority → PQueue Add with priority
removeMin PQueue → PQueue Remove highest-priority element
min PQueue → Element Peek at highest-priority element
isEmpty PQueue → Boolean Check if empty

Note: “highest priority” is usually the minimum key in min-priority-queue convention.

Time Complexity (heap implementation)

Operation Complexity
insert $O(\log n)$
removeMin $O(\log n)$
min (peek) $O(1)$

Applications

  • Prim’s algorithm (MST) — always processes cheapest available edge
  • Dijkstra’s algorithm — always relaxes lowest-cost vertex
  • A* search — processes nodes by $f(n) = g(n) + h(n)$
  • Hospital triage — patients treated by severity, not arrival order
  • Event-driven simulation

COMMON MISTAKE: A priority queue is NOT a sorted list. Elements are not maintained in sorted order — only the minimum (or maximum) is guaranteed to be accessible efficiently.

Comparison

Property Stack Queue Priority Queue
Access order LIFO FIFO By priority
insert time $O(1)$ $O(1)$ $O(\log n)$
remove time $O(1)$ $O(1)$ $O(\log n)$
Key algorithm use DFS, backtracking BFS Prim’s, Dijkstra’s

Table of Contents