requirements

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

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)

The core code

class MyQueue:

    def __init__(self) :
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) - >None:
        self.stack1.append(x)

    def pop(self) - >int:
        if not self.stack2:
            while self.stack1:
                tmp = self.stack1.pop()
                self.stack2.append(tmp)
        res = self.stack2.pop()
        return res

    def peek(self) - >int:
        if not self.stack2:
            while self.stack1:
                tmp = self.stack1.pop()
                self.stack2.append(tmp)
        return self.stack2[-1]

    def empty(self) - >bool:
        return not self.stack1 and not self.stack2

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
Copy the code

Answer: We use two stacks to complete a fifO queue. Note the pop operation and peek operation. We pop the elements that are pushed into stack1 from append to Stack2, so as to achieve the first entry at the end of the stack. Completed the overall design.