Stacks & Queues
Two ADTs that differ in exactly one respect: which end you take from. That single choice changes what an algorithm computes, which is why the same traversal code explores depth-first with one and breadth-first with the other.
- State the contract for a Stack and a Queue.
- Implement both with the right end of a Python list.
- Explain why the naive queue implementation is $O(n)$.
- Recognise which problems call for which.
Some problems need the most recent item, others the oldest. Naming those two disciplines and giving each a tiny interface makes the intent of an algorithm obvious from which one it uses.
The call stack is why a function returns to its caller and why infinite recursion produces a "stack overflow". Print queues, network packet buffers and task schedulers are queues. Undo history is a stack.
Turing described a stack mechanism for subroutine calls in 1946. Making it the standard way to implement function calls was what allowed recursion to exist as a language feature at all.
Stack
A stack is last-in-first-out. The only accessible item is the one
added most recently. Operations: push, pop,
is_empty.
class Stack:
"""A last-in-first-out collection.
Attributes:
_items: the contents, with the top of the stack at the end
"""
_items: list
def __init__(self) -> None:
"""Initialize an empty stack."""
self._items = []
def push(self, item) -> None:
"""Add item to the top of this stack."""
self._items.append(item)
def pop(self):
"""Remove and return the top item of this stack.
Preconditions: this stack is not empty.
>>> s = Stack()
>>> s.push(1)
>>> s.push(2)
>>> s.pop()
2
"""
return self._items.pop()
def is_empty(self) -> bool:
"""Return whether this stack is empty."""
return self._items == []append and pop() are $O(1)$
there.def balanced(text: str) -> bool:
"""Return whether the brackets in text are correctly nested.
>>> balanced('([])')
True
>>> balanced('([)]')
False
"""
pairs = {')': '(', ']': '[', '}': '{'}
s = Stack()
for ch in text:
if ch in '([{':
s.push(ch)
elif ch in pairs:
if s.is_empty() or s.pop() != pairs[ch]:
return False
return s.is_empty()is_empty check matters: without it
'((' would pass.Queue
A queue is first-in-first-out. The only accessible item is the
one added earliest. Operations: enqueue,
dequeue, is_empty.
class Queue:
"""A first-in-first-out collection.
Attributes:
_items: the contents, with the front of the queue at index 0
"""
_items: list
def __init__(self) -> None:
"""Initialize an empty queue."""
self._items = []
def enqueue(self, item) -> None:
"""Add item to the back of this queue."""
self._items.append(item) # O(1)
def dequeue(self):
"""Remove and return the front item of this queue.
Preconditions: this queue is not empty.
>>> q = Queue()
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.dequeue()
1
"""
return self._items.pop(0) # O(n) - shifts everythingcollections.deque, which is $O(1)$ at both ends. Writing it out
by hand is the point here.Why the choice changes the answer
Exploring a structure by taking from a collection and adding neighbours:
def explore(start, use_stack: bool) -> list:
"""Return the nodes reachable from start, in visit order.
With use_stack the exploration is depth-first; otherwise
it is breadth-first.
"""
pending = Stack() if use_stack else Queue()
add = pending.push if use_stack else pending.enqueue
take = pending.pop if use_stack else pending.dequeue
add(start)
seen = []
while not pending.is_empty():
node = take()
if node not in seen:
seen.append(node)
for neighbour in node.neighbours:
add(neighbour)
return seen• Popping from an empty stack or queue. Check the precondition or the
emptiness first.
• Using pop(0) in a loop over a large queue and wondering
why it is slow.
• Putting the stack top at index $0$. Correct but needlessly
$O(n)$.
• Forgetting the final emptiness check in bracket
matching.
• Choosing a stack when the problem wants oldest-first. The code runs and
the answer is wrong.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
Push $1$, $2$, $3$ onto a stack, then pop three times. What comes out?
Answer
A printer serves jobs in the order submitted. Stack or queue?
Answer
Why is the list-based dequeue $O(n)$?
Answer
pop(0)
removes the first element and shifts every remaining one down by one
position.Why does balanced need the final
is_empty()?
Answer
'(((' would return
True.Reverse a string using only a stack.
Solution
def reverse(text: str) -> str:
"""Return text reversed.
>>> reverse('abc')
'cba'
"""
s = Stack()
for ch in text:
s.push(ch)
out = ''
while not s.is_empty():
out = out + s.pop()
return outHow would you build a queue from two stacks?
Solution
Which structure finds the shortest path in an unweighted graph?
Answer
Why is the mechanism behind function calls a stack?
Answer
Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- Stack. LIFO contract, list-based implementation, why the top goes at the end.
- Queue. FIFO contract, and the $O(n)$ dequeue that motivates linked lists.
- Choosing. Which discipline a problem needs, and how the choice changes an algorithm's behaviour.
- Applications. Bracket matching, reversal, and the depth-first versus breadth-first distinction.
The calendar names "abstract data types and data structures for implementing them". Stacks and queues are the first worked examples; check Quercus for the assigned exercises.
Two ADTs, differing only in which end is accessible. That difference determines whether an algorithm goes deep or wide. Unit 4 gives both an implementation where every operation is constant time.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
What separates a stack from a queue?
Guide
Why put the stack top at the end of the list?
Guide
append and pop() at the end are $O(1)$, while
operations at the front are $O(n)$.Which gives depth-first search?
Guide
How can dequeue become $O(1)$?
Guide
collections.deque.