Java - 栈和队列

文章目录

• 前言
• 一、栈
• • 1.栈的特点
  • 2.栈的实现
• 二、队列
• • 1.FIFO队列
  • 2.循环队列
  • 3.双端队列

前言

线性表：一次保存单个同类型元素，多个元素之间逻辑上连续

数组，链表，栈，队列，字符串(内部就是char[])都属于线性表。

栈和队列其实是 *** 作受限的线性表。

之前的数组，链表，既可以在头部插入和删除，也能在尾部插入和删除，甚至在任意位置都可以插入和删除

“栈和队列”只能在一端插入和删除元素

一、栈

栈在现实生活中的应用(无处不在的栈的应用)
1.无处不在的undo(撤销) *** 作
在任何编辑器中，输错了一个内容，使用ctrl + z 就返回了上一次输入的内容
2. *** 作系统栈：程序在执行过程中，从A函数调用B函数，从B函数调用C函数，返回执行时，运用的就是栈这个结构。

1.栈的特点

1.只能从一端插入元素，也只能从这一端取出元素(栈顶)
栈的特点：先进后出，后进先出的线性表
添加元素和删除元素的一端称为栈顶，另一端称为栈底

2.栈的实现

基于数组实现的栈 - 顺序栈
栈只能在栈顶插入元素，在栈顶删除元素

几个核心 *** 作：
Push(E e):向栈中添加元素 -> 入栈，压栈
E pop():出栈 *** 作，d出栈顶元素
E peek():查看栈顶元素，但不出栈

public class MyStack<E> {
    //当前栈的元素个数
    private int size;
    //实际存储数据的动态数组，此时在栈中只能在数组末尾添加和删除元素
    private List<E> data = new ArrayList<>();

    public void push(E val){
        data.add(val);
        size++;
    }

    public E pop(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty,cannot pop");
        }
        E val = data.remove(size-1);
        size--;
        return val;
    }

    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty,cannot peek");
        }
        return data.get(size-1);
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data.get(i));
            if (i != size-1){
                sb.append(",");
            }
        }
        sb.append("]top");
        return sb.toString();
    }

    private boolean isEmpty() {
        return size == 0;
    }
}

二、队列

其实栈和队列是一码事，都是只能在线性表的一端进行插入和删除。
因此，栈和队列是可以相互转换的。
队列：FIFO，先进先出的数据结构，元素从“队尾”添加到队列中，元素从“队尾”出队列

几个核心 *** 作：
offer(E val) :入队列
peek():查看队首元素
poll():d出队首元素

队列也有基于数组实现的队列和基于链表实现的对列，但基于数组实现的队列在删除元素时较为麻烦，每次出队一个元素就得搬移剩下的所有元素，让其向前移动一个单位

因此，采用链表的方案更适合队列的结构：
出队列：删除头节点
添加元素：在链表的尾部添加

向对于栈来说，队列的实现子类是比较多的，比如普通的FIFO队列，双端队列Deque，循环队列LoopQueue，优先级队列PriorityQueue
故我们创建一个Queue接口，实现该接口的每个子类都具备入队 *** 作，出队 *** 作，查看队首元素等方法。

public interface Queue<E> {
    //入队 *** 作
    void offer(E val);
    //出队 *** 作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();
}

1.FIFO队列

下面我们自己实现一个基于链表普通的FIFO队列

//创建一个节点类
class Node<E>{
    E val;
    Node<E> next;

    public Node(E val) {
        this.val = val;
    }
}

public class LinkedQueue<E> implements Queue<E> {
    //当前队列中的元素个数
    private int size;
    //当前队列的队首元素
    private Node<E> head;
    //当前队列的尾部元素
    private Node<E> tail;
    @Override
    public void offer(E val) {
        //产生一个新节点
        Node<E> node = new Node<>(val);
        if (head == null){
            head = tail = node;
        }else {
            //尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }

    @Override
    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;
    }

    @Override
    public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty,cannot peek");
        }
        return head.val;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front[");
        for (Node<E> x = head; x != null; x = x.next) {
            sb.append(x.val);
            if (x.next != null){
                sb.append(",");
            }
        }
        sb.append("]tail");
        return sb.toString();
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}

2.循环队列

循环队列： *** 作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎中的redo日志
基本都是使用长度固定的数组来实现，数组在实现队列时，若从数组头部删除元素，需要频繁的移动后面的元素，效率较低

出队和入队 *** 作，使用两个引用，一个head，一个tail，添加元素在数组尾部添加，删除元素只需移动head引用指向的地址即可(逻辑删除)

循环队列就是使用长度固定的数组来实现，数组头部就是队首head，数组的尾部就是队尾tail。
数组[head…tail)是循环队列的有效元素。

head永远指向循环队列的第一个元素
tail永远指向循环队列有效元素的后一个位置

所谓的循环队列指的就是当head或者tail引用走到数组末尾时，
下一次再继续向后移动，其实就是返回数组的头部继续 *** 作

循环队列在删除元素时，不需要进行数据的搬移
当有新的元素再添加时就会覆盖掉之前的元素

注意：

于是我们在队列中，若tail + 1 == head就认为循环队列已满
在循环队列中浪费一个空间，判断队列是否已满

若head和tail要往后移动，此时我们使用% *** 作：tail = (tail + 1) % n
对数组长度取模的本质：
head和tail走到数组最后一个索引位置时，下一次要返回数组头部，就必须使用tail+1对n取模

循环队列的三个特点：

关于最后一个元素的取值
最后一个元素的取值不能简单的用索引 = tail-1来判断，当tail == 0时，最后一个元素在数组的末尾。

public class LoopQueue implements Queue<Integer> {
    //定长数组
    private Integer[] data;
    //头节点
    private int head;
    //尾节点
    private int tail;

    public LoopQueue(int size){
        data = new Integer[size + 1];
    }
    @Override
    public void offer(Integer val) {
        if (isFull()){
            throw new ArrayIndexOutOfBoundsException("LoopQueue is full");
        }
        data[tail] = val;
        tail = (tail+1) % data.length;
    }

    @Override
    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("LoopQueue is empty");
        }
        Integer val = data[head];
        head = (head+1) % data.length;
        return val;
    }

    @Override
    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("LoopQueue is empty");
        }
        return data[head];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    public boolean isFull(){
        return (tail+1) % data.length == head;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front[");
        for (int i = head; i != tail;) {
            int lastIndex = tail == 0 ? data.length-1 : tail-1;
            sb.append(data[i]);
            if (i != lastIndex){
                sb.append(",");
            }
            i = (i+1) % data.length;
        }
        sb.append("]tail");
        return sb.toString();
    }
}

3.双端队列

双端队列：Deque -> Queue的子接口
这个队列既可以从尾插头出，也可以头插尾出
以后无论使用的是栈还是队列，统一使用双端队列接口
不推荐使用Stack这个类，这个类效率很低，都是同步 *** 作
双端队列的一个常用子类就是LinkedList

双端队列中的一些基本方法：