【算法问题】如何用栈实现队列

如何用栈实现队列

摘自漫画算法：

题目：用栈模拟一个队列，要求实现队列的两个基本操作：入队、出队。

解题思路

栈的特点是先入后出，出入一款苏都是在同一端（栈顶）。如图：

栈.png

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

队列.png

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

解题思路 — 图1.png

注意问题：两个栈都是各自独立的，如何把他们有效地关联起来呢？

队列的主要操作无非有两个：

入队：在模拟入队操作时，每一个新元素都被压入到栈A当中。
出队：让栈A中的所有元素按顺序出栈，再按照出栈顺序压入栈B

例子：

1、让元素1入队

解题思路 — 图2.png

2、元素2入队

解题思路 — 图3.png

3、元素3入队

解题思路 — 图4.png

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

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

解题思路 — 图5.png

4、此时让元素1出队，也就是让元素1从栈B中弹出。

解题思路 — 图6.png

5、让元素2出队。

解题思路 — 图7.png

如果此时又想做入队操作，重新把新元素压入栈A。

6、让元素4入队。

解题思路 — 图8.png

7、此时出队操作仍然从栈B中弹出元素，让元素3出队。

解题思路 — 图9.png

此时栈B已经为空了，如果再想出队又该如何做呢？

只要栈A中还有元素，就像刚才一样，把栈A中的元素弹出并压入栈B即可。

解题思路 — 图10.png

8、元素4出队。

解题思路 — 图11.png

代码实现

import java.util.Stack;

/**
 * 描述：基于栈实现队列。
 * <p>
 * Create By ZhangBiao
 * 2020/6/6
 */
public class QueueByStack {

    private Stack<Integer> stackA = new Stack<>();

    private Stack<Integer> stackB = new Stack<>();

    /**
     * 入队操作
     *
     * @param element 入队的元素
     */
    public void enqueue(int element) {
        stackA.push(element);
    }

    /**
     * 出队操作
     */
    public Integer dequeue() {
        if (stackB.isEmpty()) {
            if (stackA.isEmpty()) {
                return null;
            }
            transfer();
        }
        return stackB.pop();
    }

    /**
     * 栈A元素转移到栈B
     */
    private void transfer() {
        while (!stackA.isEmpty()) {
            stackB.push(stackA.pop());
        }
    }

    public static void main(String[] args) {
        QueueByStack queue = new QueueByStack();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        queue.enqueue(4);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }

}