主要学习知识点
- 栈的概念及其抽象数据类型描述
- 顺序栈类和链栈的描述和实现
- 队列的概念及其抽象数据类型描述
- 顺序循环队列类和链队列类的描述与实现
一、栈
1. 概念：
- 栈的定义： 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
- 通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
- 当表中没有元素时称为空栈。
- 栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
2. 栈的抽象数据接口
public interface IStack<E> {
public void clear();//清空栈
public boolean isEmpty();//是否空栈
public int size();//栈数据元素的个数
public E peek();//读取栈顶元素
public void push(E e);//进栈
public E pop();//出栈，并返回该元素。
}
3. 顺序存储结构及实现
3.1栈及其操作示意图.png
3.2顺序栈存储结构.png
- 入栈操作
-
注意：
- 顺序栈为空的条件是 top == 0
- 顺序栈满的条件尾 top == stackElem.length
- 栈的长度为top
- 栈顶元素的下标为 top -1
-
入栈示意图
3.3入栈操作的相应变化.png 具体实现
public void push(E e) {
//检查栈是否已满
if (top == elementData.length)
throw new RuntimeException("栈已满！");
//存储元素
elementData[top] = e;
//栈顶指针 加一
top++;
}
- 出栈操作
-
示意图
3.4出栈操作.png - 具体实现
// 获取栈顶元素
public E peek() {
//判断是否为空栈
if (isEmpty())
throw new RuntimeException("栈为空！");
return (E) elementData[top - 1]; //返回栈顶元素;
}
//出栈
public E pop() {
E peek = peek();
//置空出栈元素
elementData[top - 1] = null;
//栈顶指针减一
top--;
return peek;
}
4. 链式栈及其实现
3.5链式栈存储结构.png
- 入栈操作
-
示意图
3.6链栈入栈示意图.png 代码实现
public void push(E e) {
//创建节点
LNode node = new LNode(e);
//修改栈顶指针
node.next = top;
top = node;
//栈长度加一
length++;
}
- 出栈操作
-
示意图
3.7链栈出栈示意图.png 代码实现
//获取栈顶元素
public E peek() {
if (isEmpty())
throw new RuntimeException("栈为空！");
return top.data;
}
//出栈
public E pop() {
//获取栈顶元素
E pop = peek();
//修改栈顶指针
top = top.next;
//栈长度减一
length--;
return pop;
}
二、队列
1. 定义：
- 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
- 队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
3.15队列及其操作示意图.png
2. 队列抽象接口定义
/**
* 队列接口
*/
public interface IQueue<T> {
void clear();//清空队列
boolean isEmpty();//判断空队列
int size();//队列长度
T peek(); //读取队首元素
void offer(T t);//入队列
T poll();//出队列
}
3. 顺序队列及其实现
- 出入队列示意图
3.16顺序队列入出队列示意图.png
- 假溢现象
出现原因：
- 如出入队列的示意图
- 在初始化一个长度为6的队列
- 先入队列A、B、C，然后A、B又出队列，造成对头有两个位置空置
- 接着E、F、G入队后，如果想H入队，这时必定会引起数组越界异常
- 队列有空间，但不能入队的溢出现象称为假溢现象
解决方式：
- 采用首尾相连的循环顺序队列，避免出现出队后空出存储空间
循环顺序队列的四种状态图
3.17循环顺序队列的四种状态图.png
- 解决无法区分队空和队满的状态问题(front: 队首指针，rear:队尾指针, maxSize:容量大小)
方法一、采用少存一个存储单元的方法
- 队空判断条件为： front == rear
- 队满判断条件：front == (rear+1) % maxSize
3.18少用一个存储单元实现循环队列的方式.png
设置一个标志变量：flag, 其初始值为flag = 0, 入队flag = 1, 出队列flag = 0
- 队空判断条件为： front == rear && flag == 0
- 队满判断条件：front == rear && flag == 1
设置一个计数器: length , 入队length ++; 出队length--
- 队空判断条件为： length == 0
- 队满判断条件：length >0 && front == rear
4. 链式队列及其实现
-
示意图
3.19链式队列存储结构.png -
入队列操作
3.20链式队列入队列操作.png
- 代码实现
public void offer(T t) {
// 创建节点
LNode<T> node = new LNode<T>(t);
//判断队列是否为空,空则赋值为队首和队尾指针
if (isEmpty()) {
front = rear = node;
} else {
//不为空，则插入队尾
//队列的尾节点的指针指向新节点
rear.next = node;
//尾指针指向新节点，作为新尾节点4
rear = node;
}
//长度加一
++length;
}
- 出队列
//获取队首元素
public T peek() {
//判断是否为空队列
if (isEmpty())
throw new RuntimeException("队列为空！");
return front.data;
}
//出队列
public T poll() {
//获取队首元素
T poll = peek();
//修改队首指针
this.front = this.front.next;
//长度减一
--length;
//返回数据
return poll;
}
三、 栈和队列的区别
相同点
- 都是线性结构，元素之间具有“一对一”的逻辑关系
- 插入操作都是再表尾进行
- 都可以使用顺序存储结构或链式存储结构实现
- 在时间代价上，插入删除操作的时间复杂度都是O(1), 在空间待见上也相同
不同点
- 删除操作的位置不同，栈只在表尾操作，队列在表头操作
- 栈是后进先出（LIFO），队列是先进先出（FIFO）,应用场景不同
- 顺序栈可以多栈空间共享，而顺序队列不同
