题解 | #用两个栈实现队列#
用两个栈实现队列
http://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6
算法思想：双栈（此题已明确解题方法即双栈）
解题思路：
借助栈的先进后出规则模拟实现队列的先进先出
1、当插入时，直接插入 stack1
2、当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素
图解：
代码展示：
Python版本
class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if self.stack2 == []: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop()JAVA版本：
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size() <= 0){
while (stack1.size() != 0){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
C++版本: class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
int node = stack2.top();
stack2.pop();
return node;
}
private:
stack<int> stack1;
stack<int> stack2;
}; 复杂度分析：
时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。插入不多说，对于删除操作，虽然看起来是 O(n)O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。
空间复杂度O(N)：辅助栈的空间，最差的情况下两个栈共存储N个元素
