1. Title Description

You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, POP, peek, empty) :

Implement MyQueue class:

  • Void push(int x) pushes element X to the end of the queue
  • Int pop() removes and returns the element from the beginning of the queue
  • Int peek() returns the element at the beginning of the queue
  • Boolean empty() Returns true if the queue is empty; Otherwise, return false

Description:

  • You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are 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.

Advanced:

  • Can you implement queues with O(1) amortized time per operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take a long time.

Example:

Input: [" MyQueue ", "push" and "push" and "peek", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 1, 1, false] MyQueue MyQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return falseCopy the code

Tip:

  • 1 <= x <= 9
  • Push, POP, peek, and Empty are called up to 100 times
  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK)

Second, train of thought analysis

Let’s start with the difference between stack and queue:

  • Stack: First in last out (last in first out)
  • Queue: First in, first out
  • Push: all are added to the end, adding 1, 2 and 3 successively
  • Pop: the stack removes and returns the trailing element 3, the queue removes and returns the leading element 1

After this comparison, it turns out that the difficulty of implementing a queue with a stack is getting the elements out of the bottom of the stack.

Every time we fetch an element, we need to fetch it from the bottom of the stack, which is exactly the reverse of the unstack operation.

We use another stack to store the elements in reverse order, and then go to this stack each time:

Maintain such a reverse stack:

  • Push to Stack1 when elements are normally imported
  • Check if STACK2 is empty before fetching the element:
    • When Stack2 is empty, elements in Stack1 are reversed into Stack2 and pop from Stack2
    • Pop directly from Stack2 when stack2 is not empty

With peek() : pop() implemented, it’s easy to implement peek() :

Peek () differs from pop() in that peek does not push the value off the stack.

Empty: Check whether the two stacks are empty.

AC code

/** * Initialize your data structure here. */ var MyQueue = function() { this.stack1 = []; this.stack2 = []; }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { this.stack1.push(x); }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = Function () {if(this.stack2.length <= 0){// If (this.stack1.length > 0){// If (this Push (this.stack2.push(this.stack1.pop())); } } return this.stack2.pop(); / / the stack}; /** * Get the front element. * @return {number} */ MyQueue.prototype.peek = function() { if(this.stack2.length <= While (this.stack1.length > 0){// Add stack1 to stack2 if stack2 is empty. Stack2. push(this.stack1.pop()); } } return this.stack2.length && this.stack2[this.stack2.length - 1]; // return the top element}; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function() { return ! this.stack1.length && ! this.stack2.length; }; /** * 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() * /Copy the code

Four,

  • Stack: fifin last out, queue: fifin first out; The queue fetches elements in reverse order of the stack, so a reverse stack is maintained.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign