Implement Stack Using Queues | LeetCode 225 (Costly Pop)

If you want to see how to implement a stack using two queues with the costly push method or just one queue, click here and here.

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

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

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 queue, which removes the first element added first, behave like a stack, which removes the last element 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 queue to behave like a stack when the newest element added is at the top of the queue and we can only remove the element at the bottom? Simple. By moving the element at the top of the queue to the bottom of the queue.

This post will explain how using the costly pop method, which uses two queues, with most of the work being done in the pop() method. There are other ways to do this, mainly the costly push method and with only one queue. Both of those explanations are linked above.

Ok, so as we just mentioned, the way to do this is by using two queues. We’ll call them the primary queue and the secondary queue. Then what?

Primary Secondary
an element
another element

When we add an element, we add it to the primary queue as normal.

Primary Secondary
newest element
an element
another element

Remember that the goal is to position the newest element so that it is the next to be removed. For a queue, that means it has to be at the bottom.

Here’s how that’s done. We remove all of the elements in the primary queue and add them to the secondary queue, *except for the last element added*.

Primary Secondary
newest element another element
an element

Primary Secondary
newest element an element
another element

After doing this, we’ve successfully positioned the element we just added to the bottom of the queue, which is where elements are removed from queues. To demonstrate removing the last element added:

Primary Secondary
an element
another element

And then switch the queues.

Primary Secondary
an element
another element

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

/**
 * Initialize your data structure here.
 */
var MyStack = function() {};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.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 queues, so let’s start by adding them to the constructor.

var MyStack = function() {
    this.primaryQueue = new Queue();
    this.secondaryQueue = new Queue();    
};

Now to the methods. Let’s begin with the push() method to get it out of the way. Here’s the skeleton.

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {};

As we mentioned earlier, any new element is added to the primary queue. The way to add elements to a queue is using enqueue().

MyStack.prototype.push = function(x) {
    this.primaryQueue.enqueue(x);
};

Now let’s move on to the pop() method. This is where all the real work is done to move the last element added to the bottom of the queue, thereby mimicking a stack. Here’s the skeleton.

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {};

Remember that we need to remove every element in the primary queue into the secondary queue, except for the last one added. To remove an element from a queue, use its dequeue method.

while (this.primaryQueue.size() > 1) {
    this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
}

Then we remove element we just added to the primary queue, and at the same time keeping a reference to its value. This is important because this method not only needs to remove the last element added, but also return its value.

let bottom = this.primaryQueue.dequeue();

We’re getting closer to the end of this method. Now we need to swap the two queues. If you need a reminder of why, see the illustration above.

let temp = this.secondaryQueue;
this.secondaryQueue = this.primaryQueue;
this.primaryQueue = temp;

And, finally, we return the value of the element we removed.

return bottom;

Here is the full pop() method.

MyStack.prototype.pop = function() {
  while (this.primaryQueue.size() > 1) {
    this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
  }

  let bottom = this.primaryQueue.dequeue();

  let temp = this.secondaryQueue;
  this.secondaryQueue = this.primaryQueue;
  this.primaryQueue = temp;

  return bottom;
};

Moving on to the top() method. Here is the skeleton.

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {};

It is very similar to the pop() method, except instead of removing the element we just added, we just need to move the other elements from below it so that we can get its value. Here’s how that goes.

First, just like in the pop() method, we remove the elements from below it and onto the secondary queue.

while (this.primaryQueue.size() > 1) {
    this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
}

Then we get a reference to its value by using the queue’s peek() method. This differs from the pop() method because in that, we removed the element, but in this method, we’re just getting a reference to its value.

let bottom = this.primaryQueue.peek();

Now, we move it to the secondary queue so that the elements right back in the same order that they were in in the primary queue.

this.secondaryQueue.enqueue(this.primaryQueue.dequeue());

Then we swap the queues so that everything looked like it did before, with the primary queue containing the elements and the secondary queue being empty.

let temp = this.secondaryQueue;
this.secondaryQueue = this.primaryQueue;
this.primaryQueue = temp;

And, finally, we return the value of the last element added, which was the entire point of this method.

return bottom;

Here is the full top() method.

MyStack.prototype.top = function() {
  while (this.primaryQueue.size() > 1) {
    this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
  }

  let bottom = this.primaryQueue.peek();
  this.secondaryQueue.enqueue(this.primaryQueue.dequeue());

  let temp = this.secondaryQueue;
  this.secondaryQueue = this.primaryQueue;
  this.primaryQueue = temp;

  return bottom;
};

The last method to complete is the empty() method. Here is its skeleton.

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

Since all of our elements are in the primary queue, we can just use its isEmpty() method.

MyStack.prototype.empty = function() {
    return this.primaryQueue.isEmpty();
};

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 MyStack = function() {
    this.primaryQueue = new Queue();
    this.secondaryQueue = new Queue();    
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
  this.primaryQueue.enqueue(x);
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
  while (this.primaryQueue.size() > 1) {
    this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
  }

  let bottom = this.primaryQueue.dequeue();

  let temp = this.secondaryQueue;
  this.secondaryQueue = this.primaryQueue;
  this.primaryQueue = temp;

  return bottom;
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
  while (this.primaryQueue.size() > 1) {
    this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
  }

  let bottom = this.primaryQueue.peek();
  this.secondaryQueue.enqueue(this.primaryQueue.dequeue());

  let temp = this.secondaryQueue;
  this.secondaryQueue = this.primaryQueue;
  this.primaryQueue = temp;

  return bottom;
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
  return this.primaryQueue.isEmpty();
};


class Queue {
  constructor() {
    this.top = 0;
    this.bottom = 0;
    this.storage = {};
  }

  enqueue(val) {
    this.storage[this.top] = val;
    this.top++;
  }

  dequeue() {
    let removedElement = this.storage[this.bottom];
    delete this.storage[this.bottom];
    this.bottom++;
    return removedElement;
  }

  peek() {
    return this.storage[this.bottom];
  }

  size() {
    return this.top- this.bottom;
  }

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

Link to problem on LeetCode: https://leetcode.com/problems/implement-stack-using-queues/