leetCode The first 232 topic Using stack to realize queue
link ：https://leetcode-cn.com/problems/implement-queue-using-stacks
Please use only two stacks to implement the FIFO queue . The queue should support all operations supported by the general queue （push、pop、peek、empty）：
Realization MyQueue class ：
void push(int x) Put the element x Push to the end of the queue
int pop() Remove from the beginning of the queue and return the element
int peek() Returns the element at the beginning of the queue
boolean empty() If the queue is empty , return true ; otherwise , return false
explain ：
You can only Use standard stack operations —— It's just push to top, peek/pop from top, size, and is empty Operation is legal .
The language you use may not support stacks . You can use list perhaps deque（ deque ） To simulate a stack , As long as it's a standard stack operation .
Example 1：
Input ：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output ：
[null, null, null, 1, 1, false]
explain ：
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 false
Tips ：
1 <= x <= 9
Call at most 100 Time push、pop、peek and empty
Suppose all operations are valid （ for example , An empty queue will not call pop perhaps peek operation ）
Advanced ：
Can you realize the time sharing of each operation? The complexity is O(1) Queues ？
let me put it another way , perform n The total time complexity of operations is O(n) ,
Even if one of the operations may take a long time .
Stack is first in first out
The queue is first in, first out
This can be achieved with two stacks , Push input onto input stack , When you want pop perhaps peek First judge whether the output stack is empty , If it is empty, the elements of the input stack will be pushed out of the input stack at one time , While pressing the output stack ; If it's not empty , Then the stack is directly output from the output stack . When all the elements are out , Press the input stack in again .
The condition for judging that the queue is empty is that both stacks must be empty .
## python3
class MyQueue:
def __init__(self):
self.inStack = []
self.outStack = []
def push(self, x: int) -> None:
self.inStack.append(x)
def pop(self) -> int:
if len(self.outStack) == 0 : ## If the output stack is empty , Then export all the elements of the input stack and push them into the output stack
self.outStack[:] = self.inStack[::-1]
self.inStack = []
x = None
if len(self.outStack) > 0: ## If after pressing the stack , Output is not empty , There are elements that can pop
x = self.outStack.pop() ## If it is still empty, it returns None
return x
def peek(self) -> int:
if len(self.outStack) == 0: ## If the output stack is empty , Then export all the elements of the input stack and push them into the output stack
self.outStack[:] = self.inStack[::-1]
self.inStack = []
x = None
if len(self.outStack) > 0 :
x = self.outStack[-1]
return x
def empty(self) -> bool:
return len(self.inStack) == 0 and len(self.outStack) == 0
