[数据结构]栈和队列
目录
1. 栈(Stack)
1.1、概念
1.2、 Stack的常用方法
1.3、有关栈的术语区分
2、实现自己的栈
2.1、入栈
2.2、出栈
2.3、查看栈顶元素
2.4、链式栈
3、队列(Queue)
3.1、概念
3.2、Queue的常用方法
3.3、循环队列
4、实现自己的链式队列
4.1、入队
4.2、出队
4.3、其他
5、设计循环队列
1. 栈(Stack)
1.1、概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守 后进先出 LIFO（Last In First Out）的原则。底层是数组
压栈：栈的插入操作叫做 进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做 出栈。出数据在栈顶。
1.2、 Stack的常用方法
1.3、有关栈的术语区分
栈、虚拟机栈、栈帧有什么区别?
栈：数据结构
虚拟机栈：JVM划分的一块内存
栈帧：调用方法的时候会在虚拟机中给这个方法开辟一块内存，这段内存就是栈帧
2、实现自己的栈
2.1、入栈
2.2、出栈
2.3、查看栈顶元素
2.4、链式栈
链表来实现栈的问题：
如果是双向链表，链表首尾都可以做栈顶，入栈出栈时间复杂度都是O(1)
如果是单链表，
从头入栈 -> O(1)；从头出(删除头节点)：O(1)
从尾巴入 -> O(n)；从尾巴出：O(n)，从尾巴出 有没有last的时间复杂度都是O(n)
3、队列(Queue)
3.1、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)的特点；底层是链表
入队：进行插入操作 的一端，称为队尾（Tail/Rear）
出队：进行删除操作 的一端，称为队头 （Head/Front）
3.2、Queue的常用方法
注：Queue是个接口，在实例化时必须实例化LinkedList对象，因为LinkedList实现了Queue接口
3.3、循环队列
使用数组作为队列时，会出现一种情况，在经过若干的入队出队操作后，空间还未满但无法再入队。
将数组改成一个环就能解决这个问题
如何解决这两个问题
1. rear和front相遇了他现在是空的还是满的？
2. rear 怎么从7下标来到0下标？
让 rear = (rear+1) % len 和 front = (front + 1) % len 就可以从7到0
解决是空还是满有很多种方案：
1. 使用usedSize 进行记录
2. 浪费一个空间来表示满（常用），例如数组长度是8，实际只能放7个元素
3. 使用标记，front和rear相遇一次标记一次
3.4、双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
在实际中，使用Deque接口是比较多的，栈和队列均可以使用该接口
Deque stack = new ArrayDeque<>(); // 双端队列的线性实现，底层是数组
Deque queue = new LinkedList<>(); // 双端队列的链式实现
这两行语句都不仅可以当做队列也可以当做栈，第二行语句也可以是链表
4、实现自己的链式队列
4.1、入队
4.2、出队
4.3、其他
5、设计循环队列
oj：622. 设计循环队列 - 力扣（LeetCode）
class MyCircularQueue {
public int[] elem;
public int front;//队头
public int rear;//队尾
public MyCircularQueue(int k) {
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;
}
}