山东大学《数据结构》讲义03栈和队列.docx资源-CSDN文库

199 浏览量 2022-12-15 23:25:42 上传评论收藏 55KB DOCX 举报

资源推荐

资源详情

资源评论

第三章栈和队列

内容概述

从数据结构角度来看，栈和队列是两种特殊的线性表，其特殊性表达在它们的基本

操作是线性表操作的子集，因此它们是限定性的数据结构。从抽象数据类型角度来看，

它们是不同于线性表的两类重要的抽象数据类型。由于栈和队列在实际应用中的广泛

性和其操作的特殊性，本章从栈和队列的抽象数据类型定义、栈和队列的顺序表示与

实现、栈和队列的链式表示与实现、栈和队列的应用等几个方面进行专门讨论。

重点与难点

重点为栈和队列的运算，循环队列。难点为栈与递归的关系，栈与队列的应用。

思考.栈是具有什么特性的线性表？

1 .队列是具有什么特性的线性表？

2 .分析栈与递归的关系。

3 .假设一个栈的入栈序列是1, 2, 3,…,n,其输出序列为pl,p2,p3,…,pn, 假设 pl=n,那

么 pi=?

4 .设有一个顺序栈S,元素sl,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为

s2,s3,s4,s6,s5

sl,那么顺序栈的容量至少应为多少？

5 .为什么要循环队列？在循环队列中队列空、满的评定标准是什么？

6 .利用两个栈模拟一个队列的入队、出队、判断队空等运算。

第一节栈栈是一种具有''后进先出〃特性的线性表。这种特性对其操作有何影响呢？

其存储结构相对于一般线性表又会有哪些变化？本节将从栈的定义、抽象类型定义、

栈的顺序与链式存储结构等方面入手解答上述问题。

1、栈的定义1、栈的定义

栈(Stack)又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问只能在某一端

进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶

(Top),另一端称为栈底(Bottom) o栈顶的第一个元素被称为栈顶元素。不含数据元素

的空表称为空栈。

向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成

为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使

其下面的相邻元素成为新的栈顶元素。

堆栈的性质决定它的数据是按''先进后出〃的顺序被访问，即最先存储的元素最后被

访问、删除，最后存储的元素最先被访问、删除，所以栈也称为、'LIFO〃

(Last_In,First_Out) □栈的模型在日常生活中是普遍存在的，如铁路列车调度系统

等，在计算机科学中, 栈是一种非常有用的数据结构。实际上，TurboC在将参数传

递给函数时，就使用堆栈。

我们应该注意到：栈是一种动态的数据结构，也就是说，随着对栈进行插入和删除等

不同的操作，其结点个数、内容等将会不断发生变化。

径。如图35 图中路径为该迷宫探索的全过程，包含退回至「前一通道块〃的操作过

程。

本算法的描述如下：

StatusMazeRath(MazeTypemaze,RosTypestart,PosTypeend){〃假设迷宫maze

中存在从入口 start到出口 end的通道，那么求得一条路径存放在

)

)算法3-13迷宫求解算法

4、栈与递归实现的关系4、栈与递归实现的关系

栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一

系列的调用语句间接地调用自己的函数，称作递归函数。

在程序设计中，递归是一个非常重要的工具。第一，有很多数学函数是通过递归

定义的，比方阶乘函数：

