跟我一起学算法系列7——用两个栈实现队列

1.题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

2.算法分析

首先我们需要弄清楚两个概念，栈是先进后出，队列是先进先出。概率有了，那么仔细一分析发现栈和队列刚好相反，那么我们就可以在入栈的时候，我们将它全放进栈1中,当需要出栈的时候,我们将栈1的数据出栈，并放到栈2中，然后再将栈2依次出栈。

因此，入栈的时候，只需要使用pop方式入栈到栈1。出栈的时候，我们isEmpty方法将栈1的数据push到栈2，然后将栈2的数据pop即可。

3.代码实例

import java.util.Stack;

public class Solution {

Stack stack1 = new Stack();

Stack stack2 = new Stack();

public void push(int node) { //直接入栈 stack1.push(new Integer(node));}public int pop() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ //将栈1的数据压入栈2 stack2.push(stack1.pop()); } } //栈2出栈 return stack2.pop().intValue(); }

}