Stack and queue in Python

Problem

The order email comes out empty

The shop sends an email for every order from a template: Order {order}: [{items}] (total {total} €). The templates are written by hand, and sometimes a bracket is not closed, or is closed with the wrong one. Then the email program fills in nothing, and the customer gets an empty email.

Before sending, you want to say: "the template is fine" or "error at position 23". Counting the brackets is not enough: in [{items}) two are opened and two are closed, and the error is right there.

In the collections lesson "Stack, queue and linked list" the stack and the queue were ready-made: list and deque. Here you build them yourself, to see what every operation costs and where the trap is.

The idea

A stack on a growing array

Brackets close in reverse order: the last one opened is closed first. That is a stack: you put on top and take from the top.

Inside, a stack is an array and a counter size:

push writes at index size and increases the counter;
pop decreases the counter and returns what is there;
when the array is full, it becomes twice as big, as in amortized complexity.

class CharStack:
    def __init__(self):
        self.items = [None] * 4
        self.size = 0

    def push(self, c):
        if self.size == len(self.items):
            self.items += [None] * self.size
        self.items[self.size] = c
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise IndexError("empty stack")
        self.size -= 1
        return self.items[self.size]

    def is_empty(self):
        return self.size == 0

Both push and pop work only with the end of the array. Nothing moves, so both are O(1) (push is O(1) on average, because of the growing).

In Python list already is such a growing array, and append and pop() are exactly push and pop. Here the array has a fixed size, [None] * 4, so you can see what list does for you.

See it

Checking the template

You go over the template character by character:

an opening bracket goes onto the stack;
a closing one takes the top of the stack and checks that it is of the same kind;
if the stack is empty at a closing bracket, or not empty at the end, the template is wrong.

def first_error(text):
    opened = CharStack()
    for i, c in enumerate(text):
        if c in "([{":
            opened.push(c)
        elif c in ")]}":
            if opened.is_empty():
                return i
            if "([{".index(opened.pop()) != ")]}".index(c):
                return i
    return -1 if opened.is_empty() else len(text)

templates = [
    "Order {order}: [{items}] (total {total} €)",
    "Order {order}: [{items}) (total {total} €)",
    "Order {order}: [{items}] (total {total} €",
]
for t in templates:
    at = first_error(t)
    print("OK" if at < 0 else f"error at position {at}")

OK
error at position 23
error at position 41

