计算机软件基础：12第四章数据结构栈_队列.doc资源-CSDN文库

版权申诉

115 浏览量 2022-06-14 11:37:05 上传评论收藏 3.01MB DOC 举报

资源推荐

资源详情

资源评论

《计算机软件基础》多媒体教程

第十二讲

第四章数据结构

4.3 栈和队列

4.3.1 栈

※ 定义

⊙ 只能对始结点(又称始端)进行操作的线性表称为stack(栈，堆栈)。

⊙ 栈的始端称为栈顶，栈的终端称为栈底。

⊙ 栈的主要操作包括push(进栈)和push(出栈或者退栈)，它们只涉及到栈顶结点。

⊙ 进栈操作是指在栈顶添加一个结点，使原来的栈顶结点成为栈顶的下一结点。

⊙ 出栈操作是从栈内取出栈顶结点，并使原来的栈顶下一结点成为栈顶结点。

由此可以看到，最先进栈的结点将最后出栈。

因此，栈又被称为先进后出表，记为FILO表(First In Last Out List)。

※ 栈的基本操作和存储空间测试

设计一个栈，要给予分配一定的空间，因此在进栈或退栈操作时应注意到栈空间的变

化情况。

如果在满栈(结点已经占满栈的容量)时执行进栈操作，称为上溢出(overflow)。

如果在空栈(栈内没有结点)时执行出栈操作，称为下溢出(underflow)。

通常根据栈顶指针的变化来判断是否发生上溢出和下溢出。在程序实现时，必须对上

溢出和下溢出的情况加以处理，否则将引起出错。

※ 栈的存储方式

按照栈的存储方式，可以分为顺序栈和链接栈。

用顺序存储方式实现的栈称为顺序栈，通常可以用数组来构造顺序栈。

用链接存储方式实现的栈称为链接栈，通常可以用链表来构造链接栈。

【例4-3.1】栈的应用示例：铁路车厢编组

下图中铁路的右侧是一个车厢的堆栈，规定从上边轨道进入堆栈的操作为P(push)，从

堆栈退出进入下边轨道的操作为O(pop)。通过一系列的进栈和出栈操作，可以对火车车厢

进行重新编组。

例如经过 PPO 的操作，原来按 {1, 2, 3} 编组的车厢被牵引到各条轨道。而经过

PPOPOO的操作，原来按{1, 2, 3}编组的车厢可以重新编组为{2, 1, 3}的序列。

剩余12页未读，继续阅读

内容反馈

版权申诉

智慧安全方案

粉丝: 3623
资源: 59万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip