Skip to content
wannacode

Stack, queue and linked list

Problem

"Undo" undoes the wrong thing

A text editor keeps the actions in a list. Ctrl+Z should undo the last one, but it undoes the first:

actions = []
actions.append("Typed text")
actions.append("Made the title bold")
actions.append("Inserted a photo")


# Ctrl+Z: undo the last action.
undone = actions.pop(0)
print("Undone:", undone)
print("Left:", actions)
Output
Undone: Typed text
Left: ['Made the title bold', 'Inserted a photo']

The fix is actions.pop(). But everyone who touches this code has to remember which end to remove from. And at the store checkout it is the other way around: the first one who came is served first. Is there a collection that knows the end by itself?

The idea

Stack: the last one on top

A stack is like a pile of plates. You put on top and you take from the top. The last thing put in comes out first. This is called LIFO: last in, first out.

The "Back" button in the browser is a stack:

history = []
history.append("Home")
history.append("Laptops")
history.append("14-inch laptop")
print("Now:", history[-1])


history.pop()
print("Back:", history[-1])
print(history)
Output
Now: 14-inch laptop
Back: Laptops
['Home', 'Laptops']

Python has no separate class for a stack: a list is a stack if you put and take only at the end.

  • append puts on top, pop() with no index removes and returns the top one, and history[-1] only looks at the top one.
  • The top is the end of the list. Both operations are fast, because nothing moves at the end.
  • print prints the stack from the bottom up: the top one is last.
More precisely, if you are curious
  • pop() and [-1] on an empty list stop the program with IndexError. So check first. if history: means "if the list is not empty": an empty list in if and while acts like False.
history = []
if history:
    print("Now:", history[-1])
else:
    print("There is no previous page.")
try:
    history.pop()
except IndexError as e:
    print(f"IndexError: {e}")
Output
There is no previous page.
IndexError: pop from empty list

Try it

What is left to undo?

What will the program print?

undo = []
undo.append("font")
undo.append("color")
undo.append("size")
undo.pop()
undo.append("underline")
while len(undo) > 0:
    print(undo.pop())
Answer

The idea

Queue: first come, first served

A queue is like the line at the checkout. You join at the back, and the first one is served. This is called FIFO: first in, first out.

Print jobs wait in a queue:

from collections import deque


printer = deque()
printer.append("invoice.pdf")
printer.append("contract.docx")
printer.append("photo.jpg")
print("Next:", printer[0])


while len(printer) > 0:
    print("Printing", printer.popleft())
print("Queue:", printer)
Output
Next: invoice.pdf
Printing invoice.pdf
Printing contract.docx
Printing photo.jpg
Queue: deque([])
  • deque is in the collections module, so the file starts with from collections import deque. The name comes from double-ended queue, a queue with two ends.
  • append puts at the back, popleft removes and returns the first one, and printer[0] looks at the first one.
  • Why not a list with pop(0)? pop(0) moves all the others one place forward, like inserting at the front in the lesson on lists. deque removes from the front without moving anything.
More precisely, if you are curious
  • popleft on an empty queue stops the program with IndexError. A deque can also be a stack: append and pop work at the right end.
from collections import deque


clients = deque()
clients.append("Customer 1")
clients.append("Customer 2")
print("Last:", clients.pop())
print("Served:", clients.popleft())
try:
    clients.popleft()
except IndexError as e:
    print(f"IndexError: {e}")
Output
Last: Customer 2
Served: Customer 1
IndexError: pop from an empty deque
  • There is also queue.Queue, but it is for programs with several threads that pass tasks to each other. For an ordinary queue, use deque.

Try it

Next at the checkout

The cashier calls the next customer. Which method takes them from the queue?

from collections import deque

checkout = deque()
checkout.append("Ivan")
checkout.append("Maria")
client = checkout.()
print(f"Your turn, {client}")

See it

A linked list inside

A list keeps the elements next to each other in an array. That is why inserting at the front moves all the others. There is another way: each element is in a separate object that holds the value and an arrow to the next one. An object like this is called a node:

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

A list of nodes is called a linked list. It is enough to keep the first node, head. You find each next one by following the next arrow. The last one points to None.

head = None
head = Node("Coffee", head)
head = Node("Milk", head)
head = Node("Bread", head)


n = head
while n is not None:
    print(n.value)
    n = n.next
