Last in or first in (stacks and queues)

You press undo in an essay and the last thing you typed disappears, not the first. You send three pages to a school printer and they come out in the order you sent them.

Those are two different rules for taking things out. Each one is a data structure every programmer uses.

A stack is like a pile of plates. You push a plate on top, and you pop the top one off. You never take from the middle.

In Python a list works as a stack. append pushes onto the end, and pop() takes the last item. Undo, the back button and a game's menus all use one.

# An undo button: each change is pushed on a stack.
undo = []
undo.append("typed Hello")
undo.append("made it bold")
undo.append("added a picture")
print("stack:", undo)
last = undo.pop()
print("undo takes back:", last)
print("stack now:", undo)
# Push "changed the colour", then pop twice.
# Which two changes come back, and in what order?

A queue is like the line at a till. People join at the back and are served from the front, so the first to arrive is the first served.

A list can act as a queue: append joins at the back and pop(0) serves the front. Print jobs, game lobbies and messages all wait in queues.

# A queue at a cafe till: join at the back, serve from the front.
queue = []
queue.append("Amir")
queue.append("Beth")
queue.append("Chen")
print("queue:", queue)
served = queue.pop(0)
print("served first:", served)
print("still waiting:", queue)
# Add "Dana" to the queue, then serve two more people.
# Who is left waiting?

When a list serves its front with pop(0), every other item shuffles forward one place. That is O(n), and a long queue makes it slow.

Python's deque is built for queues. Its popleft is O(1). The Runs time one join and one serve on a queue of 100,000, first with a list and then with a deque.

docker exec jupyter python3 -m timeit -s "q = list(range(100000))" "q.append(0)" "q.pop(0)"

docker exec jupyter python3 -m timeit -s "from collections import deque" -s "q = deque(range(100000))" "q.append(0)" "q.popleft()"

from collections import deque

# Orders at a till, served in the order they arrive.
orders = deque()
orders.append("cheese toastie")
orders.append("hot chocolate")
orders.append("flapjack")
print("first out:", orders.popleft())
print("waiting:", list(orders))

Code editors check that every bracket closes. They use a stack. Read the text from left to right.

Push each opening bracket. At each closing bracket, pop the top one: it must be the same kind. At the end the stack must be empty. A wrong pop, or a pop from an empty stack, means a mistake.

Could you make a stack using only queues? Try it in your notebook with two deques and only append and popleft.

Push 1, 2 and 3, then pop. You should get 3. Which operation becomes slow, and is it O(1) or O(n)?