03.栈和队列

写在前面

栈和队列，也属于线性表，因为它们也都用于存储逻辑关系为 “一对一” 的数据。使用栈结构存储数据，讲究先进后出，即最先进栈的数据，最后出栈；使用队列存储数据，讲究先进先出，即最先进队列的数据，也最先出队列。

什么是栈

栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构，同顺序表和链表一样，也是用来存储逻辑关系为 “一对一” 数据。栈的应用有很多，比如浏览器的跳转和回退机制等。

从上图可以看出：

1. 栈只能从一端存取数据，而另外一端是封闭的
2. 无论是存还是取，都需要遵循先进后出的原则。如需要取元素1，需要提前将元素4,3,2取出。

通常，栈的开口端被称为栈顶；封口端被称为栈底。

进栈和出栈

对于栈的操作一般是如下两种：

1. 进栈：将新元素放到栈顶元素的上面，成为新的栈顶元素（入栈或压栈）；
2. 出栈：将栈顶元素删除掉，使得与其相邻的元素成为新的栈顶元素（退栈或弹栈）；

栈的存储结构

• 顺序结构：使用数组实现
• 链式结构：使用链表实现

顺序栈

一个简单的队列，包含以下方法：

代码测试

public class Stack {
    /**
     * 栈的大小
     */
    private int maxSize;
    /**
     * 数组
     */
    private int[] stackArray;
    /**
     * 栈的top
     */
    private int top;
    /**
     * 初始化栈
     *
     * @param size
     */
    public Stack(int size) {
        this.maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }
    /**
     * 入栈
     *
     * @param i
     */
    public void push(int i) {
        stackArray[++top] = i;
    }
    /**
     * 常量出栈
     *
     * @return
     */
    public int pop() {
        return stackArray[top--];
    }
    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        return (top == -1);
    }
    /**
     * 是否已满
     *
     * @return
     */
    public boolean isFull() {
        return (top == maxSize);
    }
    @Override
    public String toString() {
        for (int i : stackArray) {
            System.out.println("top:"+i);
        }
        return super.toString();
    }
    //测试
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        //入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        while (!stack.isEmpty()){
            //出栈
            int pop = stack.pop();
            System.out.println("出栈元素："+pop);
        }
    }
}

测试结果可以发现显示的数据和输入的数据恰好相反。这也就符合“先进后出”的原则。

实际运用：字符反转

public class StackReverse {
    /**
     * 栈的大小
     */
    private int maxSize;
    /**
     * 数组
     */
    private char[] stackArray;
    /**
     * 栈的top
     */
    private int top;
    public StackReverse() {
    }
    /**
     * 初始化栈
     *
     * @param size
     */
    public StackReverse(int size) {
        this.maxSize = size;
        stackArray = new char[maxSize];
        top = -1;
    }
    /**
     * 入栈
     *
     * @param c
     */
    public void push(char c) {
        stackArray[++top] = c;
    }
    /**
     * 常量出栈
     *
     * @return
     */
    public char pop() {
        return stackArray[top--];
    }
    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        return (top == -1);
    }
    /**
     * 是否已满
     *
     * @return
     */
    public boolean isFull() {
        return (top == maxSize);
    }
    public String doReverse(String str) {
        System.out.println("输入字符为：" + str);
        String rev = "";
        int stackSize = str.length();
        StackReverse stack = new StackReverse(stackSize);
        for (int i = 0; i < stackSize; i++) {
            //获取字符
            char c = str.charAt(i);
            //入栈
            stack.push(c);
        }
        while (!stack.isEmpty()) {
            char pop = stack.pop();
            rev = rev + pop;
        }
        return rev;
    }
    public static void main(String[] args) {
        String rev = new StackReverse().doReverse("reverse");
        System.out.println("字符反转后：" + rev);
    }
}

测试结果：

之前我面试碰到过，我当时是这样回答的：直接调用reverse方法就行了啊。现在想想无地自容啊，因为面试官问的是实现方式，当然还有很多方法去实现，比如递归等等，这里只是举个例子。

链栈

public class StackByLink<E> {
    private Node<E> top;
    /**
     * 返回栈顶元素
     *
     * @return
     */
    public E peek() {
        return top.getData();
    }
    /**
     * 出栈
     *
     * @return
     */
    public E pop() {
        E data = null;
        if (top != null) {
            data = top.getData();
            //把栈顶元素弹出，并把原栈顶的下一个元素设为栈顶元素
            top = top.getNext();
        }
        return data;
    }
    /**
     * 入栈
     * 不太清楚的可以看上面的图
     * 把an设为新栈顶元素node  an-1为原来的栈顶元素 an-1的前一个元素就是an即node
     *
     * @param data
     */
    public void push(E data) {
        Node<E> node = new Node<E>();
        node.setData(data);
        if (top == null) {
            top = node;
        } else {
            //原来的元素设为新栈顶的下一个元素
            node.setNext(top);
            //
            top.setPre(node);
            top = node;
        }
    }
    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        return (top == null);
    }
    class Node<E> {
        E data;
        //前驱节点
        Node pre;
        //后继节点
        Node next;
        ...省略get set
    }
    //测试
    public static void main(String[] args) {
        StackByLink<String> stack = new StackByLink<>();
        stack.push("我");
        stack.push("是");
        stack.push("链");
        stack.push("表");
        System.out.println("peek:" + stack.peek());
        stack.push("实");
        stack.push("现");
        stack.push("的");
        stack.push("栈");
        System.out.println("pop:" + stack.pop());
        System.out.println("peek:" + stack.peek());
    }
}

