If you want to see how to implement a stack using two queues with the costly pop 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 push method, which uses two queues, with most of the work being done in the push() method. There are other ways to do this, mainly the costly pop 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 secondary queue.
Primary Secondary
an element newest 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.
Now, we remove the elements in the primary queue and put them on top of the secondary queue.
Primary Secondary
an element another element
newest element
Primary Secondary
an element
another element
newest element
Then we switch the two queues so that the primary becomes the secondary and vice versa.
Primary Secondary
an element
another element
newest element
Perfect. Now the newest element is at the bottom of the queue, which is how we remove elements in queues. The same steps are used for every element added.
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 most difficult one, the push method. After we’re finished this one, the other methods should fall into place. 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 secondary queue. The way to add elements to a queue is using enqueue().
this.secondaryQueue.enqueue(x);Then we empty out all of the contents in the primary queue (if it has any) into the secondary queue.
while (!this.primaryQueue.isEmpty()) {
this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
}Last, we swap the two queues so that the primary queue is now the secondary queue and vice versa.
let tempQueue = this.secondaryQueue;
this.secondaryQueue = this.primaryQueue;
this.primaryQueue = tempQueue;Here is the complete push() method.
MyStack.prototype.push = function(x) {
this.secondaryQueue.enqueue(x);
while (!this.primaryQueue.isEmpty()) {
this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
}
let tempQueue = this.secondaryQueue;
this.secondaryQueue = this.primaryQueue;
this.primaryQueue = tempQueue;
};Time to move onto the pop() method. Here’s the skeleton.
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {};Since we already set up the push method where every time an element is added, it is moved to the bottom of the queue, all we have to do is remove the bottom element. This is done using the queue’s dequeue() method.
MyStack.prototype.pop = function() {
return this.primaryQueue.dequeue();
};Now, to the top() method. Here’s the skeleton.
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {};Queues have a peek() method that shows the next element to be removed. Since we set up our push() method to move newly-added elements to the bottom of the queue, all we have to do is use this peek() method. *Note that this returns, but does not remove the element.
MyStack.prototype.top = function() {
return this.primaryQueue.peek();
};The final method is just supposed to return whether the stack is empty. Here’s the skeleton.
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.secondaryQueue.enqueue(x);
while (!this.primaryQueue.isEmpty()) {
this.secondaryQueue.enqueue(this.primaryQueue.dequeue());
}
let tempQueue = this.secondaryQueue;
this.secondaryQueue = this.primaryQueue;
this.primaryQueue = tempQueue;
};
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
return this.primaryQueue.dequeue();
};
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {
return this.primaryQueue.peek();
};
/**
* 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/