作者：行百里er

博客：https://chendapeng.cn (opens new window)

提示

这里是 行百里er 的博客：行百里者半九十，凡事善始善终，吾将上下而求索！

本文将介绍用数组实现栈的方法，以及队列与栈的一些经典操作。

用数组实现栈

由于栈的逻辑结构是先进后出，后进去的先出来，图解如下：

从图解看出，用数组实现栈时比较简单，只需要维护index的值防止数组越界即可，代码实现：

public class MyStack {
    private int[] array;
    private int index;
    
    public MyStack(int size) {
        this.array = new int[size];
    }
    
    //入栈
    public void push(int value) {
        if (index >= array.length) {
            throw new RuntimeException("栈满，不让加了");
        }
        array[index++] = value;
    }
    
    //出栈
    public int pop() {
        if (index <= 0) {
            throw new RuntimeException("栈空，不能取出");
        }
        return array[--index];
    }
}

用数组实现队列

我们再来图解分析一下，如何用数组实现队列。

入队列，依次加入1,2,3,4,5：

队列达到给定数组的长度个元素后，下面来分析一下从队列取出数据、再添加数据的过程：

要符合队列的先进先出特性，这个数组就像一个循环数组，当队列满（指队列元素个数达到指定数组长度）了，取出元素，再继续添加元素的时候，index又来到了开始的位置，如此往复。

现在我们假设两个指针，begin和end，再增加一个变量size来表示队列当前元素个数。

当size大于指定数组长度时，就不能往队列里插入数据了；当size<0时，就不能从队列取数据了——也就是说用这个size变量来控制能否push和pop。

当要插入数据时，将要插入的数据放到end的位置，然后让end++，此时需要注意下标越界的问题，若end大于等于size了，就需要将end设置到0的位置了，图解如下：

当要取出数据时，因为队列的先进先出特点，最先进入到队列的数据在begin位置，所以从begin位置取数，同时让begin++，来到新的最早进入队列的数据位置，同理也要注意begin的下标是否越界。如下图所示：

从上面的分析可知，插入数据和取出数据用size和begin、end指针就可以完成。

用数组实现队列的代码如下：

public static class MyQueue {
    private int[] array;
    private int begin;
    private int end;
    private int size;

    public MyQueue (int limit) {
        this.array = new int[limit];
        this.begin = 0;
        this.end = 0;
        this.size = 0;
    }

    public void push (int value) {
        size++;
        if (size > array.length) {
            throw new RuntimeException("队列满了");
        }
        array[end] = value;
        end++;
        //针对end越界的处理
        if (end >= array.length) {
            end = 0;
        }
    }

    public int pop () {
        size--;
        if (size < 0) {
            throw new RuntimeException("队列已空");
        }
        int result = array[begin];
        begin++;
        //针对begin越界的处理
        if (begin >= array.length) {
            begin = 0;
        }
        return result;
    }
}

用数组实现有技巧，需要根据size来控制是否能插入取出，然后借助辅助指针来移动并记录数组下标。

仍然建议画图加深理解。

一些经典操作

队列和栈的结构非常经典，在面试中会经常出现他们的变种题。

比如，实现图的宽度优先遍历，但是要求用栈实现；实现图的深度优先遍历，但是要求用队列实现。

这个题比较阴的地方就是图的宽度优先遍历通常是用队列来实现的，而深度遍历使用栈实现，所以，这里需要我们做一个转换：

先用队列来实现栈，然后用这个队列实现的栈实现宽度优先遍历，从而达到用栈实现图的宽度优先遍历的目的；

对于深度优先遍历，先用栈来实现队列，然后用这个栈实现的队列实现深度优先遍历。

这篇文章不是讨论图这种结构的，主要实现以下两种算法：

• 用栈结构实现队列结构
• 用队列结构实现栈结构

用栈实现队列

要想实现队列，我们要考虑的是怎样达到数据的先进先出。

而栈是先进后出的结构，于是我们可以用两个栈来实现：push栈和pop栈。

对于我们要实现的特殊队列，入队的时候压入数据到push栈，同时观察判断pop栈是否为空。

插入一个3，add(3)，此时pop栈为空，需要将push栈中的数弹出压入到pop栈，直到push栈为空：

插入一个2，add(2)，此时pop栈不为空，无需弹出push栈和压入pop栈：

同理，依次add(5)和add(7)：

此时，我要从队列中取出数据，poll，弹出pop栈，此时判断一下pop栈是否为空，若为空，则需要将push栈数据全部倒出压入到pop栈：