Step by step, in words
  1. The list is empty: head is None.
  2. A new node: next is the old head (None), and head moves to the node.
  3. The second node points to the first. Nothing moves in memory: only the arrows change.
  4. The third node also goes in at the front: the last one added is first.
  5. n starts at head and prints each node.
  6. n reaches None: the loop stops.
  • Inserting at the front: a new node whose next points to the old first one, and head points to the new one. Two arrows, and you move nothing.
  • Looping: you start at head and follow next until you reach None.
  • The cost: nodes have no indexes. You reach the fifth element by going through the first four.

The idea

deque, and which one when

Python has no ready-made linked list like the Node class. It has deque: inside, it is a linked list, but each node holds not one element but a whole block of them. That is why it is fast at both ends: append and appendleft, pop and popleft, [0] and [-1]:

from collections import deque


route = deque()
route.append("Plovdiv")
route.append("Stara Zagora")
route.appendleft("Sofia")
route.append("Burgas")
print(list(route))


route.remove("Stara Zagora")
print("After the change:", list(route))
print("From", route[0], "to", route[-1])
Output
['Sofia', 'Plovdiv', 'Stara Zagora', 'Burgas']
After the change: ['Sofia', 'Plovdiv', 'Burgas']
From Sofia to Burgas

Which one when:

  • A list by number: list. This is the usual choice.
  • A stack: list with append and pop.
  • A queue: deque with append and popleft.
More precisely, if you are curious
  • list(route) makes an ordinary list from the queue, so that it prints as a list. Plain print(route) gives deque([...]).
  • In CPython each block of a deque holds 64 elements, and the blocks are linked in both directions, to the next one and to the previous one. That is why route[0] and route[-1] are fast, while an element in the middle of a big queue is slow: you reach it through the blocks.
  • The node from this card has only next. A list like that is called singly linked.

Try it

Find the bug

The function should count the nodes. For the list Bread → Milk → Coffee it returns 2 instead of 3. And for an empty list it stops with AttributeError. Which line has the bug?

Pick the line with the bug.

Exercise

Stacks and queues at work

Solve the tasks in your editor. The collection is a field of the class with a _ in front.

1. A toy train. A Train class with the methods add_wagon(wagon) and remove_wagon(). The train is a stack: the last car coupled is the first one uncoupled. remove_wagon() returns the uncoupled car, or None if there is none. Add count(). Couple three cars and uncouple two.

Output
Uncoupled: Car 3
Uncoupled: Car 2
Cars: 1

2. A bus route. A BusRoute class with a queue of stops and the methods add_stop(stop) and get_next_stop(), which returns the next stop, or None if the route is over. Add "Central Station", "NDK" and "Studentski Grad", and go through the route.

Output
Next stop: Central Station
Next stop: NDK
Next stop: Studentski Grad
End of the route.

3. A stock ticker. A StockTicker class keeps the last N prices of one stock. The constructor gets the symbol and N. update_price(price) adds a price, and if there are more than N prices, it removes the oldest one. Add get_last_price() and average() for the stored prices. For SAP with N = 3, pass the prices 150, 152, 149 and 155. Hint: deque(maxlen=3) removes the oldest one by itself when there are more than 3. Print the prices with two digits after the decimal point.

Output
SAP: last price €155.00
Average of the last 3: €152.00

4. Balanced brackets. A code editor checks whether the brackets (), [] and {} are closed in the right order. Write is_balanced(text) with a stack: at an opening bracket you put it on the stack, and at a closing one you remove the top one and check that it is the same kind. At the end the stack must be empty. Read three lines.

Input
(1 + [2 * 3])
(1 + 2]
((5)
Output
(1 + [2 * 3]) -> yes
(1 + 2] -> no
((5) -> no

5. Your own linked list. A MyLinkedList class with the nodes from the lesson and the methods add(value) (at the end), remove(value), contains(value), size() and __str__(). In remove, find the node before the one you are looking for and redirect its next. Check the case where the first one is removed separately.

Output
[Invoice, Report, Meeting]
Contains Report: True
After removal: [Invoice, Meeting]
Size: 2

More tasks

  • Undo and Redo. Keep two stacks: undo and redo. A new action goes into undo and clears redo. "Undo" moves the top one from undo to redo, and "Redo" moves it back.
  • Words in reverse. Read a sentence and print it with the words in reverse order, going through a stack: "Today is Friday" becomes "Friday is Today".
  • Two checkouts. Customers come one by one and go to the checkout with the shorter line. Print who was served at which checkout.
  • Reverse the linked list. Add a reverse() method to MyLinkedList that turns the arrows around without making new nodes.

Test

Check yourself

1. You put A on a stack, then B, then C. Which comes out first at pop?
2. Which one is a job for a queue?
3. What happens at popleft() on an empty deque?
4. Why is inserting at the start of a linked list fast?
5. What is slow in a linked list?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·