两个栈实现一个队列

发表于 更新于 分类于 阅读次数： 本文字数： 159 阅读时长 ≈ 1 分钟

今天下午汉得来学校宣讲，笔试中看到这样一个题目，让我们用两个栈实现一个队列。

那时候没想太多，队列先进先出，栈先进后出，那么只要一个栈作为主栈，另一个栈作为缓存栈，来回倒腾就能实现队列的功能了。

回来后仔细想想，其实还有比这更高效的方法。也就是保留主栈的栈底元素，弹出即可，这样可以减少一次压栈操作。

顺便用代码实现了一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
入队时将元素压入栈1。
出队时先判断栈2是否为空，若不为空则直接弹出栈2的栈顶元素。若为空，则将栈1除了栈底的元素弹出并压入栈2，然后弹出栈1的元素再将栈2的元素弹出并压回栈1即可。
这样做的好处是可以减少一次压栈的操作，并且考虑了没有元素可出队的异常处理。
*/
public class StackToQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public StackToQueue() {
       stack1 = new Stack<Integer>();
       stack2 = new Stack<Integer>();
    }

    public static int pop() {
        //如果栈1不为空，且栈1所剩元素大于1，则将栈1出栈并压入栈2
        while(!stack1.isEmpty()){
        	if(1==stack.size())
        		break;
        	stack2.push(stack1.pop());
        }

        //将栈1的元素出栈，即出队。
        int top = stack1.pop();

        //如果栈2不为空，将栈2中的元素出栈并压回栈1中
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        return top;
    }
}