作者：解学武

栈怎样才能实现和队列一样从栈的底层抽出元素呢？一般会用两个栈来实现队列。

首先，我们将两个栈分别定义为 stack1 与 stack2。

实现方案 1

我们让入队操作在 stack1 中执行，而出队操作在 stack2 中执行。执行方式如下。

• 入队：直接向 stack1 中入栈。
• 出队：将 stack1 中的所有元素出栈，依次入栈到 stack2 中，然后弹出 stack2 中的栈顶元素，接着把 stack2 中的所有元素出栈，依次压入 stack1 中。

为了便于理解，我们借助图 1 解释上述入队操作。

出队操作如图 2 所示。


来回入队、出队比较烦琐，尤其是出队比较麻烦，需要先将元素从 stack1 倒入 stack2 里，然后在 stack2 弹出元素之后又倒回到 stack1 里。有没有更好的办法呢？当然有，方案 2 就是改进之后的思路。

实现方案 2

入队都在 stack1 中进行，stack2 用于出队，同时保证所有元素都在一个栈里，且遵守以下规则。

• 入队：不管 stack1 是否为空栈，都将 stack2 中的所有元素压入 stack1 中。
• 出队：若 stack2 不为空栈，则直接从 stack2 中弹出元素；若 stack2 为空栈，则把 stack1 中的元素倒入 stack2 中，再从 stack2 中弹出元素；若两个栈都是空的，则说明队列为空队，不能出队。这与方案 1 的思路一样，只不过把倒回去的这个操作放到了入队时执行，却使连续入队、出队的效率提高了。

还有更好的办法吗？当然有。方案 3 就是一种更优的解决办法。

实现方案 3

入队都在 stack1 中进行，出队在 stack2 中进行，同时遵守以下规则。

• 入队：直接把元素压入 stack1 中。
• 出队：如果 stack2 不为空，则直接弹出 stack2 中的元素；如果 stack2 为空，则将 stack1 中的所有元素倒入 stack2 中，然后弹出 stack2 中的栈顶元素。同样，若两个栈都为空栈，则队列为空队，无法出队。

这个方案在入队时非常简单，而在出队时，多数情况下可以直接通过出队 stack2 实现，若需要把 stack1 中的元素倒入 stack2 中，则一般不用每次都进行这样操作。最坏的情况就是出队一个元素、入队一个元素这样的循环操作，导致每次出队都要转移元素。

其实这三种方案的操作是一样的。总体来说，方案 3 是非常好的方案。

下面为方案 3 的代码实现。

package me.irfen.algorithm.ch02.extend;
import me.irfen.algorithm.ch02.Stack;
public class Stack2Queue {
    private Stack stack1;
    private Stack stack2;
    private int maxLength;

    public Stack2Queue(int capacity) {
        maxLength = capacity;
        stack1 = new Stack(capacity);
        stack2 = new Stack(capacity);
    }

    public boolean put(int item) {
        if (stack1.isFull() || maxLength == size()) {
            // 满了
            return false;
        }
        stack1.push(item);
        return true;
    }

    public int poll() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

    public int size() {
        return stack1.size() + stack2.size();
    }
}

下面是测试代码：

package me.irfen.algorithm.ch02.extend;
public class Stack2QueueTest {
    public static void main(String[] args) {
        Stack2Queue queue = new Stack2Queue(5);
    queue.put(1);
    queue.put(2);
    System.out.println(queue.poll()); // 1
    queue.put(3);
    queue.put(4);
    System.out.println(queue.poll()); // 2
    System.out.println(queue.poll()); // 3，本次会把3、4两个元素从stack1倒入stack2
}
}

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。