In the second template ) comes when [ is on top of the stack: error at position 23. In the third, ( is never closed and the error is at the end, at position 41, the length of the text.

More precisely, if you are curious

A real JSON checker also skips brackets inside quoted text: "[1" opens nothing. Then the stack also keeps "I am inside text now". The same goes for HTML tags: the stack keeps the names of the open tags, and </div> must meet div on top.

Try it

Predict the output

print(first_error("({total)}"))

Answer

-1

Problem

The morning delivery queue

At 8 in the morning 10,000 delivery requests wait in the system. The couriers take them one by one, the oldest first: that is a queue. Someone wrote it with a plain list:

jobs = []
for id in range(1, 10_001):
    jobs.append(f"#{id}")
done = 0
while jobs:
    job = jobs.pop(0)
    done += 1
print(f"processed: {done}")

processed: 10000

It looks harmless, but jobs.pop(0) removes from index 0 of an array. Everyone after the first moves one place forward. With 10,000 waiting, the first take moves 9,999, the second 9,998… Together that is about 50 million moves just to take each one once.

The idea

A ring buffer: head moves, not the orders

Do not move the orders. Move the pointer to the first one.

head is the index of the first order, and size is how many wait.
A take reads items[head], clears the place and moves head one forward. Nobody else moves.
The new order goes to tail = (head + size) % places. The remainder of the division turns the array into a circle: after the last place comes the first. The free places at the front, freed by the takes, are used again.
When all the places are taken, grow makes an array twice as big and copies the orders in queue order, from head on. Then head is 0.

Such an array, whose end continues from the start, is called a ring buffer (or circular buffer).

class JobQueue:
    def __init__(self):
        self.items = [None] * 4
        self.head = 0
        self.size = 0

    def enqueue(self, job):
        if self.size == len(self.items):
            self.grow()
        tail = (self.head + self.size) % len(self.items)
        self.items[tail] = job
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("empty queue")
        job = self.items[self.head]
        self.items[self.head] = None
        self.head = (self.head + 1) % len(self.items)
        self.size -= 1
        return job

    def is_empty(self):
        return self.size == 0

    def grow(self):
        n = len(self.items)
        bigger = [None] * (n * 2)
        for i in range(self.size):
            bigger[i] = self.items[(self.head + i) % n]
        self.items = bigger
        self.head = 0

So that you can see what is inside, the class also has a method for printing:

def __str__(self):
    shown = ", ".join(s or "-" for s in self.items)
    return f"[{shown}] head={self.head}"

See it

head, tail and wrapping to the start

Three orders come in, two leave, then three more. The last of them is not after the end of the array, but at index 0. Then the array is full, and the seventh order makes it grow:

class JobQueue:
    def __init__(self):
        self.items = [None] * 4
        self.head = 0
        self.size = 0

    def enqueue(self, job):
        if self.size == len(self.items):
            self.grow()
        tail = (self.head + self.size) % len(self.items)
        self.items[tail] = job
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("empty queue")
        job = self.items[self.head]
        self.items[self.head] = None
        self.head = (self.head + 1) % len(self.items)
        self.size -= 1
        return job

    def is_empty(self):
        return self.size == 0

    def grow(self):
        n = len(self.items)
        bigger = [None] * (n * 2)
        for i in range(self.size):
            bigger[i] = self.items[(self.head + i) % n]
        self.items = bigger
        self.head = 0

Step by step, in words

A delivery queue on an array with 4 places. head is the index of the first order, size is how many wait.
enqueue: the new order goes to (head + size) % 4. Three orders take places 0, 1 and 2.
dequeue takes the order at head and moves head forward. Nobody else moves: #103 stays at place 2.
#104: (2 + 1) % 4 = 3, the last place of the array.
#105: (2 + 2) % 4 = 0. The end of the array wraps to the start, and the free places in front are used again.
#106 goes to place 1. Now 4 of 4 are taken: the array is full, and the first in line is at place 2.
#107 does not fit. grow makes 8 places and copies in queue order, from head on: #103, #104, #105, #106. head becomes 0.
#107 goes to place 4. One copy per order for growing, and none for taking from the front.

q = JobQueue()
for id in range(101, 104):
    q.enqueue(f"#{id}")
print(q)
print(f"delivered: {q.dequeue()}")
print(f"delivered: {q.dequeue()}")
print(q)
for id in range(104, 107):
    q.enqueue(f"#{id}")
print(q)
q.enqueue("#107")
print(q)

[#101, #102, #103, -] head=0
delivered: #101
delivered: #102
[-, -, #103, -] head=2
[#105, #106, #103, #104] head=2
[#103, #104, #105, #106, #107, -, -, -] head=0

Look at the third line of the output: [#105, #106, #103, #104] head=2. The first in line is #103, at index 2, and #105 and #106 are at the front, because there were free places there. The order in the array is not the order of the queue. That is why grow does not copy one to one.

Try it

Where do #205 and #206 go?

q = JobQueue()
for id in range(201, 205):
    q.enqueue(f"#{id}")
q.dequeue()
q.dequeue()
q.dequeue()
q.enqueue("#205")
q.enqueue("#206")
print(q)

Answer

[#204, #205, #206, -] head=0

[#205, #206, -, #204] head=3

[-, -, -, #204, #205, #206, -, -] head=3

Try it

Fill in the blank

The new order goes to the place:

tail = (self.head + self.size) %

The idea

What it costs

Count the moves of requests that are already written: the copies when growing, and the moving forward when taking from index 0. Both queues start with 4 places and double. 10,000 requests come in, then all of them leave:

def shift_moves(n):
    items = [None] * 4
    size = 0
    moves = 0
    for job in range(1, n + 1):
        if size == len(items):
            moves += size
            items += [None] * size
        items[size] = job
        size += 1
    while size > 0:
        for i in range(1, size):
            items[i - 1] = items[i]
            moves += 1
        size -= 1
    return moves


def ring_moves(n):
    items = [None] * 4
    head = size = 0
    moves = 0
    for job in range(1, n + 1):
        if size == len(items):
            bigger = [None] * (size * 2)
            for i in range(size):
                bigger[i] = items[(head + i) % len(items)]
                moves += 1
            items = bigger
            head = 0
        items[(head + size) % len(items)] = job
        size += 1
    while size > 0:
        head = (head + 1) % len(items)
        size -= 1
    return moves

for n in [1000, 10000]:
    print(f"{n}: list {shift_moves(n)}, ring {ring_moves(n)}")

1000: list 500520, ring 1020
10000: list 50011380, ring 16380

Run it, up to 100,000 too:

List: remove at index 0 O(n²)
Ring buffer O(n)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
List: remove at index 0	57	500,520	50,011,380	≈ 5,001,138,000
Ring buffer	12	1,020	16,380	131,068

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

With 10,000 requests the list makes 50,011,380 moves, and the ring 16,380, all of them from growing. A take from index 0 is O(n), so n takes are O(n²). In the ring a take is O(1), and an add is O(1) on average, like the stack.

More precisely, if you are curious

How it is in the languages:

Java: ArrayDeque is a ring buffer: an array elements and the indexes head and tail. One place always stays empty, to tell "empty" (head == tail) from "full", so the array starts with 17 places for 16 elements. When it fills up, a small array grows a little over twice, and a big one by 50%.
C#: Queue<T> is a ring buffer with _array, _head, _tail and _size. It starts with 4 places and doubles the array when it is full. Stack<T> is an array that doubles too.
Python: collections.deque is not a ring buffer, but a linked list of blocks of 64 places. So both ends are O(1). list.pop(0) is O(n), exactly as in the problem.
JavaScript: there is no built-in queue. shift() moves all the elements of the array. V8 sometimes makes it fast by moving the start of the array instead of moving the elements, but not for big arrays, and it is not promised. For a big queue you write a ring like this one, or a queue of nodes.

Some rings keep tail instead of size, and others keep both. That is just another way of writing the same thing: tail = (head + size) % places.

Try it

Find the bug

Someone wrote grow in a shorter way. The orders before the growing come out in order, and after it mixed up:

def grow(self):
    n = len(self.items)
    bigger = [None] * (n * 2)
    for i in range(self.size):
        bigger[i] = self.items[i]
    self.items = bigger
    self.head = 0

q = JobQueue()
for id in range(101, 104):
    q.enqueue(f"#{id}")
q.dequeue()
q.dequeue()
for id in range(104, 108):
    q.enqueue(f"#{id}")
order = []
while not q.is_empty():
    order.append(q.dequeue())
print(" ".join(order))

#105 #106 #103 #104 #107

Which line is the bug on?

Pick the line with the bug.

Exercise

The last 5 lines of the log

Solve it in your editor.

The last 5 lines. The shop's server writes a line to the log for every action. On an error you want to see the last 5 lines, not the whole log. Write LastLines with a ring of 5 places that never grows: while there is room, a line goes to (head + size) % 5; when it is full, the new line overwrites the oldest one (at head), and head moves forward. A method lines() returns the lines from the oldest to the newest. Give it the eight lines:

09:00 login: ann
09:02 cart: +2
09:03 payment: €48
09:05 logout: ann
09:07 login: ivo
09:08 search: coffee
09:09 cart: +1
09:11 payment: €12

The last 5:
09:05 logout: ann
09:07 login: ivo
09:08 search: coffee
09:09 cart: +1
09:11 payment: €12

More tasks

Brackets and tags. Extend the template check to the tags <b>…</b> and <i>…</i>: the stack keeps the names of the open tags.
A queue that shrinks. If after the morning peak 10 requests wait in a queue with 8,192 places, the memory sits empty. Make the queue halve its array when it is less than a quarter full. Why not when it is less than half full?
A stack from two queues. Build a stack using only two of your queues. What does pop cost?

Test

Check yourself

1. Why does a stack check the brackets, instead of just counting the opening and closing ones?Because the last bracket opened must be closed first, and a count does not know which one was lastBecause counting does not work with more than 10 bracketsBecause counting is slower

2. A queue with 10,000 waiting is on a plain list, and every take is from index 0. How many moves does one take from the front cost?OneNoneAbout as many as wait behind it: they all move one place forward

3. A ring buffer with 8 places: head = 6, size = 3. Which place does the new order go to?To 0To 1To 9

4. The ring buffer is full and has to grow. Why can grow not simply copy items[0], items[1]… into the new array?It can: the places are the sameBecause the first in line is at head, not at 0; the copy must be in queue order, from head onBecause the new array is smaller

Stack and queue

Cookies