【Java数据结构】—栈与队列深度剖析
一、栈的基本概念
栈的定义：
栈是仅限定在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据的的栈称为空栈。
此外，栈又称为后进先出的线性表。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
如何理解栈的定义：
- 首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。区别在于栈是一种特殊的线性表。
- 定义中说的线性表的表尾进行插入和删除操作，这里的表尾指的是栈顶，而不是栈尾。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
二、栈的实现
- 利用顺序表实现，即使用尾插 + 尾删的方式实现
- 利用链表实现，则头尾皆可
相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。
import java.util.Arrays;
public class MyStack {
public int [] elem;
public int usedSize;
public MyStack(){
this.elem = new int[5];
}
//进栈
public void push(int val){
if(isFull()){
//扩容
Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize] = val;
this.usedSize++;
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
int oldVal = this.elem[usedSize - 1];
this.usedSize--;
return oldVal;
}
//获取栈顶元素
public int peek(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
return this.elem[usedSize-1];
}
//是否为空
public boolean isEmpty(){
return this.usedSize == 0;
}
}测试代码：
import java.util.Stack;
public class TestDemo {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack.pop());//弹出栈顶元素，并且删除4
System.out.println(stack.peek());//获取栈顶元素，但不删除3
System.out.println(stack.isEmpty());//false
}
}上面实现的栈，底层是一个数组，那么请问：我们能不能用单链表实现栈？
答案是可以的，我们用单链表实现栈满足以下条件：
- 先进后出
- 入栈和出栈的时间复杂度得都是O(1)
再来，链表可以头插法和尾插法，那么我们入栈使用的是头插还是尾插？
假如我们用的是尾插法，我们可以发现，我们出栈的时候每次都需要找尾巴，那么时间复杂度就是O（n)。
假如我们用的是头插法，时间复杂度则为O（1），因为出栈的时候，我们只需要删除头节点就可以了。
三、栈的注意事项
了解完栈的基本概念与实现，我们来看一下下面的这几个问题。
- 什么是栈？
- 什么是Java虚拟机栈？
- 什么是栈帧？
第一，什么是栈？ 栈其实就是一种数据结构。特点是先进先出。这里就是上面栈的基本概念。
第二，什么是Java虚拟机栈？
JVM内存结构分为五部分，如下图，而Java虚拟机栈是JVM中的一块内存。
第三，什么是栈帧？栈帧（Stack Frame）是用于支持虚拟机进行方法调用和方法执行的数据结构。它是虚拟机运行时数据区中的java虚拟机栈的栈元素。
栈帧存储了方法的局部变量表、操作数栈、动态连接和方法返回地址等信息。
每一个方法从调用开始至执行完成的过程，都对应着一个栈帧在虚拟机里面从入栈到出栈的过程。
四、队列的基本概念
定义：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）
五、队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
class Node{
public int val;
public Node next;
public Node(int val){
this.val = val;
}
}
public class MyQueue {
public Node head;
public Node last;
/** * 尾插法 * @param val */
public void offer(int val){
Node node =new Node(val);
if(head == null){
head = node;
last = node;
}else {
last.next = node;
last = last.next;
}
}
/** * 出队 * @return */
public int poll(){
if(isEmpty()){
throw new RuntimeException("队列为空");
}
int oldVal = head.val;
this.head = head.next;
return oldVal;
}
public boolean isEmpty(){
return this.head == null;
}
public int peek(){
if(isEmpty()){
throw new RuntimeException("队列为空");
}
return head.val;
}
}测试代码：
public class TestDemo {
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek());//1
System.out.println(queue.poll());//2
System.out.println(queue.poll());//3
System.out.println(queue.poll());//
}
}结果：
六、循环队列
定义：
队列头尾相接的顺序存储结构称为循环队列
如果理解这个定义呢？这里需要我们一步一步来。
下面内容很重要，请大家认真看。
6.1队列顺序存储的不足与解决方法
我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素,不需要移动任何元素，因此时间复杂度为O(1).
但问题是队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，就像我们平时排队一样，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为0(n)。
来到这里我们思考一下，我们在出队的时候，能不能不移动队列？也就说，我们能不能不把队头一定限定在下标为0的位置？
这里我们引入两个指针，一个是front指针，一个rear指针。
front指针指向队头元素，rear 指针指向队尾元素的下一个位置，这样当front等于rear时,就变成空队列了。
假设是长度为6的数组，初始状态，空队列如下左图所示，front与rear指针均指向下标为0的位置。然后入队 a1、a2、a3、a4、a5,front 指针依然指向下标为0位置，而rear指针指向下标为4的位置，如下的右图所示。
假如我们将a1出队列，则front往下移，如下图。
假如我们将元素a6、a7入队，我们会发现rear指针指向了数组之外，也就是溢出了。但事实上我们溢出了没有？很明显，前面还有空位，这个我们称为假溢出。
那如何解决假溢出的问题呢？
——————————————————采用循环队列
后面满了，就再从头开始，也就是头尾相接的循环。
我们把队列的这种头尾相接的顺序存储结构称为循环队列。
如果刚刚的例子中，我们的rear又重新指向了队头，这问题就可以解决了。
此时问题又出来了，我们刚才说，空队列时，front 等于rear，现在当队列满时，也是 front等于rear，那么如何判断此时的队列究竟是空还是满呢?
在这里，我们有两个办法解决这个问题。
方法一：
设置一个标志变量flag,当front == rear，且 flag=0时为队列空,当front == rear，且 flag =1时为队列满。
方法二：
办法二是当队列空时，条件就是 front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如下图所示，我们就认为此队列已经满了。
在实际的操作中，我们一般使用第二种比较多，所以我们这里重点介绍第二种。
由于rear可能比 front大，也可能比 front小，所以管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为 QueueSize，那么队列满的条件是：
(rear+1)%QueueSize == front(取模“%”的目的就是为了整合rear 与 front大小为一个问题)。
如下图，QueueSize = 6，front=2，而rear=1,(1+1)%6 = 2，所以此时队列满。
再如下图，front= 2而rear = 5。(5 +1) %6 ≠ 2 ，所以此时队列也是满的。
另外，当rear > front时，如下图，此时队列的长度为rear-front。
但当rear < front时，，队列长度分为两段，一段是 QueueSize-front,另一段是0 +rear,加在一起，队列长度为rear一front +QueueSize。
因此通用的计算队列长度公式为:
(rear- front + QueueSize)%QueueSize = length
其中：
length为当前队列的长度
rear为队列尾指针
front为队列头指针
QueueSize为队列可容纳的元素总数（即队列大小）
七、循环队列代码实现
public class MyCircleQueue {
public int[] elem;
public int front;//队头下标
public int rear;//队尾下标
public MyCircleQueue(int k) {
this.elem = new int[k];
}
/** * 入队 * @param value * @return */
public boolean enQueue(int value) {
if(isFull()) return false;
this.elem[rear] = value;
//rear++;
rear = (rear+1)% elem.length;
return true;
}
public boolean deQueue() {
if(isEmpty()) return false;
front = (front+1)% elem.length;
return true;
}
/** * 得到队头元素 * @return */
public int Front() {
if(isEmpty()) {
return -1;
}
return elem[front];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
int index = -1;
if(rear == 0) {
index = elem.length-1;
}else {
index = rear-1;
}
return elem[index];
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//判断队列是否已满
public boolean isFull() {
//rear的下一个是front
if( (this.rear+1) % elem.length == front) {
return true;
}
return false;
}
}八、双端队列
定义：
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
