请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [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 false
提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）
进阶：
- 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
方法一：双栈
使用两个栈，其中栈 stk1用于入队，另一个栈 stk2 用于出队。
入队时，直接将元素入栈 stk1。时间复杂度
出队时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中出栈一个元素。如果栈 stk2 不为空，则直接从栈 stk2 中出栈一个元素。均摊时间复杂度
获取队首元素时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中获取栈顶元素。如果栈 stk2 不为空，则直接从栈 stk2 中获取栈顶元素。均摊时间复杂度
判断队列是否为空时，只要判断两个栈是否都为空即可。时间复杂度
class MyQueue:
def __init__(self):
self.stk1 = []
self.stk2 = []
def push(self, x: int) -> None:
self.stk1.append(x)
def pop(self) -> int:
self.move()
return self.stk2.pop()
def peek(self) -> int:
self.move()
return self.stk2[-1]
def empty(self) -> bool:
return not self.stk1 and not self.stk2
def move(self):
if not self.stk2:
while self.stk1:
self.stk2.append(self.stk1.pop())
# 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()class MyQueue {
private Deque<Integer> stk1 = new ArrayDeque<>();
private Deque<Integer> stk2 = new ArrayDeque<>();
public MyQueue() {
}
public void push(int x) {
stk1.push(x);
}
public int pop() {
move();
return stk2.pop();
}
public int peek() {
move();
return stk2.peek();
}
public boolean empty() {
return stk1.isEmpty() && stk2.isEmpty();
}
private void move() {
while (stk2.isEmpty()) {
while (!stk1.isEmpty()) {
stk2.push(stk1.pop());
}
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/class MyQueue {
public:
MyQueue() {
}
void push(int x) {
stk1.push(x);
}
int pop() {
move();
int ans = stk2.top();
stk2.pop();
return ans;
}
int peek() {
move();
return stk2.top();
}
bool empty() {
return stk1.empty() && stk2.empty();
}
private:
stack<int> stk1;
stack<int> stk2;
void move() {
if (stk2.empty()) {
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
}
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/type MyQueue struct {
stk1 []int
stk2 []int
}
func Constructor() MyQueue {
return MyQueue{[]int{}, []int{}}
}
func (this *MyQueue) Push(x int) {
this.stk1 = append(this.stk1, x)
}
func (this *MyQueue) Pop() int {
this.move()
ans := this.stk2[len(this.stk2)-1]
this.stk2 = this.stk2[:len(this.stk2)-1]
return ans
}
func (this *MyQueue) Peek() int {
this.move()
return this.stk2[len(this.stk2)-1]
}
func (this *MyQueue) Empty() bool {
return len(this.stk1) == 0 && len(this.stk2) == 0
}
func (this *MyQueue) move() {
if len(this.stk2) == 0 {
for len(this.stk1) > 0 {
this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
this.stk1 = this.stk1[:len(this.stk1)-1]
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/class MyQueue {
stk1: number[];
stk2: number[];
constructor() {
this.stk1 = [];
this.stk2 = [];
}
push(x: number): void {
this.stk1.push(x);
}
pop(): number {
this.move();
return this.stk2.pop();
}
peek(): number {
this.move();
return this.stk2[this.stk2.length - 1];
}
empty(): boolean {
return !this.stk1.length && !this.stk2.length;
}
move(): void {
if (!this.stk2.length) {
while (this.stk1.length) {
this.stk2.push(this.stk1.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()
*/struct MyQueue {
in_stack: Vec<i32>,
out_stack: Vec<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyQueue {
fn new() -> Self {
Self {
in_stack: vec![],
out_stack: vec![],
}
}
fn push(&mut self, x: i32) {
self.in_stack.push(x);
}
fn pop(&mut self) -> i32 {
if self.out_stack.is_empty() {
self.fill_out();
}
self.out_stack.pop().unwrap()
}
fn peek(&mut self) -> i32 {
if self.out_stack.is_empty() {
self.fill_out();
}
*self.out_stack.last().unwrap()
}
fn empty(&self) -> bool {
self.in_stack.is_empty() && self.out_stack.is_empty()
}
fn fill_out(&mut self){
let MyQueue { in_stack, out_stack } = self;
if out_stack.is_empty() {
while !in_stack.is_empty() {
out_stack.push(in_stack.pop().unwrap());
}
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* let obj = MyQueue::new();
* obj.push(x);
* let ret_2: i32 = obj.pop();
* let ret_3: i32 = obj.peek();
* let ret_4: bool = obj.empty();
*/