前言： 栈和队列都是基于List(线性表)来实现的，且其限制比List更严格(提供的操作更少)，即 List 比站栈和队列更灵活
栈的实际应用场景非常多，队列的实际应用场景更多
目录
- 栈 (Stack)
- 概念
- 栈的实现
- 队列 (Queue)
- 概念
- 队列的实现
- 以链表为例 不带傀儡节点
- 以数组为例
- 循环队列(高效操作)
- 栈和队列的方法
栈 (Stack)
概念
栈是限定仅在末尾进行插入和删除操作的线性表，表尾指栈顶，而不是栈底
栈限制了线性表的插入和删除位置，它始终在栈顶进行
则：栈底是固定的，最先进栈的只能在栈底
先进后出
只支持3个核心操作：入栈，出栈，取栈顶元素
JVM 的内存区域划分(JVM内存模型)，JVM虚拟机栈，此处的栈 特指JVM中的内存区域
而今天学习的栈是，数据结构中的通用概念
栈的实现
以数组为例： 相对简单，直接上代码：
public class MyStack1 {
//管理一些 int 元素，不考虑扩容问题
private int[] array = new int[100];
private int size = 0; //栈中存在多少个有效元素
//入栈
public void push(int x){
array[size] = x;
size++;
}
//取栈顶元素(最后进来的那个元素)
public int peek(){
return array[size-1];
}
//出栈
public int pop(){
int ret = array[size-1];
size--;
return ret;
}
}
队列 (Queue)
概念
先进先出
只支持3个核心操作：入队列，出队列，取队首元素
举例：食堂排队买饭，先来的同学排在前边，后来的排在后边，先来的先买到饭，后来的后买到饭
队列的实现
实现队列的方式有很多，可以使用数组来实现，也可以使用链表来实现
以链表为例 不带傀儡节点
public class MyQueue1 {
// Node 为内部类，定义在某个类或方法中的类
// static 的效果是，创建 Node 的实例不依赖 MyQueue的这个类的实例
static class Node{
public int val;
Node next = null;
//提供构造方法
public Node(int val) {
this.val = val;
}
}
//创建一个链表，需要一个头节点 此处以 不带傀儡节点为例
//使用链表实现队列，入队列从表头插入，出队列从表尾删除
// 或 入队列从表尾插入，出队列从表头删除
// 无论上述那种，都需要记录头尾
private Node head = null;
private Node tail = null;
//以 尾入头出 为例
//入队列 尾部插入
public void offer(int val){
Node newNode = new Node(val);
if(head == null){
head = newNode;
tail = newNode;
return;
}
//非空链表
tail.next = newNode;
tail = tail.next;
}
//出队列 头部删除
public Integer pull(int val){
//判定队列是否为空
if(head == null){
//若出队列失败，返回一个错误值
return null;
}
int ret = val;
head = head.next;
if(head == null){
//删除之后，队列变成空
tail = null;
}
return ret;
}
//取队首元素
public Integer peek(){
if(head == null){
return null;
}
return head.val;
}
}
此处出队列，返回值为Integer
.
若为 int，则返回一个错误值，例如：-1，0等
但若返回-1，就不清楚是出队列失败返回的-1，还是本来就返回的是-1，故 -1 不能做非法值
Integer 包装类，也是一个引用类型的对象，引用类型就可以是一个空引用，就可以表示非法情况
.
故：此处返回值不用 int，使用 Integer
.
以数组为例
一般我们会想到，入队列，即在数组后插入一个元素
而出队列，就会依次覆盖前一个元素(搬运操作)，但这样效率会比较低
下图所展现的过程就是低效的搬运过程：
循环队列(高效操作)
不用搬运也可完成出队列操作
画图表示：
当前队列中的有效元素就算是 [head，tail)
head 始终就是队首元素，tail 始终就是队尾的下一个元素
当 head 和 tail 重合时，此时队列为空
有效元素的情况：
- tail 在前，head 在后
- tail 在前，head 在后
- head 和 tail 重合
当 head 和 tail 重合时，可能是空队列也可能是满队列
- 空队列
- 满队列
模拟实现：
public class MyQueue2 {
private int[] array = new int[100];
//size 表示元素个数
private int size = 0;
// [head,tail) 表示有效元素，但tail 可能在 head之前
private int head = 0;
private int tail = 0;
//入队列
public void offer(int val){
//判定是否为满队列
if(size == array.length){
System.out.println("队列已满，无法插入！");
return;
}
array[tail] = val;
tail++;
//若tail++，超出了数组的有效范围，那么让tail从0开始
if(tail >= array.length){
tail = 0;
}
size++;
}
//出队列
public Integer poll(){
//判定是否为空队列
if(size == 0){
System.out.println("队列为空，无法删除！");
return null;
}
Integer ret = array[head];
head++;
if(head >= array.length){
head = 0;
}
size--;
return ret;
}
//取队首元素
public Integer peek(){
//判定是否为空队列
if(size == 0){
return 0;
}
return array[head];
}
}
栈和队列实现起来非常容易，复杂的就是结合实际场景来使用
栈和队列的方法
栈的方法
| 方法 | 作用 |
|---|---|
| Stack( ) | 定义一个空栈 |
| push( ) | 入栈 |
| pop( ) | 出栈(栈顶值) |
| peek( ) | 取栈顶值(不出栈) |
| empty( ) | 判断栈是否为空 |
代码示例：
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
//入栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println(stack.empty());
//出栈
int ret = stack.pop();
System.out.println(ret); //5
ret = stack.pop();
System.out.println(ret); //4
ret = stack.pop();
System.out.println(ret); //3
ret = stack.pop();
System.out.println(ret); //2
ret = stack.pop();
System.out.println(ret); //1
System.out.println(stack.empty());
}
输出结果：
验证了栈的 先进后出 的特性
若为空栈，在进行出栈，则可能发生异常
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
//入栈
stack.push(1);
//出栈
int ret = stack.pop();
System.out.println(ret);
ret = stack.pop();
System.out.println(ret);
}
标准库中的 Stack 如果为空，再次 pop / peek，都会抛出异常
队列的方法
一般建议使用 offer( )，poll( )，peek( ) 这组操作
| 方法 | 作用 | 错误处理 |
|---|---|---|
| offer( ) | 将指定元素插入队列 | 成功返回 true，否则返回 false |
| poll( ) | 取并移除队首元素 (出队列) | 队列为空，返回null |
| peek( ) | 取队首元素，但不出队列 | 队列为空，返回null |
| add( ) | 入队列 | 抛出 IllegalStateException 异常 |
| remove( ) | 取并移出队首元素(出队列) | 队列为空，抛出 NoSuchElementException 异常 |
| element( ) | 取队首元素，但不出队列 | 队列为空，抛出 NoSuchElementException 异常 |
- ①add( ) remove( ) element( ) 示例：
public static void main(String[] args) {
//初始化
Queue<Integer> queue = new LinkedList<>();
//入队列
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
//取队首元素 (不出队列)
System.out.println("使用element()取队首元素....");
System.out.println(queue.element());
System.out.println();
//出队列
System.out.println("使用remove()出队列....");
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
}
输出结果：
验证了队列的 先进先出 的特性
特殊情况：
- 队列为空，取队首元素
public static void main(String[] args) { Queue<Integer> queue = new LinkedList<>(); //取队首元素 (不出队列) System.out.println("使用element()取队首元素...."); System.out.println(queue.element()); System.out.println(); }输出结果：
.
.
- 队列为空，出队列
public static void main(String[] args) { Queue<Integer> queue = new LinkedList<>(); //出队列 System.out.println("使用remove()出队列...."); System.out.println(queue.remove()); }输出结果：
.
- ②offer( )，poll( )，peek( ) 示例：
public static void main(String[] args) {
//初始化
Queue<Integer> queue = new LinkedList<>();
//将指定元素插入队列
queue.offer(66);
queue.offer(88);
queue.offer(99);
System.out.println();
//取队首元素
System.out.println("使用peek()取队首元素....");
System.out.println(queue.peek());
System.out.println();
//出队列
System.out.println("使用poll()出队列....");
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
输出结果：
特殊情况：
- 队列为空，取队首元素
public static void main(String[] args) { //初始化 Queue<Integer> queue = new LinkedList<>(); //取队首元素 System.out.println("使用peek()取队首元素...."); System.out.println(queue.peek()); System.out.println(); }输出结果：
.
.
- 队列为空，出队列
public static void main(String[] args) { //初始化 Queue<Integer> queue = new LinkedList<>(); //出队列 System.out.println("使用poll()出队列...."); System.out.println(queue.poll()); System.out.println(); }输出结果：
.
由上述例子可知，第①组操作失败就会抛出异常，第②组操作失败会返回一个错误值
故：一般建议使用 offer( )，poll( )，peek( ) 这组操作
下篇我们会讨论有关栈和队列的面试题~~
