《数据结构》（C++）之第三章：栈和队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《数据结构》（C++）之第三章：栈和队列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4903字，纯文字阅读大概需要8分钟。
内容图文
3.1 栈
3.1.1 栈的逻辑结构
-
定义：栈是限定仅在表尾进行插入和删除操作的线性表
栈顶 | 允许插入和删除（表尾）
— | —
栈底 | 不允许插入和删除- 不含任何数据元素的栈称为空栈
-
特点：后进先出
3.1.2 栈的顺序存储结构及实现
-
顺序栈：栈的顺序存储结构称为顺序栈
-
使用数组实现
private: DataType data[StackSize]; //存放栈元素的数组 int top; //栈顶指针（栈顶元素在数组中的下标）
-
-
特点：通常把数组中下标为0的一端作为栈底，同时复设指针top指示栈顶元素在数组中的位置
-
操作：
-
（1）栈的初始化：top置为-1
if（top == -1)同时是判空操作
-
（2）入栈：
if(top == StackSize - 1) throw "上溢"; //检查上溢 data[++top] = x; //插入 -
（3）出栈：
if(top == -1) throw "下溢"; //检查下溢 x = data[top--]; //弹出 return x; //返回值
-
-
两栈共享空间
-
应用场景：同时使用具有相同数据类型的两个栈时，为了避免空间浪费
-
思想：数组的首尾两端分别为两个栈的栈底，栈顶都向中间延伸
- 栈满条件：
top1 = top2 - 1（或top1 + 1 = top2） - 出栈入栈可使用同一个方法，通过传入参数判断具体对哪个栈操作
- 栈满条件：
-
3.1.3 栈的链接存储结构及实现
-
链栈：栈的链接存储结构称为链栈
-
使用链表实现
Node<DataType> * top; //栈顶指针即链栈的头指针
-
-
特点：仅在链表的头部/尾部（头插法/尾插法）进行插入/删除操作
-
操作：（尾插法）
-
（1）栈的初始化：链栈不带头结点，将栈顶指针置空
-
（2）入栈：
s = new Node; //申请一个新的节点s s -> data = x; //更新节点的数据域为x s -> next = top; //指向上一个节点的地址 top = x; //更新top指向的节点 -
（3）出栈：（需要工作指针p用于摘链）
if(top == null) throw "下溢"; //检查栈空 x = top -> data; //取出top指向节点的数据 p = top; //暂存栈顶元素 top = top -> next; //栈顶指针指向上一个节点 delete p; //删除栈顶节点 return x; //返回被出栈的原栈顶元素的值 -
（4）判空：
top == null
-
3.1.4 顺序栈和链栈的比较
-
相同点：时间性能
- 出栈入栈的时间复杂度都是O（1）
-
不同点：空间性能
- 顺序栈长度固定，存在空间浪费问题
- 链栈没有栈满的问题，但每个元素都需要一个指针域，产生了结构性开销
3.2 队列
3.2.1 队列的逻辑结构
-
定义：队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表
队尾 允许插入（也称入队、进队）的一端 队头 允许删除（也称出队）的一端 -
特点：先进先出（单向移动性）
- 应用：排队系统
3.2.2 队列的顺序存储结构及实现
-
循环队列：队列的头尾相接，队头和队尾都是活动的（令出队入队操作的时间复杂度都是O(1)，而不需要移动元素到数组前端），需要设置队头、队尾两个指针
队头指针front 指向队头元素的前一个位置 队尾指针rear 指向队尾元素 - 使用数组实现
private: DataType data[QueueSize]; //存放队列元素的数组 int front, rear; //队头和队尾指针
- 使用数组实现
-
解决循环队列的假溢出问题
-
问题：队列存在“单向移动性”，当元素被插入到数组中下标最大的位置上后，队列的空间会被判定为用尽
-
解决思想：将存储队列的数组看成头尾相接的循环结构，即允许队列直接从数组中下标最大的位置延续到下标最小的位置
- 因为数组查找的特性，取出队头元素的时间复杂度还是O(1)
-
实现方法（1）：通过 取模操作 实现
-
队空条件：
rear = front -
队满条件：
(rear + 1) % QueueSize = front- 为与队空条件区分，浪费一个数组元素空间 将临界状态视为队满
-
-
实现方法（2）：设置num为构成队列的数组空间数量，以计算剩余空间
-
-
操作：
-
（1）循环队列的初始化：将队头指针和队尾指针同时指向数组的某一个位置（一般是数组的高端）
rear = front = QueueSize - 1; -
（2）入队：
if ((rear + 1) % QueueSize == front) throw "上溢" //入队的时候判断是否已满 rear = (rear + 1) % QueueSize; //队尾在循环的意义上加1 data[rear] = x; //在队尾插入元素 -
（3）出队：不需要删除操作，新的数据覆盖旧的数据
if(rear == front) throw "下溢"； //出队的时候判空 front = (front + 1) % QueueSize; //队头在循环意义下加1 return data[front]; //读取并返回出队前的元素
-
3.2.3 队列的链接存储结构及实现
-
链队列：加入头结点（为使空队列与非空队列操作一致）的链表实现队列
队头指针 指向链队列的头结点 队尾指针 指向终端结点 
-
队空条件：
front = rear -
操作：
- （1）链队列初始化：
s = new Node; //申请一个新的结点作为头结点 s -> next = null; //头结点的后继置空 front = rear = s; //将队头指针和队尾指针都指向头结点 - （2）入队：
s = new Node; //申请一个新结点 s -> data = x; //新结点的数据域为插入数据的值 s -> next = null; //新结点的后继为null rear -> next = s; //尾指针指向结点的后继指向新结点 rear = s; //尾指针指向新结点 - （3）出队：（需要工作指针p用于摘链）
if (rear == front) throw "下溢"; //判断队列是否为空 p = front -> next; //将工作指针指向即将出队结点 x = p -> data; //保存即将出队结点的值 front -> next = p -> next; //将头结点的后继指向新的队列的第一个元素 if (p -> next == null) rear = front; //如果即将出队结点的后继为空，则证明此结点为队列中最后一个结点，将尾指针指向头结点（恢复初始化状态） delete p; //摘链 return x; //返回出队结点的值
- （1）链队列初始化：
3.2.4 循环队列和链队列的比较
-
相同点：时间性能
- 出队入队的时间复杂度都是O（1）
-
不同点：空间性能
- 循环队列长度固定，存在空间浪费问题
- 链队列没有栈满的问题，但每个元素都需要一个指针域，产生了结构性开销
3.3 表达式求值
| 名称 | 表示 | 别名 |
|---|---|---|
| 前缀式 | +ab | 波兰表达式 |
| 中缀式 | a+b | |
| 后缀式 | ab+ | 逆波兰表达式 |
内容总结
以上是互联网集市为您收集整理的《数据结构》（C++）之第三章：栈和队列全部内容，希望文章能够帮你解决《数据结构》（C++）之第三章：栈和队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。