C. Designing Modular Programs · Modular and Object-Oriented Design

Abstract Data Types: Stacks, Queues and Dictionaries

C1.1 C1.2 C1.4About 75 minutes

Learning goals

I can explain what an abstract data type is and separate its interface from its implementation.
I can implement and use a stack (LIFO) and a queue (FIFO) as encapsulated classes.
I can describe the dictionary (map) ADT and use two interchangeable implementations of it.
I can choose the right ADT for a problem (undo, bracket matching, waiting lines, look-ups).

Words to know

abstract data type (ADT)
A data type defined by the operations it supports and how they behave, not by how the data is stored.

interface
The set of operations an ADT or class offers to other code, with what each one does.

implementation
The actual code and storage that make the interface work; it can be replaced without changing client code.

stack
A LIFO (last in, first out) ADT with push, pop, peek and is_empty.

queue
A FIFO (first in, first out) ADT with enqueue, dequeue and is_empty.

dictionary (map)
An ADT that stores key-value pairs and looks values up by key, with operations like put, get and remove.

underflow
Trying to pop or dequeue from an empty stack or queue; a well-designed ADT raises an error.

deque
A double-ended queue (from collections) that adds and removes quickly at both ends.

client code
Any code that uses a class or module through its interface.

Same behaviour, different insides

When you press Undo in a text editor, the most recent change disappears first. When you print three documents, the first one you sent prints first. When you look up a word in a dictionary, you go straight to the word, not through every page. These three behaviours (last-in first-out, first-in first-out, look up by key) are so common that computer scientists gave them names: stack, queue and dictionary (or map).

Each one is an abstract data type (ADT): a type defined by what operations it offers and how they behave, not by how the data is stored inside. Expectation C1.1 names exactly these three as examples, and asks you to decompose problems into ADTs as well as classes.

Interface and implementation

An ADT has two sides:

The interface: the list of operations and what each one promises. A stack promises that pop() returns the item most recently pushed.
The implementation: the class that keeps that promise, using a list, a linked chain of objects, an array, or anything else.

Client code must use only the interface. Then the implementation can be swapped for a faster one without changing a single line of the client. That is encapsulation (C1.2) and reuse (C1.4) working together, and it is why a class is the natural way to write an ADT: the storage is internal, and the methods are the interface.

The stack: last in, first out

Think of a stack of plates at a buffet: you add to the top and take from the top.

push(x) puts x on top.
pop() removes and returns the top item.
peek() returns the top item without removing it.
is_empty() tells whether there is anything to pop.

A Python list makes a good implementation if the end of the list is the top, because append() and pop() at the end are fast. Popping from an empty stack is called underflow; our class raises an IndexError with a clear message instead of failing somewhere confusing.

A stack only adds and removes at the top. The last item pushed is the first popped (LIFO), which is exactly what bracket matching needs: the most recent open bracket must be closed first.

Worked example

Example 1: Checking brackets with a stack

