Google 美国面经：用栈实现队列
G 家不看重解出最优解，更看重代码优化的思路，有时候不解出答案，但面试官看到了你优秀的代码逻辑，也能直接拿到 strong hire 。
关于面试，G 家一般是 4 轮算法+1 轮 BQ，偶尔会考到系统设计，算法比较少考原题，考原题也不是做出来就能过……
今年 HC 很少！今年 HC 很少！不要报太大期望，且败且战，不要太气馁。
写到最后时间不多，其实面试官没啥 follow up 问我，最后问了一下复杂度和有没有什么优化方法。
题目：
正如标题所述，你需要使用两个栈来实现队列的一些操作。
队列应支持 push(element)，pop() 和 top()，其中 pop 是弹出队列中的第一个(最前面的)元素。 pop 和 top 方法都应该返回第一个元素的值。
在线做题地址
例 1:
输入: push(1) pop() push(2) push(3) top() pop() 输出: 1 2 2 例 2:
输入: push(1) push(2) push(2) push(3) push(4) push(5) push(6) push(7) push(1) 输出: [] 解题思路
先考虑只有一个栈的时候，由于栈的先入后出特性 FILO，栈中的元素的顺序是反的，我们无法直接访问栈底的元素。但是当把 1 号栈中所有元素依次弹出并压入到 2 号栈中，2 号栈顶的元素就变成了原来 1 号栈的栈底，即正序。所以我们要提取元素时，只需从 2 号栈提取即可。
但是由于 2 号栈中栈顶元素是最先加入队列的元素，所以只有当 2 号栈为空时，才能将 1 号栈中所有元素加入到 2 号栈中。
举例说明：
首先我们有一个主要栈 stack1：[1,2,3) ，以下所有栈的表示方式中，圆括号 ‘)’ 均为栈顶。 那么 stack1 的出栈顺序为 3-2-1，其中 1 为我们要找到的元素，也就是队首。
我们需要借助一个辅助栈 stack2：[)，将 stack1 中的元素依次放到 stack2 中：stack2 [3,2,1)。这时我们发现 stack2 的栈顶就是我们要找的元素，弹出即可。
此时我们再向主要栈 stack1 中压入 4 和 5 。两个栈状态：stack1 [4,5) 、stack2 [3,2)。 现在我们需要队首的话，应该先弹出辅助栈 stack2 的栈顶。
如果此时辅助栈空，我们就要执行之前转移的操作，将 stack1 的所有元素压入 stack2，然后弹出 stack2 的栈顶即可。
代码思路
定义 move()，操作是将元素从 1 号栈转移到 2 号栈。当要提取元素，且 2 号栈为空时，调用 move()。
复杂度分析
时间复杂度
- 每个元素最多会别 push，pop，move 一次，每个操作的均摊时间复杂度为 O(1)。
空间复杂度
- 假设一共操作了 N 次 push，空间复杂度为 O(N)。
public class MyQueue { public MyQueue() { // do intialization if necessary } /* * @param element: An integer * @return: nothing */ public void push(int element) { stack1.push(element); } /* * @return: An integer */ public int pop() { if (stack2.isEmpty()) { move(); } return stack2.pop(); } /* * @return: An integer */ public int top() { if (stack2.isEmpty()) { move(); } return stack2.peek(); } // 将 1 号栈中的元素移动到 2 号栈中 private void move() { while (! stack1.isEmpty()) { stack2.push(stack1.pop()); } } private Stack<Integer> stack1 = new Stack<>(); private Stack<Integer> stack2 = new Stack<>(); }