Stacks, Queues and Linked Lists

Ava's shop gets busy at lunch time. Customers line up, and the first to arrive must be served first. Meanwhile her undo button in the order screen must reverse the last action first. Two different rules for removing things, and each has a name. A queue serves the oldest first, and a stack serves the newest first.

• A line of customers: first in, first out
• An undo button: last in, first out
• Two classic data structures

Stack versus queue

Think of a stack of plates. You add a plate on top, and you take a plate from the top. Last in, first out. A queue is a line at a cashier. You join at the back, and leave from the front. First in, first out. Both are simple, and they appear everywhere, in browsers, operating systems, and algorithms.

A stack with a list

A Python list is already a good stack. Append pushes onto the end, and pop removes from the end, both very fast. The last item added is the first removed. Here, Ava keeps a history of her edits, and undoes the last two. We peek at the top with minus one.

history = []
for action in ["add fern", "add ivy", "remove rose", "apply 10% off"]:
    history.append(action)
print(history[-1])
print(history.pop())
print(history.pop())
print(history)

apply 10% off
apply 10% off
remove rose
['add fern', 'add ivy']

A queue with deque

For queues, use collections deque. Popping from the front of a list is slow, because every item shifts. A deque removes from both ends quickly. Here, customers join the line, and Ava serves them in order, first in, first out. And the maximum length option makes a rolling window of the latest items.

from collections import deque

line = deque()
for name in ["Maya", "Sam", "Lee"]:
    line.append(name)
print("Serving", line.popleft())
print("Next:", line[0], "waiting:", len(line))
last3 = deque(range(10), maxlen=3)
print(list(last3))

Serving Maya
Next: Sam waiting: 2
[7, 8, 9]

A linked list from scratch

A linked list chains nodes. Each node holds a value, and a link to the next node. There is no index, you follow the links, from the head. Inserting at the front is instant. Building one yourself shows how objects reference each other, and it is a classic interview question.

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

head = None
for v in ["rose", "ivy", "fern"]:
    head = Node(v, head)

node = head
while node:
    print(node.value, end=" -> ")
    node = node.next
print("end")

fern -> ivy -> rose -> end

Choosing a data structure

The choice affects speed. Lists are great for ordered items, and fast at the end. Dictionaries and sets give fast lookups by key, or by value. Deques give fast operations at both ends. Heaps keep the smallest item ready. Tuples are fixed. Choosing well, matters more than any clever trick.

Reverse with a stack

Your turn. Use a list as a stack, to reverse a word. Push each letter, then pop them all, and join the result. Ready? Here is one solution. A loop pushes the letters, and a second loop pops them back, in reverse order.

stack = []
for ch in "leaf":
    stack.append(ch)
out = ""
while stack:
    out += stack.pop()
print(out)

fael

Summary