Java中的栈

java中的栈是通过继承Vector来实现的，如下：

Vector作为List的另外一个典型实现类，支持List的全部功能，Vector类也封装了一个动态的，允许在分配的Object[]数组，Vector是一个比较古老的集合，JDK1.0就已经存在，建议尽量不要使用这个集合，Vector与ArrayList的主要是区别是，Vector是线程安全的，但是性能比ArrayList要低，主要原因是每个方法都是通过synchronized来保证线程同步的。

所以问题就来了，既然只是为了实现栈，为什么不用链表来单独实现，只是为了复用简单的方法而迫使它继承Vector（Stack和Vector本来是毫无关系的）。这使得Stack在基于数组实现上效率受影响，另外因为继承Vector类，Stack可以复用Vector大量方法，这使得Stack在设计上不严谨，当我们看到Vector中：

public void add(int index, E element) {
    insertElementAt(element, index);
}

该方法可以在指定位置添加元素，这与Stack的设计理念相冲突（栈只能在栈顶添加或删除元素），我估计当时的开发者肯定是偷懒了。

什么是队列

队列是一种要求数据只能从一端进，从另一端出且遵循 “先进先出” 原则的线性存储结构。

通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。生活中常见的排队买票和医院挂号都是队列。

队列的存储结构

• 顺序结构：使用数组实现
• 链式结构：使用链表实现

一个简单的队列，包含以下方法：

顺序队列

public class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int count;
    /**
     * 初始化
     * @param s
     */
    public Queue(int s) {
        this.maxSize = s;
        queueArray = new int[s];
        front = 0;
        rear = -1;
        count = 0;
    }
    /**
     * 入队
     * @param i
     */
    public void add(int i) {
        if (rear == maxSize - 1) {
            rear = -1;
        }
        queueArray[++rear] = i;
        count++;
    }
    /**
     * 出队
     * @return
     */
    public int remove() {
        int temp = queueArray[front++];
        if (front == maxSize) {
            front = 0;
        }
        count--;
        return temp;
    }
    /**
     * 获取队列头部元素
     * @return
     */
    public int peek() {
        return queueArray[front];
    }
    public boolean isEmpty() {
        return (count == 0);
    }
    @Override
    public String toString() {
        return "入队元素：" + Arrays.toString(queueArray);
    }
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        System.out.println(queue);
        while (!queue.isEmpty()){
            int remove = queue.remove();
            System.out.println("出队元素："+remove);
        }
    }
}

测试结果

链式队列

队列的链式存储结构，本质就是线性表的单链表，但它只能尾进头出，可参考前面的单链表，这里不再复述。

注：以下队列只做介绍，并附上详细讲解连接，感兴趣的可以自行查看

双端队列

双端队列Deque是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

ArrayDeque是Deque接口的一个实现，使用了可变数组，所以没有容量上的限制。 同时，ArrayDeque是线程不安全的，在没有外部同步的情况下，不能再多线程环境下使用。

ArrayDeque是Deque的实现类，可以作为栈来使用，效率高于Stack；

也可以作为队列来使用，效率高于LinkedList。

需要注意的是，ArrayDeque不支持null值。

可参考：ArrayDeque类的使用详解

阻塞队列

当队列是空的时候，从队列获取元素的操作将会被阻塞，当队列是满的时候，从队列插入元素的操作将会被阻塞。后面会在并发编程的JUC中讲到。

Java中阻塞队列BlockingQueue是一个接口，他的实现类主要包括以下几种：

可参考：BlockingQueue（阻塞队列）详解

优先级队列

优先级队列和通常的栈和队列一样，只不过里面的每一个元素都有一个优先级，在处理的时候，首先处理优先级最高的。如果两个元素具有相同的优先级，则按照他们插入到队列中的先后顺序处理。

可参考：Java Queue系列之PriorityQueue

总结

栈和队列涉及的方面很广，比如JVM的虚拟机栈，消息中间件MQ和队列的关系，本文主要强调对栈和队列概念的理解，后续会逐步分享。

参考

• 栈和队列详解
• 为什么质疑Java中的Stack

拓展延伸

• Java中的Stack是通过Vector来实现的，这种设计被认为是不良的设计，说说你的看法？
• LIFO和FIFO各代表什么含义？
• 栈的入栈和出栈操作与队列的插入和移除的时间复杂度是否相同？

都是自己人，点赞关注我就收下了🤞（白piao无罪🥺）