Your code editor highlights unbalanced brackets. Write balanced(text), which returns True when every (, [ and { is closed by the matching bracket in the right order.

Scan the text one character at a time.
When you see an opening bracket, push it. The stack now remembers every bracket that is still open, most recent on top.
When you see a closing bracket, the most recent open bracket must match it. If the stack is empty, or the popped bracket is the wrong kind, return False. The dictionary PAIRS maps each closer to its opener.
Other characters are ignored.
At the end, the text is balanced only if the stack is empty: ((x) leaves one ( unclosed.
Note the order of the test s.is_empty() or s.pop() != PAIRS[ch]: if the stack is empty, or stops before calling pop, so there is no underflow (short-circuit evaluation).

The Stack class, the function and its test output are below.

class Stack:

"""A last-in, first-out (LIFO) collection."""

def __init__(self):

self._items = [] # the top of the stack is the END of the list

def push(self, item):

"""Put item on top."""

self._items.append(item)

def pop(self):

"""Remove and return the top item."""

if self.is_empty():

raise IndexError("pop from empty stack")

return self._items.pop()

def peek(self):

"""Return the top item without removing it."""

if self.is_empty():

raise IndexError("peek at empty stack")

return self._items[-1]

def is_empty(self):

return len(self._items) == 0

def __len__(self):

return len(self._items)

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(text):

"""Return True if every bracket in text is closed in the right order."""

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()

for t in ["(a[1] + b) * {c}", "(]", "((x)", "print(len([1, 2]))"]:

print(t, balanced(t))

brackets.py: a stack ADT and a client function that uses only push, pop and is_empty.

(a[1] + b) * {c} True

(] False

((x) False

print(len([1, 2])) True

Output of the program above (what Python prints).

The queue: first in, first out

A queue is a line-up: people join at the back and are served from the front.

enqueue(x) adds x at the back.
dequeue() removes and returns the item at the front.
is_empty() tells whether anyone is waiting.

A plain list can do this with append() and pop(0), but pop(0) must shift every remaining element one place left, which gets slow for long queues (the Algorithm Design and Analysis unit measures this kind of cost). The standard-library collections.deque (said "deck") is built to add and remove quickly at both ends, so it is a better implementation. Because the queue is encapsulated, choosing deque is a private decision: client code never knows.

A queue adds at the back and removes from the front, so the first to join is the first served (FIFO). The first two skiers (shaded differently) board chair 1.

Worked example

Example 2: A chairlift simulation

Skiers join the lift line in the order Ana, Ben, Chloé, Dev, Eli. Each chair carries up to two people. Simulate the loading and print who rides each chair.

Enqueue each skier in arrival order.
While the queue is not empty, dequeue one rider; if anyone is still waiting, dequeue a second.
' and '.join(riders) joins one or two names into a single string.
Because a queue is FIFO, the loading order matches the arrival order: fair, like a real lift line.

Three chairs: Ana and Ben, Chloé and Dev, then Eli alone. The code is below.

from collections import deque

class Queue:

"""A first-in, first-out (FIFO) collection."""

def __init__(self):

self._items = deque() # fast at both ends

def enqueue(self, item):

"""Add item at the back."""

self._items.append(item)

def dequeue(self):

"""Remove and return the item at the front."""

if self.is_empty():

raise IndexError("dequeue from empty queue")

return self._items.popleft()

def is_empty(self):

return len(self._items) == 0

def __len__(self):

return len(self._items)

line = Queue()

for skier in ["Ana", "Ben", "Chloé", "Dev", "Eli"]:

line.enqueue(skier)

chair = 1

while not line.is_empty():

riders = [line.dequeue()]

if not line.is_empty():

riders.append(line.dequeue())

print(f"Chair {chair}: {' and '.join(riders)}")

chair += 1

lift.py: a Queue class built on collections.deque, and a simulation that uses it.

Chair 1: Ana and Ben

Chair 2: Chloé and Dev

Chair 3: Eli

Output of the program above (what Python prints).

The dictionary (map) ADT

A map stores key-value pairs and finds a value by its key. Its interface is roughly: put(key, value) (add or replace), get(key), remove(key), contains(key) and a way to list the keys. Python's built-in dict is a very fast implementation that uses a hash table: it turns each key into a number that says where to store the pair, so a look-up does not need to search.

To see interface and implementation clearly separated, Example 3 builds the same map ADT twice and runs one client function with both.

An ADT is defined by its interface (the operations), not by how it is stored. The client only calls put, get and keys, so either implementation can be plugged in without changing the client.

Worked example

Example 3: One client, two implementations

Write a map ADT with put, get and keys, implemented once with two parallel lists and once with a dict. Write count_words(text, counts) that works with either, and show that both give the same answer for "Snow on snow on snow".

ListMap searches its key list with in and index(), which checks keys one by one. Simple, but slow when there are thousands of keys.
DictMap wraps a Python dict, so each operation is a fast hash-table operation.
count_words never touches _keys or _d. It calls only put and get, so it cannot tell which implementation it was given. This style, where any object with the right methods will do, is called duck typing ("if it walks like a duck and quacks like a duck...") and it returns in the polymorphism lesson.
The text is lower-cased first, so "Snow" and "snow" count as one word: snow 3, on 2.

Both implementations print the same pairs. The code is below.

class ListMap:

"""Map ADT stored in two parallel lists: simple, but slow when large."""

def __init__(self):

self._keys = []

self._values = []

def put(self, key, value):

if key in self._keys:

self._values[self._keys.index(key)] = value

else:

self._keys.append(key)

self._values.append(value)

def get(self, key, default=None):

if key in self._keys:

return self._values[self._keys.index(key)]

return default

def keys(self):

return list(self._keys)

class DictMap:

"""The same Map ADT, stored in a Python dict (a hash table): fast."""

def __init__(self):

self._d = {}

def put(self, key, value):

self._d[key] = value

def get(self, key, default=None):

return self._d.get(key, default)

def keys(self):

return list(self._d)

def count_words(text, counts):

"""Count words using ANY map object that offers put, get and keys."""

for word in text.lower().split():

counts.put(word, counts.get(word, 0) + 1)

return counts

poem = "Snow on snow on snow"

for empty_map in [ListMap(), DictMap()]:

m = count_words(poem, empty_map)

pairs = []

for k in m.keys():

pairs.append((k, m.get(k)))

print(type(m).__name__, pairs)

maps.py: two implementations of one ADT, and a client that works with both.

ListMap [('snow', 3), ('on', 2)]

DictMap [('snow', 3), ('on', 2)]

Output of the program above (what Python prints).

ADT	Order rule	Main operations	Typical uses
Stack	LIFO	push, pop, peek, is_empty	undo, back button, bracket matching, function calls
Queue	FIFO	enqueue, dequeue, is_empty	print jobs, waiting lines, messages, turn order
Dictionary / map	by key	put, get, remove, contains	phone books, word counts, settings, caches

Choosing an ADT. Ask: in what order do items come out, or how are they found?

Just for fun

When a program calls functions inside functions forever, Python stops with a RecursionError, and many other languages report a stack overflow, because every unfinished call is stored on a stack. The well-known programmers' question-and-answer site Stack Overflow is named after that very error.

Hands-on activity

Plates, line-ups and undo

You need: about 6 books or plastic plates, 7 small objects to act as people (cups, toys), sticky notes, and a computer with Python.

Stack: label the books A to F with sticky notes. Push A, B, C onto a pile; pop twice; push D. Write down what each pop returned. Then type the same operations with the Stack class and compare.
Queue: line up 5 of the objects as a lift line. Enqueue two more at the back, dequeue three from the front. Predict the front of the line, then check with the Queue class.
Undo: write a tiny editor that stores the text as a string and an undo_stack. Each command type word pushes the old text before adding the word; undo pops and restores the old text. Test it: type "maple", type "syrup", undo, type "leaf". The final text should be "maple leaf".

What to look for: you can say why undo needs a stack (the latest change must be undone first) and why a lift line needs a queue (fairness).

Your turn

What is an abstract data type?

Predict the output:

s = Stack()

for x in [4, 7, 1]:

s.push(x)

print(s.pop(), s.peek(), len(s))

Predict the output:

q = Queue()

for x in [4, 7, 1]:

q.enqueue(x)

q.dequeue()

q.enqueue(9)

print(q.dequeue(), len(q))

Which ADT fits each job? (a) a browser's back button (b) tickets at a help desk (c) province abbreviations (ON → Ontario).

Trace balanced("{[}]"). Where does it fail?

Why does the Stack class keep the top of the stack at the end of the list rather than the start?

Why can count_words work with both ListMap and DictMap?

More practice: warm-up

What does LIFO stand for?

What does FIFO stand for?

Which operation looks at the top of a stack without removing it?

What error does our Stack raise on pop from an empty stack?

Which standard-library module provides deque?

More practice: on your own

Use a Stack to write reverse(text) that returns the text backwards. What is reverse("Iqaluit")?

Add a peek() method (front item, not removed) to the Queue class.

Add remove(key) to DictMap. It should raise KeyError if the key is missing.

A printer queue holds jobs A, B, C. Job D is added, two jobs print, then E is added. List the queue from front to back.

Why is ListMap.get slow for 100 000 keys but DictMap.get fast?

Challenge

Postfix notation puts each operator after its two operands. For example, this postfix expression means (3 + 4) × 2:

3 4 + 2 *

Write eval_postfix(text) using a Stack. Tokens are separated by spaces; the operators are plus, minus and times, written as in Python (+, - and the asterisk). What does this call return?

eval_postfix("5 1 2 + 4 * + 3 -")

Implement a Queue using two stacks (an "inbox" and an "outbox") so that it is still FIFO. Explain why it works.

A hospital emergency room does not serve patients first-come, first-served; the most urgent go first. Which ADT is that, and how could you implement it simply with what you know?

Check your understanding

Quiz

Which statement best describes an abstract data type?

After push(1), push(2), push(3), pop(), what does peek() return?

After enqueue("a"), enqueue("b"), enqueue("c"), dequeue(), what does the next dequeue() return?

Which ADT is best for an Undo feature?

Why is collections.deque a better queue implementation than a list with pop(0)?

What does balanced("(()") return with the stack-based checker?

For parents and teachers

Big idea: C1.1 names stacks, queues and dictionaries as abstract data types that students should use when decomposing problems. The key idea is the split between interface (what operations exist) and implementation (how the data is stored). Writing ADTs as classes also practises encapsulation (C1.2) and reuse (C1.4). How fast each implementation is gets measured in the Algorithm Design and Analysis unit.

How to help: The plates-and-line-ups activity works well with real objects. Ask your teen to predict each pop or dequeue aloud before doing it.

Common difficulties:

Mixing up which end is the top of a stack or the front of a queue.
Popping in the wrong order in postfix evaluation (the right operand comes off first).
Reaching into _items from client code instead of using the methods.
Forgetting to check for an empty structure before popping.