problem address
Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. Example: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false Notes: You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).题目要求用栈实现队列, 有些人用一个列表当然也可以 用两个栈实现队列要注意:
栈2不为空直接pop否则把栈1所有元素放到栈2，然后执行栈2pop操作 在这里栈2是按照队列的顺序的，所以有值肯定可以pop,步骤你也可以把栈1剩下一个元素，其余放到栈2，这样直接pop栈1的就行. from collections import deque class Stack: def __init__(self): self.items = deque() def push(self, val): return self.items.append(val) def pop(self): return self.items.pop() def top(self): # 返回栈顶值 return self.items[-1] def len(self): return len(self.items) def empty(self): return len(self.items) == 0 class MyQueue: def __init__(self): """ Initialize your data structure here. """ self.s1= Stack() self.s2 = Stack() def push(self, x: int) -> None: """ Push element x to the back of queue. """ self.s1.push(x) def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ if not self.s2.empty(): return self.s2.pop() while not self.s1.empty(): val = self.s1.pop() self.s2.push(val) return self.s2.pop() def peek(self) -> int: """ Get the front element. """ if not self.s2.empty(): return self.s2.top() while not self.s1.empty(): val = self.s1.pop() self.s2.push(val) return self.s2.top() def empty(self) -> bool: """ Returns whether the queue is empty. """ return self.s1.empty() and self.s2.empty()