A queue with two stacks

A few years ago, during a job interview for Google, a friend got the following challenge: “implement a queue using two stacks”. I found it an interesting challenge, so I decided to give it a thought (for the inverse problem, check the next post). Before you keep reading, think about how you would approach this challenge.

...

Done?

Let’s begin with a brief review on stacks and queues.

Stacks and queues

A stack is a collection of elements based on the concept of Last In First Out (LIFO): the last added element is the first to leave. It has two basic operations: push (add an element to the end of the stack) and pop (remove and return the last element of the stack).

Analogously, a queue is a data structure based on First In First Out (FIFO): the first added element is the first to leave (e.g. a bank queue). It also has two basic operations: insert (add an element to the end of the queue) and remove (remove and return the first element of the queue).

Implementation

Let’s use the following implementation of a stack in Python (don’t worry if you don’t know Python, it should be possible to get the overall idea):

class Stack(object):
    def __init__(self):
        self.elements = []

    def push(self, element):
        self.elements.append(element)

    def pop(self):
        return self.elements.pop()

    def empty(self):
        return len(self.elements) == 0

I added an extra function empty to tell us if the stack is empty or not. Now, to the implementation of the queue with two stacks:

class Queue(object):
    def __init__(self):
        self.normal = Stack()
        self.inverted = Stack()

    def insert(self, element):
        transfer(self.inverted, self.normal)
        self.normal.empilha(elemento)

    def remove(self):
        transfer(self.normal, self.inverted)
        return self.inverted.pop()

    def empty(self):
        return self.normal.empty() and self.inverted.empty()

def transfer(origin, destination):
    while (not origing.empty()):
        destination.push(origin.pop())

Explanation

The “trick” is to use one stack as the normal queue and the other as the inverted queue. After any operation all elements are either in the normal or in the inverted stacks, thus at least one of the stacks is always empty. This invariant is essential for our implementation to work correctly. Let’s explain each function.

The auxiliary function transfer pops all elements from origin and pushes them, in order, to destination. Assuming one of the stacks is empty we have two cases:

1. The stack origin is empty: nothing happens.
2. The stack destination is empty: the elements in origin are removed from the last to the first and added in this order into the destination stack. In other words, the origin stack is inverted in the destination stack.

We can interpret that the function transfer always inverts the elements in origin and stores them in destination. Note that at the end of this operation the origin stack is always empty, so the invariant that at least one of the stacks are empty still holds.

The function insert must add an element to the end of the queue. The function push inserts an element at the end of a stack. We just need to push the new element to the normal stack. Again, considering our invariant, we have two cases:

1. The inverted stack is empty: the function transfer doesn’t do anything and all elements are already in order in the normal stack.
2. The normal stack is empty: the function transfer inverts the inverted stack (thus, applying the correct order) and adds it to the normal stack.

In both cases, after the call to transfer the inverted stack is empty and the normal stack contains all elements. The new element is added to the end of the normal stack and the invariant still holds.

Finally, the function remove must remove the first element of the queue. This is the reason we have a stack that stores the inverted queue, because popping the last element of the inverted queue is the same as removing the first element of the non-inverted queue. Now we want to make sure the elements are in the inverted stack. For this we invert and transfer the elements from the normal to inverted stack. According to our invariant we have, one more time:

1. The inverted stack is empty: the function transfer inverts the normal stack and transfers the elements to the inverted stack.
2. The normal stack is empty: the function transfer doesn’t do anything.

The last element in the inverted stack (first element of the queue) is then removed and the invariant still holds. As the function empty doesn’t change any of the stacks and in the initial condition both stacks are empty, the invariant is always true.

Simulation

To help understanding the algorithm, let’s see a simulation. Let’s insert the numbers from 0 to 4 into the queue. After the third element we will remove an element immediately after it is added.

We initially insert the numbers 0, 1, and 2 into the queue. As the inverted (I) stack is empty, they are simply pushed to the normal queue (N):

As we remove an element, all elements in the normal queue are transfered to the inverted queue

then the last element is removed (popped).

The first element that was added, the number 0, was removed. Let’s now insert the numbers 3 and 4. For this the elements in the inverted stack are transfered back to the normal stack

and the new elements are inserted (pushed) into the end of the normal stack. The elements in the inverted stack should be transfered to the normal stack, however the inverted stack is already empty, so we will ignore this step

Let’s now remove all elements until the queue is empty. For this we will once again transfer the elements from the normal stack to the inverted stack

then we pop all elements from the last to the first

If we revisit the simulation we will see that the elements were removed from the queue in the same order they were inserted, thus we have a FIFO.

This is our implementation of a queue with two stacks. Can you implement a stack with two queues?