栈（Stack）
什么是栈
栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后入先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据是在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
出栈时，是C先出，然后是B，再是A .
注意：这个栈是一种数据结构，与JVM内存模型中的栈不同，JVM中的栈是指JVM中一段内存区域。
栈的使用
public static void main(String[] args) { Stack<Integer> s = new Stack(); //尖括号里是我要存放的数据类型 s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(s.size()); // 获取栈中有效元素个数---> 4 System.out.println(s.peek()); // 获取栈顶元素---> 4 s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3 System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为2 if(s.empty()){ System.out.println("栈空"); }else{ System.out.println(s.size()); } }
栈的模拟实现
可以看到，Stack继承了Vector，Vector是动态顺序表，与ArrayList类似，不同的是 Vector 是线程安全的。
import java.util.Arrays; public class MyStack { int array[]; //数组用于存放数据 int size = 0; //size用于记录当前元素个数 public MyStack() { this(12); //默认开辟大小为12的空间 } public MyStack(int m) { array = new int[m]; } //入栈 public int push(int value) { if(size == array.length) { //扩容 int[] copy; //复制array，并将其扩容一倍 copy = Arrays.copyOf(array,2* array.length); array = copy; //将array指向扩容后的数组 } array[size] = value; size++; return value; } //出栈 public int pop() { if(size == 0) { throw new RuntimeException("栈中没有元素"); } int n = array[size-1]; size--; return n; } //获取栈顶元素 public int peek() { if(size == 0) { throw new RuntimeException("栈中没有元素"); } return array[size-1]; } //获取元素个数 public int getSize() { return size; } //判断栈是否为空 public boolean isEmpty() { return size == 0; } }
队列（Queue）
什么是队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出特性。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列的使用
在Java中，Queue是个接口，底层是通过链表LinkedList实现的，LinkedList实现了Queue接口，我们可以通过LinkedList实例化对象，如：
Queue<Integer> queue = new LinkedList<>();
队列里的方法：
public static void main(String[] args) { Queue<Integer> queue = new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); queue.offer(5); // 从队尾入队列 System.out.println(queue.size()); //获取元素个数 System.out.println(queue.peek()); // 获取队头元素 queue.poll(); System.out.println(queue.poll()); // 从队头出队列，并将删除的元素返回 if(queue.isEmpty()){ System.out.println("队列空"); }else{ System.out.println(queue.size()); } }
输出：
队列的模拟实现
实现一个队列，我们可以用数组存储数据，也可以用链表存储数据，那究竟用哪种存储方式更好呢？
我们认为链表存储更好，因为链表的存储空间不连续，可以更好的利用存储空间（可以利用零碎的空间），而数组它的空间是连续的，万一空间不足就会出问题（不能利用零碎空间）。
public class MyQueue { //双向链表节点 public static class ListNode { ListNode next; //记录下一个节点 ListNode prev; //记录上一个节点 int val; //记录该节点存储的值 ListNode(int val){ this.val = val; } } ListNode head; // 队头 ListNode last; // 队尾 int size = 0; //入队列 public void offer(int val) { ListNode node = new ListNode(val); //先实例化这个节点出来 if(last == null) { //链表中未存放元素时 last = node; head = last; }else { last.next = node; node.prev = last; last = node; } size++; //链表元素个数加一 } //出队列 public int poll() { if(isEmpty()) { //判断队列是否为空 throw new RuntimeException("队列为空，无法出元素"); } int m = head.val; head = head.next; head.prev = null; size--; return m; } //判断队列是否为空 public boolean isEmpty() { return size == 0; } //获取对头元素 public int peek() { if(isEmpty()) { //判断队列是否为空 throw new RuntimeException("队列为空，无法获取元素"); } return head.val; } //获取元素个数 public int getSize() { return size; } }
循环队列
我们有时还会使用一种队列叫循环队列。环形队列通常使用数组实现。
队头添加元素，队尾删除元素，每块空间都能反复利用，有效节省空间。
front 指向队列的第一个元素，即array[front]为队列的第一个元素，初始值为0；
rear 指向最后一个元素的后一个元素，初始值为0；
从上图可以看出队列为空的条件：front == rear
当队列存放一个元素时，rear向前走一步，如下图：
那队列啥时候满了呢？当情况为下图时吗？
如果这就是满的话，但如何判断呢？是 front == rear 吗？
显然，这与判断队列为空相矛盾，我们不应该这样判断，那应如何判断呢？
我们有两种方法：
- 通过添加 size 属性记录（用size记录元素个数）
- 牺牲一个位置来表示满
我们就以牺牲一个位置为例吧，如果我们牺牲一个位置来表示满，当情况为下图时：
此情况就表示满，条件即是：(rear + 1) % array.length == front
class MyCircularQueue { int front = 0; int rear = 0; int[] array; public MyCircularQueue(int k) { //设计一个可以存放k个数据的数组 array = new int[k+1]; //为什么要设计k+1个大小呢？ } //因为在队尾后面需要牺牲一个空间，方便判满 //向循环队列插入一个元素。如果成功插入则返回真。 public boolean enQueue(int value) { if(isFull()) { return false; } array[rear] = value; rear = (rear + 1) % array.length; return true; } //从循环队列中删除一个元素。如果成功删除则返回真。 public boolean deQueue() { if(isEmpty()) { return false; } front = (front + 1) % array.length; return true; } //从队首获取元素。如果队列为空，返回 -1 。 public int Front() { if(isEmpty()) { return -1; } return array[front]; } //获取队尾元素。如果队列为空，返回 -1 。 public int Rear() { if(isEmpty()) { return -1; } return array[(rear+array.length-1)%array.length]; } //检查循环队列是否为空。 public boolean isEmpty() { if(rear == front) { return true; } return false; } //检查循环队列是否已满。 public boolean isFull() { if((rear+1) % array.length == front) { return true; } return false; } }
双端队列 (Deque)
双端队列：指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList或ArrayDeque的对象。
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
