Leetcode 232. Implementing queues with stacks, difficulty: Easy. The original problem is here.

Topic describes

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) :

Void push(int x) pushes element x to the end of the queue int pop() removes the element from the beginning of the queue and returns the element 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 1:

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
  • A maximum of 100 callspush,pop,peek 和 empty
  • Assume that all operations are valid (for example, an empty queue is not calledpoporpeekOperation)

Thought analysis

The stack is a FIFO data structure, while the queue is a FIFO data structure. Using a stack to simulate the FIFO feature of queues requires the assistance of another stack. Push pushes elements into inStack, and when pop is needed, pushes all of the inStack elements into the outStack so that the order of the data is reversed enough to satisfy the nature of a queue POP. Similarly, peek is the last element in the outStack. To do this, you need an auxiliary function, in2Out(), to push the inStack data into the outStack. Since there are two stacks, it is necessary to determine whether inStack and outStack are both empty.

The time complexity of push and Empty in this solution is O(1), while pop and peek are amortized O(1). In terms of time complexity, what is amortized complexity?

AC code

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

conclusion

答 案 :

  • 225. Implement stacks with queues

Techniques used

  • How JS uses classes and methods, the sample code uses a mixture of constructors and prototypes.
  • Since JS has no queue and stack data structures, arrays are used to simulate stacks in this case.
  • Pay attention topeekMethod, although it returns the beginning of the queue, foroutStackBoth are top of the stack elements, but different frompopMethod, which does not need to delete the value in the original data structure, so the operation used isreturn this.outStack[this.outStack.length - 1];Rather thanthis.outStack.pop().

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