漫画：如何用栈实现队列？

—————  第二天  —————

————————————

栈的特点是先入后出，出入元素都是在同一端（栈顶）：

入栈：

出栈：

队列的特点是先入先出，出入元素是在不同的两端（队头和队尾）：

入队：

出队：

既然我们拥有两个栈，那么我们可以让其中一个栈作为队列的入口，负责插入新元素；另一个栈作为队列的出口，负责移除老元素。

队列的主要操作无非有两个：入队和出队。

在模拟入队操作时，每一个新元素都被压入到栈A当中。

让元素1 “入队”：

让元素2 “入队”：

让元素3 “入队”：

这时候，我们希望最先“入队”的元素1“出队”，需要怎么做呢？

让栈A中的所有元素按顺序出栈，再按照出栈顺序压入栈B。这样一来，元素从栈A弹出并压入栈B的顺序是3,2,1，和当初进入栈A的顺序1,2,3是相反的：

此时让元素1 “出队”，也就是让元素1从栈B弹出：

让元素2 “出队”：

让元素4 “入队”：

此时的出队操作仍然从栈B弹出元素。

让元素3 “出队”：

让元素4 “出队”：

1. private Stack<Integer> stackA = new Stack<Integer>();
2. private Stack<Integer> stackB = new Stack<Integer>();
3. 

5. /**
6. * 入队操作
7. * @param element  入队的元素
8. */
9. public void enQueue(int element) {
10.    stackA.push(element);
11. }
12. 

14. /**
15. * 出队操作
16. */
17. public Integer deQueue() {
18.    if(stackB.isEmpty()){
19.        if(stackA.isEmpty()){
20.            return null;
21.        }
22.        transfer();
23.    }
24.    return stackB.pop();
25. }
26. 

28. /**
29. * 栈A元素转移到栈B
30. */
31. private void transfer(){
32.    while (!stackA.isEmpty()){
33.        stackB.push(stackA.pop());
34.    }
35. }
36. 

38. public static void main(String[] args) throws Exception {
39.    StackQueue stackQueue = new StackQueue();
40.    stackQueue.enQueue(1);
41.    stackQueue.enQueue(2);
42.    stackQueue.enQueue(3);
43.    System.out.println(stackQueue.deQueue());
44.    System.out.println(stackQueue.deQueue());
45.    stackQueue.enQueue(4);
46.    System.out.println(stackQueue.deQueue());
47.    System.out.println(stackQueue.deQueue());
48. }

—————END—————