Skip to content
wannacode

Stack and queue

In short: A stack returns the last element added (LIFO) and a queue the first (FIFO); a stack on a growing array and a queue as a ring buffer make every operation O(1), with adding O(1) on average.

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: Stack<T> and Queue<T>. 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
{
    private char[] items = new char[4];
    private int size = 0;


    public void Push(char c)
    {
        if (size == items.Length)
        {
            Array.Resize(ref items, size * 2);
        }
        items[size] = c;
        size++;
    }


    public char Pop()
    {
        if (size == 0) throw new InvalidOperationException("empty stack");
        size--;
        return items[size];
    }


    public bool IsEmpty => 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).

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.
static int FirstError(string text)
{
    var opened = new CharStack();
    for (int i = 0; i < text.Length; i++)
    {
        char c = text[i];
        if ("([{".Contains(c))
        {
            opened.Push(c);
        }
        else if (")]}".Contains(c))
        {
            if (opened.IsEmpty) return i;
            if ("([{".IndexOf(opened.Pop()) != ")]}".IndexOf(c)) return i;
        }
    }
    return opened.IsEmpty ? -1 : text.Length;
}
string[] templates =
[
    "Order {order}: [{items}] (total {total} €)",
    "Order {order}: [{items}) (total {total} €)",
    "Order {order}: [{items}] (total {total} €"
];
foreach (string t in templates)
{
    int at = FirstError(t);
    Console.WriteLine(at < 0 ? "OK" : $"error at position {at}");
}
Output
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

Console.WriteLine(FirstError("({total)}"));
Answer

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:

var jobs = new List<string>();
for (int id = 1; id <= 10_000; id++)
{
    jobs.Add("#" + id);
}
int done = 0;
while (jobs.Count > 0)
{
    string job = jobs[0];
    jobs.RemoveAt(0);
    done++;
}
Console.WriteLine($"processed: {done}");
Output
processed: 10000

It looks harmless, but jobs.RemoveAt(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
{
    private string?[] items = new string?[4];
    private int head = 0;
    private int size = 0;


    public void Enqueue(string job)
    {
        if (size == items.Length) Grow();
        int tail = (head + size) % items.Length;
        items[tail] = job;
        size++;
    }


    public string Dequeue()
    {
        if (size == 0)
            throw new InvalidOperationException();
        string job = items[head]!;
        items[head] = null;
        head = (head + 1) % items.Length;
        size--;
        return job;
    }


    public bool IsEmpty => size == 0;


    private void Grow()
    {
        var bigger = new string?[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[(head + i) % items.Length];
        }
        items = bigger;
        head = 0;
    }
}

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

public override string ToString() =>
    $"[{string.Join(", ", items.Select(s => s ?? "-"))}] head={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
{
    private string?[] items = new string?[4];
    private int head = 0;
    private int size = 0;


    public void Enqueue(string job)
    {
        if (size == items.Length) Grow();
        int tail = (head + size) % items.Length;
        items[tail] = job;
        size++;
    }


    public string Dequeue()
    {
        if (size == 0)
            throw new InvalidOperationException();
        string job = items[head]!;
        items[head] = null;
        head = (head + 1) % items.Length;
        size--;
        return job;
    }


    public bool IsEmpty => size == 0;


    private void Grow()
    {
        var bigger = new string?[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[(head + i) % items.Length];
        }
        items = bigger;
        head = 0;
    }
}
Step by step, in words
  1. A delivery queue on an array with 4 places. head is the index of the first order, size is how many wait.
  2. Enqueue: the new order goes to (head + size) % 4. Three orders take places 0, 1 and 2.
  3. Dequeue takes the order at head and moves head forward. Nobody else moves: #103 stays at place 2.
  4. #104: (2 + 1) % 4 = 3, the last place of the array.
  5. #105: (2 + 2) % 4 = 0. The end of the array wraps to the start, and the free places in front are used again.
  6. #106 goes to place 1. Now 4 of 4 are taken: the array is full, and the first in line is at place 2.
  7. #107 does not fit. Grow makes 8 places and copies in queue order, from head on: #103, #104, #105, #106. head becomes 0.
  8. #107 goes to place 4. One copy per order for growing, and none for taking from the front.
var q = new JobQueue();
for (int id = 101; id <= 103; id++) q.Enqueue("#" + id);
Console.WriteLine(q);
Console.WriteLine($"delivered: {q.Dequeue()}");
Console.WriteLine($"delivered: {q.Dequeue()}");
Console.WriteLine(q);
for (int id = 104; id <= 106; id++) q.Enqueue("#" + id);
Console.WriteLine(q);
q.Enqueue("#107");
Console.WriteLine(q);
Output
[#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?

var q = new JobQueue();
for (int id = 201; id <= 204; id++) q.Enqueue("#" + id);
q.Dequeue();
q.Dequeue();
q.Dequeue();
q.Enqueue("#205");
q.Enqueue("#206");
Console.WriteLine(q);
Answer

Try it

Fill in the blank

The new order goes to the place:

int tail = (head + 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:

static long ShiftMoves(int n)
{
    int[] items = new int[4];
    int size = 0;
    long moves = 0;
    for (int job = 1; job <= n; job++)
    {
        if (size == items.Length)
        {
            moves += size;
            Array.Resize(ref items, size * 2);
        }
        items[size++] = job;
    }
    while (size > 0)
    {
        for (int i = 1; i < size; i++)
        {
            items[i - 1] = items[i];
            moves++;
        }
        size--;
    }
    return moves;
}


static long RingMoves(int n)
{
    int[] items = new int[4];
    int head = 0, size = 0;
    long moves = 0;
    for (int job = 1; job <= n; job++)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[size * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[(head + i) % items.Length];
                moves++;
            }
            items = bigger;
            head = 0;
        }
        items[(head + size) % items.Length] = job;
        size++;
    }
    while (size > 0)
    {
        head = (head + 1) % items.Length;
        size--;
    }
    return moves;
}
foreach (int n in new[] { 1000, 10000 })
{
    Console.WriteLine($"{n}: list {ShiftMoves(n)}, ring {RingMoves(n)}");
}
Output
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)
Algorithmn = 10n = 1,000n = 10,000n = 100,000
List: remove at index 057500,52050,011,380≈ 5,001,138,000
Ring buffer121,02016,380131,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:

private void Grow()
{
    var bigger = new string?[items.Length * 2];
    for (int i = 0; i < size; i++)
    {
        bigger[i] = items[i];
    }
    items = bigger;
    head = 0;
}
var q = new JobQueue();
for (int id = 101; id <= 103; id++) q.Enqueue("#" + id);
q.Dequeue();
q.Dequeue();
for (int id = 104; id <= 107; id++) q.Enqueue("#" + id);
var order = new List<string>();
while (!q.IsEmpty) order.Add(q.Dequeue());
Console.WriteLine(string.Join(" ", order));
Output
#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
Output
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?
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?
3. A ring buffer with 8 places: head = 6, size = 3. Which place does the new order go to?
4. The ring buffer is full and has to grow. Why can grow not simply copy items[0], items[1]… into the new array?

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