COMP9123 — Data Structures & Algorithms

Week 3: Stacks, Queues & Algorithm Analysis

Week 3 has two teaching jobs. First it sharpens the language of algorithm analysis so you can compare solutions reliably. Then it introduces stacks and queues as restricted ADTs whose power comes from matching the logical shape of real problems.

📈 Why Big-O beats raw timing

📦 Stack = LIFO thinking

📤 Queue = FIFO service

🔍 Balanced-parentheses algorithm

Lecture content from slide 6 onward Recap and admin skipped First ADTs with strict access rules Built for revision

📐 Foundations → 🗺 Mind Map →

Week 3 starts by asking how algorithms scale, then shows why restricted data structures can be more useful than general ones when the access pattern is exactly right.

Why Analyze Algorithms Instead of Just Timing Them?

The lecture begins by slowing down and asking a foundational question: if there are many ways to solve the same problem, how should we compare them fairly?

Execution time is noisy

Raw runtime depends on hardware, memory, compiler choices, programming language, and system load. That makes it a poor theoretical comparison tool.

Input size matters

A method can look fast on tiny examples and then collapse badly at scale. The lecture wants you to focus on how performance changes as \(n\) grows.

Worst case gives guarantees

Worst-case analysis matters because it tells you what performance ceiling you can rely on, even when the input is adversarial or unlucky.

Big-O idea: describe growth rather than exact runtime. That means suppressing machine-specific details and asking how the algorithm scales conceptually.

Professor mindset: when someone says one algorithm is “faster,” ask “for what input size, on what model, and by what kind of bound?” Week 3 is training that reflex.

Quick check

Why does the lecture prefer Big-O to raw execution time as the main comparison language?

Because Big-O gives exact runtime in seconds

Because it focuses on growth with input size and avoids hardware-specific noise

Because it only applies to recursive code

Because it always proves an algorithm is optimal

Growth Classes: Turning Intuition into a Scale

The middle analysis slides use real-world analogies to make the common growth classes feel concrete instead of symbolic.

Complexity	Lecture analogy	What behaviour it captures
\(O(1)\)	Direct access by known shelf number	Work stays effectively fixed as input grows.
\(O(\log n)\)	Finding a word in a physical dictionary	Each step shrinks the remaining search space dramatically.
\(O(n)\)	Scanning supermarket items one by one	Each input item causes another similar unit of work.
\(O(n^2)\)	Checking for duplicate transactions pairwise	Nested comparison structure makes work grow like pairs.
\(O(2^n)\)	Generating all possible passwords or feature subsets	The number of possibilities explodes combinatorially.

Time complexity

Measures how execution time grows with input size. This is the main language used when comparing algorithms on the slides.

Space complexity

Measures how much extra memory an algorithm or data structure needs as input grows. Week 3 explicitly treats this as a separate design cost.

The important habit: do not memorise symbols in isolation. Tie each class to a code shape or process shape: scan, halve, nest, or enumerate choices.

Stack ADT: LIFO Structure and the Meaning of “Top”

A stack is a restricted List ADT where both insertion and removal happen at the same end. That restriction is exactly what gives stacks their clarity.

Stack rule: last in, first out. The most recently pushed item is the next one that can be popped or observed with top().

Operation	Meaning	What changes
`push(e)`	Add a new top element.	The stack becomes one element taller.
`pop()`	Remove and return the current top.	The previous element becomes the new top.
`top()`	Inspect the current top without removing it.	The stack itself stays unchanged.

Operation sequence from the slides

Starting from stack [6, 9, 3] with 3 on top:

push(5)  -> [6, 9, 3, 5]
pop()    -> [6, 9, 3]
top()    -> 3
push(8)  -> [6, 9, 3, 8]
isEmpty()-> false
pop()    -> [6, 9, 3]
top()    -> 3

Why restricted ADTs matter: stacks are less general than lists, but that restriction matches many real problems perfectly. The lecture is making the point that “less general” can mean “more useful.”

Method Stacks: Why Recursion Already Uses a Stack

One of the most important applications in the lecture is invisible during everyday coding: the runtime itself uses a stack to manage active method calls.

Call frame

Each method call pushes a frame containing local variables, control state, and the return position.

Return behaviour

When a method finishes, the most recently called unfinished method is the one that resumes first. That is pure LIFO behaviour.

Why recursion works

Recursive calls do not need special magic. They rely on the same stack discipline as any other nested call sequence.

Translation: even if your code never declares a stack object, the runtime environment may still be using a stack on your behalf.

Balanced Parentheses: a Stack Matching the Shape of Nesting

