第 3 章 栈 队列 数组
3.1. 栈
3.1.1. 定义
后进先出
数学性质
个不同元素进栈,出栈元素不同排列的个数为
3.1.2. 栈的形式
- 数组栈
- 链栈
3.2. 队列
3.2.1. 定义
先进先出
3.2.2. 顺序存储结构
1. 顺序队列
#define MaxSize 50struct SeqQueue { int data[MaxSize]; int front, rear;}
- 队空:
Q.front == Q.rear == 0
- 入队:
if ( !Q.full() ) { Q.rear = x; Q.rear++; }
- 出队:
if ( !Q.empty() ) { int temp = Q.front; Q.front++; return temp; }
然而,这种队列存在假溢出的现象,需要进行改进。
2. 循环队列
- 初始:
Q.front == Q.rear == 0
- 队首指针进一:
Q.front = (Q.front + 1) % MaxSize
- 队尾指针进一:
Q.rear = (Q.rear + 1) % MaxSize
- 队列长度:
(Q.rear - Q.front + MaxSize) % MaxSize
此时,队空和队满的条件相同,难以区分。可以采用 “牺牲一个元素的位置” 来决定队列是否满。
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
value | a | b | c | |||||||
pointer | front | rear |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
value | a | b | d | e | f | g | h | i | j | |
pointer | rear | front |
- 队满条件:
(Q.rear + 1) % MaxSize == Q.front
- 队空条件:
Q.rear == Q.front
- 队列元素数量:
(Q.rear - Q.front + MaxSize) % MaxSize
其他方法,如增加一个 tag
表明是否满,均可。
#[derive(Debug)]struct LinkQueue { front: usize, rear: usize, max_size: usize, data: Vec<i32>,}
impl LinkQueue {
pub fn new(max_size: usize) -> Self { let mut data = Vec::<i32>::new(); data.resize(max_size, 0); LinkQueue { front: 0, rear: 0, data, max_size } }
pub fn is_empty(&self) -> bool { self.front == self.rear }
pub fn is_full(&self) -> bool { (self.rear + 1) % self.max_size == self.front }
pub fn push(&mut self, x: i32) -> Option<i32> { if self.is_full() { return None; } self.data[self.rear] = x; self.rear = (self.rear + 1) % self.max_size; Some(x) }
pub fn pop(&mut self) -> Option<i32> { if self.is_empty() { return None; } let x = self.data[self.front]; self.front = (self.front + 1) % self.max_size; Some(x) }}
3.2.4. 双端队列
- 两头进,两头出
- 受限的双端队列
- 两头进,一头出
- 一头进,两头出
3.3. 栈和队列的应用
3.3.4. 队列在层次遍历中的作用
- 根节点入队
- 若队空,则退出;否则重复下一步
- 队头出队,并访问它。将它的所有(未访问的)子节点添加到队尾。返回上一步
3.4. 数组和特殊矩阵
3.4.3. 特殊矩阵的压缩存储
- 压缩矩阵:为多个值相同的元素只分配一个存储空间,对零元素不分配存储空间。目的是节省存储空间
- 特殊矩阵:具有许多相同矩阵元素或令元素,并且这些相同矩阵元素或零元素的分布有一定的规律性。常见的有对称矩阵、上(下)三角、对角阵等
1. 对称矩阵
用下三角区存储
只需要 个元素的空间,元素 在数组中的索引
用上三角区存储
只需要 个元素的空间,元素 在数组中的索引
2. 三角矩阵
将 压缩存储在 中,前面 个为数组元素,最后一个为常数
下三角
元素 在数组中的索引
上三角
元素 在数组中的索引
3. 三对角矩阵
元素 在数组中的索引
3.4.4. 稀疏矩阵
使用三元组存储