Grind 75 Question 14: Implement Queue Using Stacks
Well, I do need more practice with queues and stacks…
The Problem
mplement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x)Pushes element x to the back of the queue.int pop()Removes the element from the front of the queue and returns it.int peek()Returns the element at the front of the queue.boolean empty()Returnstrueif the queue is empty,falseotherwise.
Notes:
- You must use only standard operations of a stack, which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.
The Initial Attempts
Well, I’m utterly baffled by what “standard” operations of a stack are, so it looks like I’ve got some Googling/Neetcode-watching to do. It needs me to write five functions, and I just feel like…what? This is supposed to be easy?
I don’t know exactly what I’m doing, but I write the most basic of functions and see if anything runs:
var MyQueue = function() {
const stack = [];
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
return stack.push(x);
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
const frontOfQueue = stack[0];
stack.splice(0, 1);
return frontOfQueue;
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
const frontOfQueue = stack[0];
return frontOfQueue;
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
if stack.length == 0 return true;
return false;
};
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = new MyQueue()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/Of course it doesn’t work, because each function can’t communicate with the main myQueue function. I tinker around some more — no use even sharing what I’ve done, because it’s messy and still doesn’t budge. Help me, Neetcode! You’re my only hope.
The Solution
I don’t like this problem. #grumpy. But also. OMG I was on the right track! I just needed to be using this.stack! Once I figured out my syntax issues, it all followed fairly quickly, and I was gobsmacked when my initial code fix ran and was accepted.
var MyQueue = function() {
this.stack = []
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.stack.push(x);
return this.stack;
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
const frontOfQueue = this.stack[0]
this.stack.splice(0, 1);
return frontOfQueue;
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
return this.stack[0]
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return this.stack.length == 0;
};
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = new MyQueue()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/It’s barely even worth going over, but I will anyway. MyQueue is a new array, that’s all. For the push function, you just push it into the stack array. For pop, you create a variable that’s the front of the queue (or bottom of the stack, depending on how you want to look at it), splice out the first element, and return the variable. For peek, you just return that first element, and for empty, you just return the boolean of whether it has any length or not. Boom done.
What I Learned
- The biggest, most important thing is how to use this. I’ve seen it used in Leetcode questions before, but have never used it myself. I guess it’s just a way of communicating between functions. I was always super intimidated by this.props.whatever in React, but I suppose it’s not too much different. I dunno. I’m getting it. I’m getting it!
Onward to the second question of Week 2!
mins
read
