[topic address]

Implement a MyQueue class that uses two stacks to implement a queue.

Example:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // Return 1 queue.pop(); // Return 1 queue.empty(); / / returns falseCopy the code

Description:

  • You can only use standard stack operations — that is, onlypush to top.peek/pop from top.size 和 is emptyThe operation is legal.
  • Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.
  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK).

Let’s simulate a queue with two stacks

The nature of the queue is FIFO

The nature of the stack is FILO

In this case, only two stacks need to be maintained, one for queue entry and one for queue creation

For push, elements are pushed into the queue, for peek and POP, elements are fetched from the queue

When there are no elements in the queue, each element is ejected from the queue and pushed in and out of the queue, because the stack is advanced and then out, and the element at the top of the queue is the last one to be pushed in. After being pushed in and out of the queue in this order, the element at the top of the queue is the earliest one to be pushed in

The animation is shown below:

The code is as follows:

Var MyQueue = function() {this.stackOut = []; var MyQueue = function() {this.stackOut = []; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { this.stackin.push(x) }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = Function () {// Import all elements from the queue if(! this.stackout.length) while(this.stackin.length){ this.stackout.push(this.stackin.pop()) } return this.stackout.pop(); }; /** * Get the front element. * @return {number} */ myqueue.prototype. peek = function() {// If (! this.stackout.length) while(this.stackin.length){ this.stackout.push(this.stackin.pop()) } return this.stackout[this.stackout.length-1] }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function() { return this.stackin.length===0&&this.stackout.length===0 };Copy the code

This completes leetcode- Interview question 03.04- breaking stacks into queues

If you have any questions or suggestions, please leave a comment!