【数据结构】栈和队列
数据结构系列二：栈和队列
一、贯彻性分类
1.栈
2.队列
2.1双端队列：
2.2循环队列的设计实现：
2.2.1优点
2.2.2实现
2.2.3公式
1.角标移动公式
2.有效长度计算公式
3.共性
二、设计实现
1.链表实现它的链式栈队列
单向链表
双向链表
2.数组实现它的线性栈队列
数组
三、提供的帮助设计方法
1.Queue
2.Deque
四、底层方法的使用
1.Stack
1.1构造
1.2获取
1.2.1获取栈顶元素
1.2.2获取有效元素个数
1.2.3获取是否为空栈
1.3插入
1.4删除
2.Queue
2.1获取
2.1.1获取队头元素
2.1.2获取有效元素个数
2.1.3获取是否为空队列
2.2插入
2.3删除
一、贯彻性分类
在所有数据结构中，在增删数据维护位置上，分出了栈队列和非栈队列两大性质的数据结构，数据结构类的增删数据限制在只在端进行就属于栈队列性质的数据结构
1.栈
限制全由一端增删数据实现的数据结构就属于栈，存储数据特点是先进后出、后进先出，数据成同一端来同一端出的U字结构，只能进行尾插头删
2.队列
限制在一端实现增数据、另一端实现删数据的数据结构就属于队列，存储数据特点是先进先出、后进后出，数据成一端进另一端出的直线方向结构
2.1双端队列：
单向队列限制的是增删数据只能在一个方向上的一端增数据、一端删数据，如果在此基础上，从另一个方向来把原来端上缺的增删都各自对应补充实现完，就实现了双端队列
2.2循环队列的设计实现：
2.2.1优点
底层是数组，利用公式设计成两端能自然地互通到达，能循环地使用数组且时间复杂度为O(1)
2.2.2实现
- front记录的是队头，对队头进行删除，队头记录的空间有数据的
- rear记录的是队尾，对队尾进行插入，队尾记录的空间往往是沼泽地无数据的等插入的
在队头队尾之间都是有效数据的记录，在front == rear时判定为空，在rear的下一个是front时判断为满，所以队列维护的区域中总有一个是不放数据做沼泽地的来使得判满的，这样判空与判满就都各自都有就能实现了，数据成一端进另一端出的曲线方向结构
2.2.3公式
1.角标移动公式
队头队尾同往大角标方向的顺序：
index = (index + offset) % array.length
队头队尾同往小角标方向的顺序：
index = (index + array.length - offset) % array.length
2.有效长度计算公式
len = (rear - front + array.length) % array.length
3.共性
双端队列使用时限制只用双端队列的一端就又实现了栈，栈队列记录的头与尾一直都是对有效元素记录的而不是对其所在存储总空间的记录
二、设计实现
任何一种数据结构都可以去限制实现它那种结构下的栈和队列，只是时间复杂度的原因合不合适去实现而已：
1.链表实现它的链式栈队列
单向链表
复杂度：头插、尾插、头删复杂度O(1)
合适实现—> 头插头删栈、尾插头删队列
双向链表
复杂度：头插尾插头删尾删复杂度全都为O(1)
合适实现—> 所有端任意搭配方式实现的栈队列
2.数组实现它的线性栈队列
数组
复杂度：尾插、尾删复杂度O(1)
合适实现—> 尾插尾删栈、尾插头删循环队列
三、提供的帮助设计方法
任何一种数据结构都能设计成栈和队列的性质结构，其中库里面提供有帮助直接设计成栈和队列的接口方法，不用自己再去限制定义，只要遵循着只使用栈和队列接口实现的方法就可以实现栈和队列的结构：
1.Queue
Queue接口配备的抽象方法比较少(offer、poll)，仅支持帮助设计成单向队列
2.Deque
Queue的子类Deque就在它基础上再实现补全增加了另一向的方法(offerFirst、offerLast、poolFirst、poolLast)，使其能支持帮助设计成双向队列了，(push、pop)同时也补全分出有专门实现栈的方法，也不需要借助双向队列实现栈，都是提供全了所有结构专门实现的方法，因此继承于Deque的ArrayDeque与LinkedList里面都有设计成单向队列、双向队列、栈结构的方法，使它们能直接用提供的方法实现所有的栈和队列结构
四、底层方法的使用
下面是库里面实现提供好的最下层栈实现类Stack和最上层队列接口Queue里最底层方法的使用：
1.Stack
Stack类变量对数组限制使用尾插尾删最底层头插头删实现的顺序结构的栈
1.1构造
new Stack<E>();
—> return Stack<E>
构造一个纯空的栈，构造方法构造出来时都是纯空栈，到后面插入元素进来时会自动扩容的
1.2获取
1.2.1获取栈顶元素
stack.peek();
—> return E
获取栈数组后头大角标的元素即那一个处于栈顶的元素
1.2.2获取有效元素个数
stack.size();
—> return int
获取栈数组当前有效元素的个数
纯空栈 -> 有效元素个数为0且数组空间为0
空栈 -> 有效元素个数为0
1.2.3获取是否为空栈
stack.isEmpty();
—> return boolean
判断栈里面有效元素个数是否为0
1.3插入
stack.push(E);
—> return E
将元素插入栈顶并返回此插入的引用
1.4删除
stack.pop();
—> return E
将栈顶引用元素从栈数组中删除并返回此删除的引用
2.Queue
Queue接口里有最底层尾插头删单向队列操作的方法
Queue接口不能直接实例化，通过其实现类LinkedList或ArrarDeque来间接实例化有的
2.1获取
2.1.1获取队头元素
linkedlist.peek();
—> return E
2.1.2获取有效元素个数
linkedlist.size();
—> return int
获取队列中有效元素个数
2.1.3获取是否为空队列
linkedlist.isEmpty();
—> return boolean
判断队列有效元素个数是否为0队列是否为空
2.2插入
linkedlist.offer(E);
—> return boolean
在队尾后面插入元素
2.3删除
linkedlist.poll();
—> return E
删除队头元素，并返回此删除的引用元素