和 2 阶 Fibonacci 数歹(J：

等；第二，由于有的数据结构本身固有的递归特性，它们的操作可以通过递归进行描

述，比方二叉树、广义表等；第三，有的问题虽然本身不具备明显的递归结构，但是

运用递归进行问题的求解相比迭代方法更简单，比方八皇后问题、Hanoi 塔问题等。

作为递归函数，在其执行过程中，需要屡次进行自我调用。为了理解这个问题，

我们先看任意两个函数之间是如何进行调用的。在高级语言编制的程序中，调用函数

和被调用函数之间的链接及信息交换需要通过栈来进行。通常，当在一个函数的运行

期间调用另一个函数时，系统在运行被调用函数前要先完成以下工作：(1)将所有的实

在参数、返回地址等信息传递给被调用函数保存；(2)为被调用函数的局部变量分配存

储区；(3)将控制转移到被调用函数的入口。同样，从被调用函数返回调用函数前，系

统也需要完成一些工作：(1)保存被调用函数的计算结果；(2)释放被调用函数的数据

区；(3)依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套

调用时，按照''后调用先返回〃的原那么，上述函数之间的信息传递和控制转移必须

通过栈来实现。系统设置一个栈作为整个程序运行时所需的数据空间，每调用一个函

数就为其在栈顶分配一个存储区，每从一个函数退出时就释放其存储区，那么当前正

运行的函数的数据区必在栈顶。实际上，在调用函数和被调用函数之间不一定传递参

数的值, 也可以传递参数的地址。通常，每个程序设计语言都有它自己的参数传递方法。

下面举一个例子来具体说明函数调用的工作原理。在图3,6(c)所示的程序段中, 主函数

main中调用了函数first,而在函数first中又调用了函薮second,那么当前系统正在执行

函数second中某个语句时栈的状态如图3.6(a),从函数second 退出后正执行函数first中

某个语句时栈的状态如图3.6(b)。注意，图中语句标号表示返回地址。

一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是

同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的''层次假设调

用该递归函数的主函数为第0层，那么从主函数调用递归函数为进入第1层；一般地，

从第i层递归调用本函数为进入''下一层〃，即第i+1层。反之，从第i+1层递归退出返

回至''上一层〃，即第i层。

5、汉诺塔问题的算法5、汉诺塔问题的算法

(1)问题的提出

19世纪，欧洲出现了一个称为''汉诺塔〃的游戏，该游戏表示(毫无疑问是伪造

的)Brahma寺庙地下通道中的一个任务。在世界产生初期，牧师得到一个镶嵌着3根钻

石针的黄铜平台。第一根针上堆积着64个金圆盘，每一个金圆盘比它下面的金圆盘稍

微小一些(在欧洲流行的特殊版本为具有8个纸圆盘和3个木质柱子)。牧师被赋予一项

任务，将所有的金圆盘从第一根针移动到第三根针, 遵从的规那么是：每一次只能移动

一个金圆盘，移动过程中可以借助第二根针，金圆盘不能放在比它小的金圆盘之上。

牧师还被告知当完成这64个金圆盘的移动之后，将昭示着世界末日的到来。

当然，我们的任务是编写一个计算机程序，为牧师列出一个移动金圆盘的指令列

表。这个任务可以使用如下指令：

剩余23页未读，继续阅读

评论收藏

内容反馈

matlab大师

粉丝: 2434
资源: 9万+

山东大学《数据结构》讲义03栈和队列.docx

《数据结构及其应用》笔记含答案 第三章_栈和队列.docx

山东大学《数据结构》实验指导03栈与队列.docx

2数据结构实验报告二(栈和队列及其应用).docx

数据结构实验-栈和队列.docx

栈和队列的基本操作及其应用数据结构实验报告书.docx

数据结构实验报告(2) - 栈与队列.docx

数据结构实验报告—栈及其应用.docx

是栈还是队列.docx

武汉理工大学数据结构及算法综合实验连连看.docx

运动会分数统计数据结构课程设计含源代码.docx

(完整版)数据结构实验报告全集_1.docx

数据结构实验报告——栈和队列.docx

数据结构_栈与队列.docx

数据结构实验报告-栈和队列.docx

数据结构实验报告+栈和队列.docx

数据结构模拟试卷.docx

数据结构-实验4-循环队列的实现和运算.docx

山东大学《数据结构》讲义04树和二叉树.docx

2、上机实验报告二栈与队列.docx

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

农村公交与异构无人机协同配送优化

李飞飞自传 我看见的世界 The World I see

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

4个亲测好用的ChatGPT4渠道

基于小波与卷积神经网络的多尺度时间序列分类.zip

最新资源

《数据结构及其应用》笔记含答案第三章_栈和队列.docx

李飞飞自传我看见的世界 The World I see