＜Java＞一把云顶的时间，带你认识栈和队列

落蕊重芳

前言

在学习栈和队列 之前，先了解一下什么是线性表：一次保存单个同类型的元素，多个元素之间逻辑上连续，比如数组，链表，字符串，栈和队列
栈和队列其实操作受限的线性表，数组也罢，链表也罢，既可以在头部插入和删除，也能在尾部插入和删除，但是栈和队列只能在一端插入，在一端删除
一、栈

1.定义

只能在一端插入元素，也只能在这一端删除元素（栈顶），可以把栈看作一个“水杯”，只能从一端添加元素，也只能从一段删除元素，而且，先进入水杯的水在杯底，后进入水杯的水在杯顶，往出倒水的时候，也是倒出的杯顶的水，栈也是一样，先入栈的元素在栈底，后入栈的元素在栈顶，所以先入栈的元素后出，后入栈的元素先出，这也是栈的特性“先进后出，后进先出”Last In First Out(LIFO),取出元素和添加元素只能在栈顶。
将1 2 3 4 5，一次放入栈中


2.栈的应用

1.无处不在的undo(撤销)操作

在任何一个编辑器中输错一个内容后，使用Ctrl + z就返回到了输入的内容；
在任何一个浏览器中点击后退操作


都是栈的这个结构的应用
1.使用编辑器使用撤销操作，一次输入就把内容压入栈中，再输入就就再压入栈中，发现一次输入错误，就使用撤销操作，把当前栈顶的错误内容弹出，那么当前栈顶的内容就是上次输入的内容。
2.浏览网页其实也是相同原理的，就像打开百度 -> 打开csdn -> 打开创作中心，也是使用栈这个结构，先把百度网页压入栈中 ，然后csdn网页压入栈中，然后创作中心网页压入栈中，想要返回到csdn主页，按下后头箭头，就把当前栈顶的创作中心网页弹出，取出csdn主页。
2.操作系统栈

程序再执行的过程中，从A函数调用B函数，从B函数调用C函数，调用结束，返回执行时，如何得知从哪继续开始执行呢，背后也是栈这个结构
3.栈的实现

基于链表实现的栈 – 链式栈
基于数组实现的栈 – 顺序栈（使用较多）
定义一个基于动态数组实现的栈
//基于动态数组实现的顺序栈
public class MyStack<E> {
    //记录当前栈的元素个数
    private int size;
    //实际存储数据的动态数组，此时在栈中只能在数组的尾部添加和删除元素
    private List<E> data = new ArrayList<>();
    }4.栈的操作

1.向栈中添加一个元素
只能在栈顶添加
/**
     * 向当前栈中添加元素 -- >压栈操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }2.当前从栈顶弹出一个元素
/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在数组末尾删除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }3.查看当前栈顶元素，但不弹出
/**
     * 查看当前栈顶元素值，不弹出该元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }二、队列

1.定义

队列：先进先出（FIFO）的数据结构i，元素只能从队尾添加到队列中，也只能从队首出队列，元素的出队顺序和入队顺序保持一致
将1 2 3 4 5依次入队


2.队列的应用

现实生活中，各种各样的“排队”操作
3.队列的实现

基于数组实现的队列 – 顺序队列
基于链表实现的队列 – 链式队列
出队操作只能在队列的头部进行，若采用数组实现的队列，每次出队一个元素就得搬移剩下的所有元素向前移动一个单位，此时采用链表实现的队列更适合队列的结构，删除元素只需要删除头结点，添加元素在链表的尾部添加
public interface Queue<E> {
    //入队操作
    void offer(E val);
    //出队操作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();
}对于栈来说队列的实现子类是比较多的，比如
FIFO队列
双端队列
循环队列
优先级队列
不管哪个队列都要实现
4.FIFO队列

1.定义一个FIFO队列
// An highlighted block
var foo = 'bar';2.向队列中添加一个元素
public void offer(E val) {
        Node<E> node = new Node<>(val);
        if (head == null){
            head = tail = node;
        }else{
            //链表的尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }3.从当前队首出队一个元素
public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        //头删
        E val = head.val;
        Node<E> node = head;
        head = head.next;
        node.next = node = null;
        size--;
        return val;
    }4.查看当前队列的队首元素
public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }5.循环队列

1.定义：基本上都是使用固定长度的数组来实现，数组在实现队时，若从数组头部删除元素需要频繁的移动后面的元素，效率比较低；出队和入队操作，使用两个引用，一个head，一个tail,添加元素在数组的尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就是队尾（tail），数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置


此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素，就只用让head引用向后移动一个位置


此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素，但此时head引用已经走到末尾了，所谓循环队列就是当head或者tail引用走到数组末尾时，再向后移动就是返回数组头部的操作，循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作，当有新的元素添加到队列中就会覆盖掉原来的元素，就只需要将tail索引位置覆盖上新的元素，再让tail再向后移动

当队列为空时,head == tail

当队列已“满”时，head == tail

循环队列需要注意的关键点
1.因此当head 和 tail相等时，没法区分此时循环队列已满，还是为空，因此在循环队列中，若(tail + 1) % n == head就认为循环队列已满



此时循环队列就已经满了，在循环队列中就会浪费一个空间，判断队列是否已满
2.head和tail的移动不能简单的 + 1，使用取模操作，取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质：
当head和tai走到数组最后一个索引位置时，下一次要返回数组头部，就必须用 + 1对数组长度取模
3.head == tail时，认为队列为空
6.循环队列的操作

1.定义一个循环队列
//基于整形的循环队列
public class LoopQueue implements Queue<Integer> {
    //定长数组
    private Integer[] data;
    //指向队首元素
    int head;
    //指向队尾元素的下一个元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }
}2.向循环队列中添加一个元素
@Override
    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }3.从循环队列中出队一个元素
@Override
    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }4.查看当前循环队列队首元素
@Override
    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }5.判断当前循环队列是否为空
@Override
    public boolean isEmpty() {
        return head == tail;
    }6.判断当前循环队列是否已满
public boolean isFull(){
        return (tail + 1) % data.length == head;
    }7.toString方法
public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }7.双端队列

双端队列：Deque是Queue的子接口，这个队列既可以尾插，头出；也可以头插，尾出
双端队列的一个常用子类就是LinkedList，不管使用栈还是队列，都可以统一使用双端队列接口
1.现在需要一个栈



2.现在需要一个队列