If you want to see how to implement a stack using queues with the costly pop or costly push method, 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 dish 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.
This post will explain how using only one queue. There are other ways to do this, mainly the costly pop and costly push methods. Both of those explanations are linked above.
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. Let’s start with what we do know — this has to be done with a queue. Let’s instantiate a new queue in the constructor.
var MyStack = function() {
this.queue = 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 will fall in place.
/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {};Ok, so this method adds an element to the stack, but we need it do a little more than that. Not only can we implement it, we can implement it in a way that ensures that the last element added is the first one removed, which is stack-like behavior. But how can we do this? Doesn’t the queue remove the element at the bottom first? Yes, but after we add an element, we can remove all of the elements below it and move them on top of it. That way, the element we just added is always at the bottom of the queue. It would look something like this. Imagine we have a queue with two elements in it. Element 1 is at the bottom, followed by element 2.
2
1Now we want to add element 3. We do so as usual. I’ll add asterisks around it to make it easier to see.
*3*
2
1Then we rotate the array by the number of elements that were in the queue before the number 3 was added. There were two elements in it before, so we rotate it two times.
Rotation one:
1
*3*
2And then rotation two:
2
1
*3*Now when we want to remove an element, look at what’s being removed. It’s the number 3, the last element we added, just like a stack!
The code for that looks like this:
MyStack.prototype.push = function(x) {
let rotations = this.queue.size();
this.queue.enqueue(x);
while (rotations > 0) {
this.queue.enqueue(this.queue.dequeue());
rotations--;
}
};Like I mentioned before, the rest of the methods are straightforward.
Let’s go to the pop() method.
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {};In a stack, the pop() method, removes the element at the top of the pile (the last element added). In a queue(), it removes the element at the bottom of the pile. But since we implemented the push() method in a way where the last element added *is* at the bottom of the pile, all we have to do now is use the queue’s standard method to remove an element, which is called dequeue();
MyStack.prototype.pop = function() {
return this.queue.dequeue();
};Next, we go to the top() method.
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {};In a stack, the top() method is pretty much the same as the pop() method, except it doesn’t actually remove anything. It simply shows you what is at the top of the stack, aka the last element added. Well, again, since we created the push() method in such a way where the last element added is at the bottom of the queue, all we have to do is use the standard queue peek() method, which shows you the next element that would be removed from the queue (if you wanted to).
MyStack.prototype.top = function() {
return this.queue.peek();
};Finally, we get to the empty() method.
/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function() {};This doesn’t do anything special. It just shows us if the stack is empty. Since we’re using a queue instead of a stack, we can use the queue’s isEmpty() method.
MyStack.prototype.empty = function() {
return this.queue.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.queue = new Queue();
};
/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
let rotations = this.queue.size();
this.queue.enqueue(x);
while (rotations > 0) {
this.queue.enqueue(this.queue.dequeue());
rotations--;
}
};
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
return this.queue.dequeue();
};
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {
return this.queue.peek();
};
/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return this.queue.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/