继续从队列取数：

从上述add和poll的过程我们可以得出一个结论：

无论队列add还是poll都要看一下pop栈是否为空，如果pop栈为空了，则需要弹出push栈的数据压入到pop栈，直到push栈为空。

即：

• push栈数倒入到pop栈时要一次性倒完
• 当pop栈不为空时，不需要压入push栈的数据

这样就能保证先进先出了。

因此我可以抽象出一个弹出push栈数据压入pop栈的方法：

public void pushToPop() {
    if (popStack.isEmpty()) {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
    }
}

用栈实现队列的完整代码：

public class MyQueueWithStack {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;
    
    public MyQueueWithStack() {
        this.pushStack = new Stack<>();
        this.popStack = new Stack<>();
    }
    
    public void pushToPop() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
    }
    
    public void add(int value) {
        pushStack.push(value);
        pushToPop();
    }
    
    public int poll() {
        if (popStack.isEmpty() && pushStack.isEmpty()) {
            throw new RuntimeException("队列空了！");
        }
        pushToPop();
        return popStack.pop();
    }
}

用队列实现栈

有了用两个栈实现队列的经验，我们可以再来试一下如何用两个队列实现栈。

终极目的是实现数据的先进先出，也就是先添加的数据，在取数的时候先取出。

下面先用图来演示一遍过程：

上图演示的数据入栈出栈过程：

入栈：1，2，出栈：2

入栈：3，4，5，出栈：5

入栈：无，出栈：4

...

所以，这一过程实现了栈的后进先出，达到了用队列实现栈的目的(用两个队列来回倒数据)。

要点：定义两个队列，实现的这种栈在push时往非空的那个队列（如果都为空，则选择其中一个）插入数据，pop时将非空的队列数据取出并依次插入到原来空的那个队列，只留下最后一个元素，将这个元素取出返回，这样原来非空的就变成了空队列了。---每次操作无论push还是pop均有一个队列是空的。

把上面我分析的思路翻译成代码就是这样的：

public class MyStackWithQueue<T> {
    private Queue<T> queue;
    private Queue<T> help;
    
    public MyStackWithQueue() {
        this.queue = new LinkedList<>();
        this.help = new LinkedList<>();
    }
    
    public void push(T value) {
        if (queue.isEmpty() && help.isEmpty()) {
            queue.add(value);
        }
        if (!queue.isEmpty()) {
            queue.add(value);
        }
        if (!help.isEmpty()) {
            help.add(value);
        }
    }

    public T pop() {
        Queue<T> temp = new LinkedList<>();
        if (!queue.isEmpty()) {
            temp = queue;
            while (queue.size() > 1) {
                help.add(queue.poll());
            }
        } else if (!help.isEmpty()) {
            temp = help;
            while (help.size() > 1) {
                queue.add(help.poll());
            }
        }
        return temp.poll();
    }
}

延伸：Java中的List和Queue

List集合

List集合元素有明确的 上一个 和 下一个 元素，也存在明确的第一个和最后一个元素。

List集合最常用的是 ArrayList 和 LinkedList 两个集合类。

ArrayList

ArrayList的容量可以改变，非线程安全集合。其内部实现用数组进行存储，集合扩容时会创建一个更大的数组控件，把原有数据复制到新数组中。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    
    //......
}

ArrayList支持对元素的快速随机访问，但是插入和删除的速度较慢，因为插入和删除的过程需要移动元素。

LinkedList

LinkedList本质上是一个双向链表。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
    
    //...
}

它和ArrayList很明显的区别就是，LinkedList的插入和删除速度快，而随机访问速度则很慢。

另外，LinkedList还实现了 Deque 接口（double-ended queue，双端队列），Deque 同时具有队列和栈的性质，因为它可以先进先出，也可以先进后出。

LinkedList将零散的内存单元通过附加引用（其内部定义了指向前一个和后一个元素的first和last指针）的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高。

Queue集合

前面几篇文章一直在探讨队列、栈这些数据结构，队列的**先进先出（FIFO）**应该深入我们的脑海中---队列只允许从一端进行取数，在另一端进行插入数据。

从棣属于juc包下的 BlockingQueue 出现以来，队列就应用于各种高并发场景中，鉴于其先进先出的特性记忆阻塞操作的特点，它经常被用作数据缓冲区。

---

首发公众号 行百里er ，欢迎老铁们关注阅读指正。