栈(Stack) · 队列(Queue) · 循环队列 · 双端队列

一、栈(Stack)

1.1 概念

栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈 / 入栈 / 压栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

1.2 代码实现

1. 利用顺序表实现，即使用尾插 + 尾删的方式实现。
2. 利用链表实现，则头尾皆可。

相对来说，顺序表的实现上要更为简单一些，所以我们优先使用顺序表实现栈。

import java.util.ArrayList;
import java.util.Arrays;

public class MyStack {
    private int[] elem;
    private int usedSize = 0;

    public MyStack() {
        elem = new int[10];
    }

    //是否满
    public boolean isFull() {
        if (this.usedSize == this.elem.length) return true;
        return false;
    }

    // item 入栈
    public void push(int item) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
        }
        this.elem[this.usedSize++] = item;
    }

    //是否空栈
    public boolean isEmpty(){
        return this.usedSize == 0;
    }

    //弹出栈顶元素
    public int pop() throws RuntimeException{
        if (isEmpty()) {
            throw new RuntimeException("空栈~");
        }
        int ret = this.elem[this.usedSize-1];
        this.usedSize--;
        return ret;
    }

    //查看栈顶元素是多少
    public int peek() throws RuntimeException{
        if (isEmpty()) {
            throw new RuntimeException("栈为空~");
        }
        return this.elem[this.usedSize-1];
    }
}

补充：

超级简单的中缀表达式转变成后缀表达式。

第一步，把中缀表达式每一项加上括号；
第二步，把每一项中的符号都移动到该括号包裹的外面；
第三步，把所有括号去掉，得出后缀表达式。

---

二、队列（Queue）

2.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO（First In First Out）.

入队列：进行插入操作的一端称为队尾（Tail / Rear）
出队列：进行删除操作的一端称为队头（Head / Front）

2.2 代码实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些。
因为使用数组的结构，出队列在数组头上出数据，效率比较低。

class Node{
    public int data;
    public Node next;
    public Node(int data) {
        this.data = data;
    }
}

public class MyQueueLinked {
    private Node front;
    private Node rear;
    private int usedSize;

    //入队列
    public void offer(int val) {
        Node node = new Node(val);
        if ((this.front == null) && (this.rear == null)) {
            this.front = node;
            this.rear = node;
        }else {
            this.rear.next = node;
            this.rear = node;
        }
        this.usedSize++;
    }

    //出队头元素
    public int poll() throws RuntimeException {
        if (this.usedSize == 0) {
            throw new RuntimeException("队列为空！");
        }
        int val = this.front.data;
        if (this.front.next == null) {
            this.front = null;
            this.rear = null;
        }else {
            this.front = this.front.next;
        }
        this.usedSize--;
        return val;
    }

    //查看队头元素
    public int peek() throws RuntimeException {
        if (this.usedSize == 0) {
            throw new RuntimeException("队列为空！");
        }
        int val = this.front.data;
        return val;
    }

    //判断队列是否空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    //得到队列的元素个数
    public int size() {
        return this.usedSize;
    }
}

---

三、循环队列

3.1 概念

实际中我们还会使用到一种队列叫循环队列。循环队列通常使用数组实现。

如何区分空与满：

1. 通过添加 size 属性记录.
2. 保留一个位置.

因为要和空的循环队列区分，所以满的循环队列要浪费一个空间，来表示这是满的循环队列。

3.2 代码实现

/**
 * Created by cc
 * Description:
 * User: CZH
 * Date: 2022-09-29
 * Time: 19:38
 */
public class MyCircularQueue {
    private int[] elem;
    private int usedSize;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.elem = new int[k];
    }

    //入队操作
    public boolean enQueue(int value) {
        if (this.usedSize == this.elem.length) {
            return false;
        }
        this.elem[this.rear] = value;
        this.usedSize++;
        this.rear = (this.rear + 1) % this.elem.length;
        return true;
    }

    //判断是否存放满数据
    public boolean isFull1() {
        return this.usedSize == this.elem.length;
    }
    public boolean isFull2() {
        return ((this.rear + 1) % this.elem.length) == this.front;
    }

    //出队
    public boolean deQueue() {
        if (this.usedSize == 0) {
            return false;
        }
        this.front = (this.front + 1) % this.elem.length;
        this.usedSize--;
        return true;
    }

    //判断是否有数据
    public boolean isEmpty() {
        return this.front == this.rear;
    }

    //查看队头元素
    public int frontNum() throws RuntimeException {
        if (isEmpty()) {
            throw new RuntimeException("循环队列空");
        }
        int val = this.elem[this.front];
        return val;
    }

    //查看队尾元素
    public int RearNum() throws RuntimeException {
        if (isEmpty()) {
            throw new RuntimeException("空~");
        }
        if (this.rear == 0) {
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear-1];
    }
}

---

四、双端队列（Deque）

4.1 概念

双端队列是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。

那就是说明元素可以从队头出队和入队，也可以从队尾出队和入队。

---

五、Java 中栈和队列的方法

5.1 Stack

5.2 Queue

5.3 Deque