Implement Queue Using Stacks | LeetCode 232

In this question, we need to create a queue, but we’re only allowed to use stacks to do so. Both stacks and queues add elements in the same order.

I highly suggest reading the explanation and implementation of stacks here if you don’t have a good grasp of them already.

So what’s the difference between a stack and a queue? Stacks are LIFO, which stands for Last In First Out. This means that the last element to be added to it is the first to be removed. Think of it like a stack of plates. Even though the first plate may have been added days ago, the first one you’ll wash is the one at the top. Queues, on the other hand, are FIFO, which stands for First In First Out. The first element added to the queue will be the first one removed. Think of it like standing in line at a grocery store. The first customer in line is the first to be helped. The meat of this question is how to make a stack, which removes the last element added first, behave like a queue, which removes the oldest element added first.

Just remember that a queue removes the newest element added and a stack removes the oldest element added. But how do we get a stack to behave like a queue when the oldest element added is at the bottom of the queue and we can only remove the element at the top? Simple. By moving the elements in the first stack into a second stack in the reversed order, giving us access to the oldest elements first.

Ok, so as we just mentioned, the way to do this is by using two stacks. We’ll call them the push stack and the pop stack. By the way, push means add and pop means remove. Any time we add an element, we add it to the push stack. Every time we remove an element, it is removed from the pop stack.

But how do any elements get into to the pop stack if they’re always added to the push stack? Any time we want to remove an element, we first check if the pop stack is empty. If it is, we remove *all* of the elements in the push stack into the pop stack and then we pop (remove) the element off the top of it.

Example of push method (pushing two elements):
  | |   | | // both stacks are initially empty


  |2|   | |
  |1|   | |

Notice that the elements are only added to the first stack.



Example of pop method:
  |2|    | | // stack one initially has two elements
  |1|    | |
First, remove all elements from the push stack into the pop stack.
  | |    | |
  |1|    |2| // element 2 is removed from the push stack and added to the pop stack


  | |    |1| // element 1 is removed from the push stack and added to the pop stack
  | |    |2|


  | |    |2| // element 1 is removed from the pop stack since it is at the top

Now, to the code. Let’s start with the skeleton provided by LeetCode.

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.pushStack = new Stack();
    this.popStack = new Stack();
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {};

That’s a lot of methods we need to create, but don’t be intimidated. We know we need to use two stacks, one called pushStack and one called popStack, so let’s start by adding them to the constructor.

var MyQueue = function() {
    this.pushStack = new Stack();
    this.popStack = new Stack();
};

Now to the methods. Let’s begin with the push() method to get it out of the way. All we have to do is push the element to the push stack.

MyQueue.prototype.push = function(x) {
    this.pushStack.push(x);
};

Now, we can move to the pop() method. As we mentioned earlier, before we pop anything off of the pop stack, we first have to make sure it’s not empty since you can’t remove any elements if there aren’t any there.

MyQueue.prototype.pop = function() {
    if (this.popStack.empty()) {}
};

Then we make a loop inside of that if statement. This loop takes every element from the push stack and adds it to the pop stack.

MyQueue.prototype.pop = function() {
    if (this.popStack.empty()) {
        while (!this.pushStack.empty()) { // stop when all elements from the push stack have been removed
            this.popStack.push(this.pushStack.pop()); // pop the element off of the push stack and add it to the pop stack
        }
    }
};

Now that every element has been moved into the pop stack in reverse order, we can simply remove the top element from the pop stack and return its value.

MyQueue.prototype.pop = function() {
    if (this.popStack.empty()) {
        while (!this.pushStack.empty()) {
            this.popStack.push(this.pushStack.pop());
        }
    }
    
    return this.popStack.pop(); // remove and return the element at the top of the pop stack
};

See? That wasn’t too bad. We can move onto the peek() method, which is very similar to the pop() method. The only difference is the last thing it does is simply look at the element at the pop stack and return its value. *It does not remove it.*

MyQueue.prototype.peek = function() {
    if (this.popStack.empty()) {
        while (!this.pushStack.empty()) {
            this.popStack.push(this.pushStack.pop());
        }
    }
    
    return this.popStack.peek(); // this is the only difference between this and the pop method
};

Finally, we can implement the empty() method. This just returns whether the queue is empty. Since our queue consists of two stacks, we have to return whether both stacks are empty. If either stack is not empty, the queue is not empty.

MyQueue.prototype.empty = function() {
    return this.popStack.empty() && this.pushStack.empty();
};

And that’s it! The full implementation is at the bottom of this page, but if you want to support us and are interested in the resources we use to make this content, check out the links below.

AFFILIATE LINKS

Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

Last, but not least, here is the full implementation.

var MyQueue = function() {
    this.pushStack = new Stack();
    this.popStack = new Stack();
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.pushStack.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if (this.popStack.empty()) {
        while (!this.pushStack.empty()) {
            this.popStack.push(this.pushStack.pop());
        }
    }
    
    return this.popStack.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if (this.popStack.empty()) {
        while (!this.pushStack.empty()) {
            this.popStack.push(this.pushStack.pop());
        }
    }
    
    return this.popStack.peek();
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.popStack.empty() && this.pushStack.empty();
};



class Stack {
  constructor() {
    this.storage = {};
    this.size = 0;
  }

  push(val) {
    this.storage[this.size] = val;
    this.size++;
  }

  pop() {
    let top = this.storage[this.size - 1];
    this.size--;
    delete this.storage[this.size];
    return top;
  }

  peek() {
    return this.storage[this.size - 1];
  }

  empty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }
}