栈和队列

栈

定义

栈是一种后进先出（LIFO，Last In First Out）的线性表。栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。

总结：

1. 栈只能从表的一端存取数据，另一端是封闭的。
2. 在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。拿上图的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

• 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
• 从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

实现

• 利用顺序存储结构（数组）实现队列称为顺序栈
• 利用链式存储结构（链表）实现队列称为链式栈

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。

顺序栈

链式栈

Java的栈

在Java中应用Stack类来创建一个后进先出的栈。

堆栈只定义了默认构造函数，用来创建一个空栈。

常用的方法主要有：

• boolean empty() ：测试堆栈是否为空。
• Object peek( )：查看堆栈顶部的对象，但不从堆栈中移除它。
• Object pop( )：移除堆栈顶部的对象，并作为此函数的值返回该对象。
• Object push(Object element)：把项压入堆栈顶部。
• int search(Object element)：返回对象在堆栈中的位置，以 1 为基数。

import java.util.*;
 
public class StackDemo {
 
    static void showpush(Stack<Integer> st, int a) {
        st.push(new Integer(a));
        System.out.println("push(" + a + ")");
        System.out.println("stack: " + st);
    }
 
    static void showpop(Stack<Integer> st) {
        System.out.print("pop -> ");
        Integer a = (Integer) st.pop();
        System.out.println(a);
        System.out.println("stack: " + st);
    }
 
    public static void main(String args[]) {
        Stack<Integer> st = new Stack<Integer>();
        System.out.println("stack: " + st);
        showpush(st, 42);
        showpush(st, 66);
        showpush(st, 99);
        showpop(st);
        showpop(st);
        showpop(st);
        try {
            showpop(st);
        } catch (EmptyStackException e) {
            System.out.println("empty stack");
        }
    }
}

题和应用

当我们我们要处理的数据只涉及在一端插入和删除数据，并且满足 后进先出（LIFO, Last In First Out） 的特性时，我们就可以使用栈这个数据结构。

• 实现浏览器的回退和前进功能

  我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。示例图如下:

  

• 有效括号

• 反转字符串：将字符串中的每个字符先入栈再出栈就可以了。

• 维护函数调用：最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。

队列

定义

队列是先进先出（FIFO，First In，First Out）的线性表。队列只允许在后端（rear）进行插入操作（入队enqueue），在前端（front）进行删除操作（出队dequeue）。

总结：

1. 数据从队列的一端进，另一端出；
2. 数据的入队和出队遵循"先进先出"的原则；

实现

• 利用顺序存储结构（数组）实现队列称为顺序队列
• 利用链式存储结构（链表）实现队列称为链式队列

两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。

顺序队列

• 简单队列
• 循环队列

链式队列

Java的队列

在Java中，Queue接口代表了基本队列，Queue接口定义以下几个方法：

• int size()：获取队列长度；
• boolean add(E)/boolean offer(E)：添加元素到队尾；
• E remove()/E poll()：获取队首元素并从队列中删除；
• E element()/E peek()：获取队首元素但并不从队列中删除。

LinkedList类实现了Queue接口。

import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        //add()和remove()方法在失败的时候会抛出异常(不推荐)
        Queue<String> queue = new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("element="+queue.element()); //返回第一个元素 
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("peek="+queue.peek()); //返回第一个元素 
        for(String q : queue){
            System.out.println(q);
        }
    }
}

双队列

题和应用

• 求解报数问题
• 求迷宫问题
• 阻塞队列： 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。
• 线程池中的请求/任务队列： 线程池中没有空闲线程时，新的任务请求线程资源时，线程池该如何处理呢？答案是将这些请求放在队列中，当有空闲线程的时候，会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列，除非系统资源耗尽，比如 ：FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了，当队列满的话后面再有任务/请求就会拒绝，在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。
• Linux 内核进程队列（按优先级排队）
• 消息队列

参考

• http://data.biancheng.net/view/169.html
• https://javaguide.cn/cs-basics/data-structure/linear-data-structure.html
• https://www.runoob.com/java/data-queue.html