Saturday 13 July 2013

Algorithm: Implement a queue using 2 stacks

Problem

Implement a queue using two stacks.

Analysis

A queue can actually be implemented using a single stack, this method makes use of recursion however which makes uses another stack of sorts, the call stack. This method involves popping each item off the queue and then recursively calling itself until the last element is found, on the way back down the call stack we push the items back on to the stack.

queuepop()
  value ← stack.pop()
  if stack is empty
    return value
  else
    result ← queuepop()
    stack.push(value)
    return result

This isn't very efficient though considering that the pop function is \(O(n)\), we can do better.

So how can we make use of the second stack to better the running time of the algorithm? Think about what a stack and a queue actually is, if we have a stack and reverse it, it will be in the order in which a queue would serve it up.

Push orderPop order
Stack 1, 2, 3, 4 4, 3, 2, 1
Queue 1, 2, 3, 4 1, 2, 3, 4
Reversed stack 4, 3, 2, 1 1, 2, 3, 4

Luckily reversing a stack into another stack is a very trivial task; just transfer the elements of the first stack to the second stack. This is what's happening in the above "single stack" implementation. If there are two stack data structures available instead of the temporary call stack, the second stack can be used to cache the next \(n\) elements. Any new items added can just be pushed on to the first stack.

This method maintains two stacks, a good analogy of this process is to consider the first stack the "inbox" and the second stack the "outbox". When items are transferred from the inbox to the outbox, no more will be added until the outbox has been completely emptied.

Pseudocode

function queuepush (obj)
  stack1.push(obj)

function queuepop ()
  if stack2 is empty
    if stack1 is empty
      return null
    while stack1 is not empty
      stack2.push(stack1.pop())
  return stack2.pop()

Complexity

The push function is just a simple push on to the first stack which is \(O(1)\). The pop function's worst case will still be \(O(n)\), but only when the second stack is empty. If the second stack contains items however then the algorithm is \(O(1)\).

Code

View on GitHub

class StackQueue<T> {
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();

    void push(T obj) {
        s1.push(obj);
    }

    T pop() {
        if (s2.isEmpty()) {
            if (s1.isEmpty()) {
                return null;
            }
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}