作者：解学武

本节介绍一下如何用两个队列实现栈。

栈的主要操作就是入栈和出栈，其特点就是后进先出。我们先将两个队列分别定义为 queue1 与 queue2。

方案 1

入栈和出栈，都在 queue1 中完成，而 queue2 作为中转空间。

• 入栈：直接入 queue1 即可。
• 出栈：把 queue1 中除最后一个元素外的所有元素都移动到 queue2 中，再将 queue1 中的元素出队，此时即出栈；接着将 queue2 中的所有元素移动到 queue1 中。

具体操作如图 1 和图 2 所示。



该操作过程与用栈实现队列的方案 1 一样，都是把第 2 个结构当作一个中转站，然后将数据来回倒。接下来看一个更优一点的方案。

方案 2

从方案 1 的操作方式中，我们可以看出其劣势，即在出栈时要把 queue2 中的元素移动到 queue1 中。在两个队列之间能否不用每次先出栈再把元素移动回去？当然可以。下面是入栈、出栈的具体操作描述。

• 入栈：两个队列哪个不为空，就把元素入队到哪个队列中；如果都为空，则任选一个队列入队，假设这个队列就是 queue1。
• 出栈：把不为空的队列中除最后一个元素外的所有元素移动到另一个队列中，然后出队最后一个元素。

这样方案 2 就更简单了，省去了方案 1 中最后一步的转回操作。

下面是实现代码：

package me.irfen.algorithm.ch02.extend;
import me.irfen.algorithm.ch02.ArrayQueue;
public class Queue2Stack {
    private ArrayQueue queue1;
    private ArrayQueue queue2;
    private int maxLength;
   
    public Queue2Stack(int capacity) {
        maxLength = capacity;
        queue1 = new ArrayQueue(capacity);
        queue2 = new ArrayQueue(capacity);
    }
   
    /**
     * 入栈
     * @param item
     * @return 入栈结果
     */
    public boolean push(int item) {
        if (size() == maxLength) {
            return false;
        }
        if (queue2.isEmpty()) {
            queue1.put(item);
        } else {
            queue2.put(item);
        }
        return true;
    }
   
    /**
     * 出栈
     * @return
     */
    public Object pop() {
        if (size() == 0) {
            throw new IndexOutOfBoundsException("栈里已经空啦");
        } else {
            if (queue2.isEmpty()) {
                while (queue1.size() > 1) {
                    queue2.put(queue1.poll());
                }
                return queue1.poll();
            } else {
                while (queue2.size() > 1) {
                    queue1.put(queue2.poll());
                }
                return queue2.poll();
            }
        }
    }
   
    public int size() {
        return queue1.size() + queue2.size();
    }
}

测试代码如下：

package me.irfen.algorithm.ch02.extend;
public class Queue2StackTest {
    public static void main(String[] args) {
        Queue2Stack stack = new Queue2Stack(5);
        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop()); // 2
        stack.push(3);
        stack.push(4);
        System.out.println(stack.pop()); // 4
        System.out.println(stack.pop()); // 3
    }
}

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