数据结构·栈和队列

发布时间 : 2021-04-06 12:01

阅读 :

栈

栈(Stack)：只允许在一端插入或删除的线性表
栈顶：线性表允许进行插入或删除的那一端
栈底：固定的，不允许进行插入和删除的另一端
特点：是受限的线性表，拥有线性关系；后进先出LIFO

顺序栈

使用顺序存储，自底向上存储数据元素，指针指向栈顶元素的位置
操作

s.top = -1;             //判空
s.data[++s.top] = x;    //进栈
x = s.data[s.top--];    //出栈
x = s.data[s.top];      //读取栈顶元素

共享栈

两个栈共享一个一维数组空间
两个栈分别设置在共享空间两端
栈顶指向中间延伸位置
有利于空间使用

链式栈

采用链式存储
便于多个栈共享存储空间
效率高

队列

允许在一端插入，另一端删除的线性表
队头：允许删除的一端
队尾：允许插入的一端
先进先出FIFO

顺序队列

连续的存储单元
头指针指向队头元素
尾指针指向队尾元素

循环队列

首尾相连的顺序存储的队列
操作

Q.rear = Q.front = 0;                           // 初始化
rear = (rear + 1) % MaxSize;                    // 入队
front = (front + 1) % MaxSize;                  // 出队
queueLen = (rear + MaxSize - front) % MaxSize;  // 队列长度

判断空队列或满队列

// 使用一个单元区分队空或队满
(Q.rear + 1) % MaxSize = Q.front;   //
Q.front = Q.rear;                   //
// 类型中增加表示个数的数据成员
Q.size = 0;                         //
Q.size = MaxSize;                   //
// 增加tag成员
tag = 0;                            //
tag = 1;                            //

链式队列

双端队列

允许两端可以入队和出队
输出受限的双端队列：允许一端进行插入和删除，另一端只允许插入的双端队列
输入受限的双端队列：允许一端进行插入和删除，另一端只允许删除的双端队列

应用

栈在括号匹配的应用

算法思想

空栈，一次读入一个符号
右括号：使栈顶元素消解，或不合法（序列不匹配，退出程序）
左括号：放入栈顶，作为更高优先级的一个元素，栈为空，否则括号序列不匹配

栈在表达式中的应用

中缀表达式转换后缀表达式

栈在递归中的应用

原理：将原始问题转换为相同属性的小规模问题
求出递归表达式
边界条件（递归出口）

队列

队列在层次遍历的应用

队列在计算机系统中的应用

解决主机与外设之间速度不匹配的问题
解决多用户引起的资源竞争问题

特殊矩阵压缩存储

数组的存储结构

行优先：先存储行号较小的元素，行号相等先存储列号小的元素
列优先：先存储列好较小的元素，列号相等先存储行号小的元素

n阶对称矩阵

上三角、主对角线、下三角，其中上下三角元素相同
通常不使用二维数组存储，使用一维数组存储，元素$a_{ij}$在数组中下标为$k$
元素下标之间的对于关系
$i \ge j , k = \frac{i*(i-1)}{2+j}-1(下三角区和主对角线元素)$
$i < j , k = \frac{j*(j-1)}{2+i}-1(上三角区元素)$

n阶三角矩阵

下三角矩阵（上三角区元素为常量）和上三角矩阵（下三角矩阵元素为常量）
通常不使用二维数组存储，使用一维数组存储，元素$a_{ij}$在数组中下标为$k
下三角矩阵的的元素下表之间的对应关系

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 jaytp@qq.com