Analysis

A queue can actually be implemented using a single stack. This method makes use of recursion however which 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 order	Pop 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

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

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

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

/**
 * Creates a queue implemented with two stacks.
 * @constructor
 */
function TwoStackQueue() {
  this.inbox = [];
  this.outbox = [];
}

/**
 * Push a value to the queue.
 * @param {*} value The value to push.
 */
TwoStackQueue.prototype.push = function (value) {
  this.inbox.push(value);
};

/**
 * Pops a value from the queue and returns it.
 * @return {*} The popped value.
 */
TwoStackQueue.prototype.pop = function () {
  if (!this.outbox.length) {
    if (!this.inbox.length) {
      return undefined;
    }
    while (this.inbox.length) {
      this.outbox.push(this.inbox.pop());
    }
  }
  return this.outbox.pop();
};

module.exports = TwoStackQueue;

Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.

 

More posts tagged Interview question