目录
📚一、栈(Stack)
🐬1、概念
🐬2、栈的使用
🐬3、栈的模拟实现
📌（1）push(int val)方法
📌（2）empty()方法
📌（3）pop()方法
📌（4）peek()方法
📌（5）size()方法
📌（6）完整代码
🐬4、练习
📚二、队列(Queue)
🐬1、概念
🐬2、队列的使用
🐬3、队列模拟实现
📌（1）offer(E e)方法
📌（2）poll()方法
📌（3）peek()方法
📌（4）size()方法
📌（5）isEmpty()方法
📌（6）完整代码
🐬4、循环队列
三、双端队列(Deque)
📚一、栈(Stack)
🐬1、概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，栈中的数据元素遵守后进先出。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
因此我们的入栈和出栈的操作都是在栈顶进行的，并遵循后进先出原则
🐬2、栈的使用
栈总共有六种方法
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e 入栈,并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素的个数 |
| boolean empty() | 检测栈是否为空 |
入栈E push(E e)：
出栈pop()：
获取栈顶元素E peek()：
获取栈中有效元素的个数 int size()：
检测栈是否为空boolean empty()：
🐬3、栈的模拟实现
Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，既然是顺序表想必我们是能够使用数组来进行模拟实现的。
创建一个数组
📌（1）push(int val)方法
📌（2）empty()方法
📌（3）pop()方法
📌（4）peek()方法
📌（5）size()方法
📌（6）完整代码
MyStack
import java.util.Arrays;public class MyStack {public int[] arr;public int usedsize;public static final int DEFAULT_SIZE = 10;public MyStack(){this.arr = new int[DEFAULT_SIZE];}public int push(int val){if(isFull()){ensure();}this.usedsize++;arr[usedsize] = val;return arr[usedsize];}public boolean isFull(){return usedsize == this.arr.length;}public void ensure(){this.arr = Arrays.copyOf(this.arr,2*this.arr.length);}public int pop(){if(empty()){throw new StackEmptyException("栈为空");}this.usedsize--;return arr[usedsize];}public int peek(){if(empty()){throw new StackEmptyException("栈为空");}return arr[usedsize-1];}public int size(){return this.usedsize;}public boolean empty(){return 0 == this.usedsize;}}
异常
public class StackEmptyException extends RuntimeException{public StackEmptyException(String message){super(message);}
}
主函数
public class Test {public static void main(String[] args) {MyStack stack = new MyStack();}
}🐬4、练习
这道题选择C，因为如果3是第一个出栈的，第二个出栈的只有两个可能2和4，不可能是1
在这里如果3要出栈，下一次出栈的是直接进行出栈的2，和先进行入栈的，然后再出栈的4，不可能是1
📚二、队列(Queue)
🐬1、概念
队列：只允许在一端进行插入数据操作，在另一端进进行删除数据操作的特殊线性表，队列具有先进先出
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
🐬2、队列的使用
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
入队列offer(E e）
出队列poll()
获取队头元素peek()
获取队列中有效元素个数size()
检测队列是否为空isEmpty()
🐬3、队列模拟实现
创建一个结点
📌（1）offer(E e)方法
📌（2）poll()方法
📌（3）peek()方法
📌（4）size()方法
📌（5）isEmpty()方法
📌（6）完整代码
MyQueue
public class MyQueue {public static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode front;public ListNode last;public int usedsize = 0;public void offer(int e){ListNode node = new ListNode(e);if(front == null){front = node;}else {last.next = node;node.prev = last;}last = node;this.usedsize++;}public int poll(){if(front == null){System.out.println("队列为空");return -1;}int val = front.val;front = front.next;if(front != null){front.prev = null;}else{last = null;}return val;}public int peek(){if(front == null){System.out.println("队列为空");return -1;}return front.val;}public int size(){return this.usedsize;}public boolean isEmpty(){return front == null;}}
主函数
public class Test {public static void main(String[] args) {MyQueue myQueue = new MyQueue();}
}🐬4、循环队列
在使用的时候我们还会使用一种队列——循环队列（环形队列），环形队列通常使用数组实现。
当我们每添加一个元素是rear就会向前走一步，没减少一个元素front就会向前走一步
首先对这种环形队列我们会引出两个问题：
1、如何让下标从7到0？
2、什么情况下为满，什么情况下为空？
1、如何让下标从7到0？
正常来说从0下标到1下标我们只需要加1就可以实现了，但是这是一个环形队列他会从7下标跳到0下标，那么我们该用什么方法使他既不影响0~7，也能实现7~0呢？其实很简单我们只需要让front或rear在移动一位后模上我们的队列长度即可：(front+1)%len 或(rear+1)%len。
2、什么情况下为满，什么情况下为空？
这两个的判断标准其实很简单，每个空间都有数了就是满，都没有数就是空
但我们判断的方式却有三种：
（1）定义一个size来记录存储的个数如果size == len 就是满了，如果size = 0 就是空
（2）浪费一个空间来进行判断，当rear的下一个位置为front时就是满的，至于从7到0的方法我们刚才就进行讲解了，如下图
但是这个图其实是有问题的我们要判断这个环形队列满没满，虽然我们牺牲一个空间的方法的确能够成功判断，但我们牺牲的空间却是我们要判断环形队列的本身，这就导致了其实我们并没有存满就认为它满了，那么我们该怎样解决？其实我们只需要将它原本的空间增加一个就可以了，这样我们last最后到达的空间在我们原本的队列上其实是不存在的，只要到达了哪里，并且下一个是front就代表它满了。
初始化
判满
判空
当我们的队头和队尾相遇时队列为空
入队
出队
得到队头元素
得到队尾元素
如果不为空，由于rear的位置在队尾元素的前面，因此我们想要得到队尾元素需要让rear减一，但是，当rear =0时队尾元素应该在7位置因此当rear = 0时我们要得到7，我们发现这时我们可以利用三目运算符，当rear等于0时就让，它等于队列长度减一，这样就得到了7下标。
完整代码
习题链接
https://leetcode.cn/problems/design-circular-queue/description/
class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {this.elem = new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {return (rear+1) % elem.length == front;}
}
（3）添加标记法：
最初在front = rear = 0时，我们将isFull置为false，代表没满。
每次入队我们检查front是否等于rear如果等于就将 isFull置为true，代表满了。
当我们出队时，每出队一次就将isFull置为false，代表没满。
这样我们就可以将上面的代码进行改造
初始化
判满
这时判满只需要返回isFull本身即可，以为当队列满是isFull就会等于true;
判空
这时我们我们判断为不为空就不能简单的认为相遇就是空了，在上面相遇就是空是因为在判断是否为空前多了一个空间来判断队列满满没满？，因次在这里我们要进行满没满的判断，如果没满（isFull = false，加上一个 ！，就会让isfull = true,能够继续执行），front和rear相遇了就代表为空
入队
出队
得到队头元素
得到队尾元素
完整代码
class MyCircularQueue {public int front;public int rear;public int[] elem;public boolean isFull= false ;public MyCircularQueue(int k) {this.elem = new int[k];}public boolean enQueue(int value) {if(isFull()){return false;}elem[rear] = value;rear = (rear+1) % elem.length;if(rear == front){isFull = true;}return true;}public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;isFull = false;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return !isFull && front == rear;}public boolean isFull() {return isFull;}
}
三、双端队列(Deque)
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque是“doubleended queue”的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。
从头进，从头出
从尾进，从尾出
好了今天的分享就到这里了，还请大家多多关注，我们下一篇见！