题目:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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(双端队列)来模拟一个栈,只要是标准的栈操作即可。
答案:
新建两个栈s1,s2,其中s1是真正的放元素的栈,s2是辅助操作
因为队列是先进先出,所以要保证s1里每次新增元素时,把它放到最底下,原来的在上面,这样就能保证先进先出.
具体方案:
对于入队:把新元素放进s1之前,先一次把s1里面原来的元素挪到s2里暂存一下,也就是第一个循环干的事情.然后放入新元素.然后再把s2里面的挪回来.
每次新增元素都这么干,就意味着后放入的元素在最底下.先放的元素在上面.
对于查看队首元素,也就是看s1栈顶是啥元素,直接调用s1.peek()即可
对于出队,就是弹出s1栈顶元素,直接调用s1.pop()
class MyQueue {private Stack<Integer> s1 = new Stack<>();private Stack<Integer> s2 = new Stack<>();public MyQueue() {}public void push(int x) {while(!s1.isEmpty()){s2.push(s1.pop());}s1.push(x);while(!s2.isEmpty()){s1.push(s2.pop());}}public int pop() {return s1.pop();}public int peek() {return s1.peek();}public boolean empty() {return s1.isEmpty();} }