Implement stacks with queues

Category Difficulty Likes Dislikes
algorithms Easy (59.63%). 61 –
Tags

stack | design

Companies

Use queues to implement the following operations on the stack:

  • Push (x) — element X is pushed
  • Pop () — Removes the top element of the stack
  • Top () — Gets the top element on the stack
  • Empty () — Returns whether the stack is empty

Note:

  • You can only use the basic operations of the queue — i.epush to back.peek/pop from front.size, andis emptyThese operations are legal.
  • Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.
  • You can assume that all operations are valid (for example, no pop or top operations are called on an empty stack).
/* * @lc app=leetcode.cn id=225 lang=javascript * * [225] Implement stack with queue */
/** * 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() {};/** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() * /
Copy the code

1

So this is the order of the queue, and let’s see if it’s the order of the stack

If each element we add is “at the bottom of the stack “, then we can simply exit the queue in the future

So how do we implement this reverse order addition?

MyStack.prototype.push = function (x) {
	const tempQueue = [x]
	while (this.queue.length) {
		tempQueue.push(this.queue.shift())
	}
	this.queue = tempQueue
};
Copy the code
/* * @lc app=leetcode.cn id=225 lang=javascript * * [225] Implement stack with queue */
/** * Initialize your data structure here. */
var MyStack = function () {
	this.queue = []
};

/** * Push element x onto stack. * @param {number} x * @return {void} */
MyStack.prototype.push = function (x) {
	const tempQueue = [x]
	while (this.queue.length) {
		tempQueue.push(this.queue.shift())
	}
	this.queue = tempQueue
};

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

/** * Get the top element. * @return {number} */
MyStack.prototype.top = function () {
	return this.queue[0]};/** * Returns whether the stack is empty. * @return {boolean} */
MyStack.prototype.empty = function () {
	return !this.queue.length
};

/** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() * /
Copy the code