This is the canonical Week 3 algorithmic application. The key insight is that the next closing bracket must match the most recent unmatched opener.

Core idea: push opening delimiters as they appear. When a closing delimiter arrives, compare it with the top of the stack. If it mismatches or the stack is empty, the expression is unbalanced.

Algorithm sketch

create empty stack S
for each character c in expression:
    if c is an opening bracket:
        push c onto S
    else if c is a closing bracket:
        if S is empty:
            return false
        open = pop from S
        if open does not match c:
            return false
return S is empty

Balanced example

( w * [ x + y ] / z ) works because every closer matches the most recent unmatched opener, and the stack ends empty.

Unbalanced example

{ [ x + y ) ] - z } fails because ) tries to close [. The top-of-stack mismatch immediately exposes the error.

1

Nesting means the last opener you saw is the first one that must be matched before earlier openers can close.

2

That “last unresolved item must be handled first” rule is exactly LIFO.

3

If the process ends with leftover openers on the stack, the expression still has unresolved structure and is therefore unbalanced.

Memory hook: nesting depth is stack depth.

Quick check

When the algorithm reads a closing bracket, which opener is the only valid one to compare against first?

The earliest opener in the expression

Any opener of the same type

The most recent unmatched opener on the stack

The smallest bracket by ASCII code

Queue ADT: FIFO Service, Scheduling, and Buffering

Queues reverse the access rule from stacks. The oldest waiting item leaves first, which is why queues appear wherever order-of-arrival matters.

Queue rule: first in, first out. New items join at the rear with enqueue, and the oldest item leaves from the front with dequeue.

ADT	Access rule	Typical examples
Stack	LIFO	Undo history, recursion, delimiter matching
Queue	FIFO	Waiting lines, packet buffering, shared-resource scheduling

Queue sequence from the slides

Starting from queue [6, 9, 3] with 6 at the front:

enqueue(5) -> [6, 9, 3, 5]
dequeue()  -> [9, 3, 5]
first()    -> 9
enqueue(8) -> [9, 3, 5, 8]
size()     -> 4
dequeue()  -> [3, 5, 8]
first()    -> 3

Forward bridge: queues become the engine of breadth-first processing later in the course because layer-by-layer exploration is naturally FIFO.

Tutorial 3 and the Code Bundle: From Basic ADTs to Better Design

The tutorial pushes beyond definitions. It asks you to compare growth rates, reason about the best linked-list implementations of stacks and queues, and then improve an ADT by storing the right extra information.

Tutorial problem cluster	What it is really testing
Ordering asymptotic growth classes	Whether you can compare \( \sqrt{n}, n, n \log n, n^2, 2^n, n!, n^n \) without confusing syntax for growth.
Stack / queue on singly linked lists	Whether you know which end to treat as front or top so operations stay \(O(1)\).
`getAverage()` for a queue	Whether you can augment an ADT with extra maintained state instead of recomputing from scratch.
Queue using two stacks	Whether you can simulate one ADT with another and still reason about operation costs carefully.
Palindrome and parentheses problems	Whether you can connect structural properties of data to algorithm design choices.

Why linked-list skeletons are bundled here

The included files [Node.py](/Users/chinaharry/Desktop/Workspace/Usyd%20Mastery/9123DataStructureAlgo/chapters/chapter3/Codes/Node.py), [single_ll.py](/Users/chinaharry/Desktop/Workspace/Usyd%20Mastery/9123DataStructureAlgo/chapters/chapter3/Codes/single_ll.py), and [DoublyLinkedList.py](/Users/chinaharry/Desktop/Workspace/Usyd%20Mastery/9123DataStructureAlgo/chapters/chapter3/Codes/DoublyLinkedList.py) remind you that stacks and queues are often implemented on top of simpler list primitives rather than as magical standalone structures.

What the queue-augmentation question is teaching

Do not rescan the queue every time getAverage() is called. Store a running sum and update it during enqueue / dequeue so the new operation becomes cheap while the original operations remain cheap too.

Great Week 3 answer style: specify the data you store, explain how each operation updates it, and then justify the running time from those updates.

Quick check

What extra state is the cleanest way to support getAverage() in \(O(1)\) time for a queue?

A sorted copy of all queue elements

A running sum together with the queue size

A binary search tree of elements only

No extra information at all

Chapter Quizzes

Use the embedded checks above while reading, then switch to the Quiz Hub and flashcards for mixed recall across Week 3.

Best rhythm: test each concept right after learning it, then finish with mixed practice so stacks, queues, and analysis language start to feel automatic.

Open Quiz Hub Flashcards