资源简介

(共55张PPT)
第3章 栈与队列
栈的概念
栈的顺序存储
栈的链式存储
队列的概念
队列的顺序存储
队列的链式存储
栈的概念
栈的链式存储
3.2
3.3
3.1
点击查看本小节知识架构
点击查看本小节知识架构
点击查看本小节知识架构
队列的概念
3.4
点击查看本小节知识架构
队列的顺序存储
3.5
点击查看本小节知识架构
队列的链式存储
3.6
点击查看本小节知识架构
栈的顺序存储
学习目标
了解
掌握
掌握
掌握
了解栈与队列的基本概念
1
掌握顺序队列的定义与代码编写方法
4
2
掌握顺序栈的定义与代码编写方法
3
掌握链式栈的定义与代码编写方法
本章将主要介绍两种典型的数据结构——栈与队列，栈与队列都是基于线性表的数据结构类型，其数据元素之间仍然满足线性结构。栈与队列可以通过不同的物理结构实现，如顺序存储与链式存储。因此，栈又可以分为顺序栈与链式栈，队列同样可以分为顺序队列与链式队列。本章将从栈与队列的数据操作分析入手，详细介绍代码的编写方法。
3.1 栈的概念
3.1.1
栈的定义
返回目录
3.1.2
栈的运算
3.1.1 栈的定义
栈是一种运算受限制的线性表，其只允许在表的一端进行插入和删除操作，俗称堆栈。允许进行操作的一端称为“栈顶”，另一个固定端称为“栈底”，当栈中没有元素时称为“空栈”。
例如，栈(a 1 ,a 2 ,a 3 ,… ,a i )，其中 a 1为栈底结点，而a i 为栈顶结点。如果需要插入或删除结点，只能从栈顶操作，插入结点称为入栈，删除结点称为出栈，如图所示。
由图可知，栈中的数据在入栈和出栈时，遵循后进先出的原则。这类似于手枪的子弹夹，最先装入的子弹，最后出膛击发。
3.1.2 栈的运算
栈的运算指的是对栈中的数据进行操作，其具体实现与栈的物理结构有关。栈常见的几种运算如下。
（1）判栈空：判断栈是否为空。
（2）取栈顶：获取栈顶结点的数据。
（3）入栈：将结点压入栈的顶部。
（4）出栈：移出栈顶结点。
3.2 栈的顺序存储
3.2.1
顺序栈的定义
返回目录
3.2.2
顺序栈的创建
3.2.3
入栈
3.2.4
出栈
3.2 栈的顺序存储
3.2.5
显示结点数据
返回目录
3.2.6
整体测试
3.2 栈的顺序存储
栈采用顺序存储称为顺序栈，顺序栈是顺序表的一种，是运算受限制的顺序表，具有与顺序表相同的存储结构。
3.2.1 顺序栈的定义
在C语言程序中，栈用数组表示，配合数组下标表示的栈顶指针完成各种操作。代码如下所示。
由以上代码可知，结构体中的第1个成员为一维数组，使用该数组表示栈，数组中保存的元素为栈的数据结点；结构体中的第2个成员top表示栈顶指针，其初始值为0，表示栈中没有数据结点，每压入一个数据结点，top的值加1。如图所示。
3.2.2 顺序栈的创建
在对栈中的数据结点进行操作之前，需要先创建一个空栈。假设一个结点所占的空间大小为L，栈中的结点有n个，则栈所占的空间为n*L。但实际的情况是栈中的结点数是不确定的，其占有的内存空间也是不确定的，因此需要先分配max*L个连续的内存空间，使其能存储max个结点。
通过代码实现创建空栈，示例代码参考教材3.2.2节。
如例所示，创建空栈只需为结构体在内存上申请一块连续的空间，并将表示栈顶指针的top置为0，表示栈中没有任何结点。
3.2.3 入栈
3.2.2节已经完成了创建空栈的操作，接下来将通过代码展示如何向栈中压入数据结点。在压入数据结点之前，需要判断栈是否为满，如果为满则不允许入栈，否则会造成数据在内存上越界。
压入数据结点需要先判断栈是否为满，代码如下所示。（变量定义与例3-1一致）。
栈未满即可进行入栈操作，代码如下所示。（变量定义与例3-1一致）。
3.2.3 入栈
由以上述代码可知，入栈只需要将新压入的数据保存至表示顺序栈的数组中即可。
3.2.4 出栈
在移出数据结点之前，需要判断栈是否为空，如果为空，表示没有数据可以移出。代码如下所示。（变量定义与例3-1一致）。
栈非空即可执行出栈操作，代码如下所示。（变量定义与例3-1一致）。
3.2.4 出栈
由上述代码可知，出栈只需要将栈顶top值减1即可。
执行入栈或出栈时，都可以通过当前top值及时获取栈顶结点的数据，代码如下所示。（变量定义与例3-1一致）。
3.2.5 显示结点数据
显示栈中所有结点的数据，代码实现如下所示。（变量定义与例3-1一致）。
3.2.6 整体测试
将3.2.3节、3.2.4节、3.2.5节的功能代码与例3-1结合，测试数据操作是否成功，具体示例点参考教材3.2.6节。
例中，主函数主要用于测试子函数是否正确。首先执行入栈操作，并通过显示数据判断入栈是否成功；然后执行出栈操作并显示出栈数据。输出结果如下所示。
由输出结果可以看出，数据入栈成功，数据出栈成功。
3.3 栈的链式存储
3.3.1
链式栈的定义
返回目录
3.3.2
链式栈的创建
3.3.3
入栈
3.3.4
出栈
3.3 栈的链式存储
3.3.5
显示结点数据
返回目录
3.3.6
整体测试
3.3 栈的链式存储
栈采用链式存储称为链式栈，链式栈是单链表的一种，是运算受限制的单链表，具有与单链表相同的存储结构。
3.3.1 链式栈的定义
链式栈作为单链表的一种，其插入操作与删除操作均在链表头部进行，链表尾部就是栈底，头指针就是栈顶指针，如图所示。
由图可知，链式栈中的结点结构与单链表一致，代码如下所示。
3.3.2 链式栈的创建
在对链式栈中的数据进行操作之前，需要先创建一个空的链式栈。通过代码实现创建一个空的链式栈，如例所示。
3.3.2 链式栈的创建
由以上述代码可知，创建空栈与创建单链表一致，都是为头结点申请内存空间。
3.3.3 入栈
3.3.2节已经完成了创建空栈的操作，接下来将通过代码展示如何向栈中压入数据结点。链式栈不同于顺序栈，不需要设定栈的大小，因此也不需要判断栈是否为满。
入栈采用单链表操作中的头插法，最先插入的数据结点成为栈底。代码如下所示。（变量定义与例3-3一致）。
3.3.4 出栈
在移出数据结点之前，需要判断栈是否为空，如果为空，则没有数据可以移出。代码如下所示。（变量定义与例3-3一致）。
栈非空即可执行出栈操作，出栈采用单链表操作中的头删法，最后删除的数据结点为栈底。代码如下所示。（变量定义与例3-3一致）。
3.3.5 显示结点数据
显示栈中所有的结点数据，代码如下所示。（变量定义与例3-3一致）。
3.3.6 整体测试
将3.3.3节、3.3.4节、3.3.5节的功能代码与例3-3结合，测试数据操作是否成功，示例代码参考教材3.3.6节。
例中，主函数主要用于测试子函数是否正确。首先执行入栈操作，并通过显示数据判断入栈是否成功；然后执行出栈操作并显示出栈数据。输出结果如下所示。
由输出结果可以看出，数据入栈成功，数据出栈成功。
3.4 队列的概念
3.4.1
队列的定义
返回目录
3.4.2
队列的运算
3.4.1 队列的定义
队列同样是一种运算受限制的线性表，是只能在两端进行插入和删除操作的线性表。允许进行插入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”，当队列中没有元素时，队列称为“空队”。
例如，队列(a 1 ,a 2 ,a 3 ,… ,a i )，其中 a 1 为队头，而a i 为队尾。如果需要删除结点，只能从队头操作；如果需要插入结点，只能从队尾操作。如图所示。
由图可知，队列中的数据在进行入队和出队时，遵循先进先出的原则。这类似于生活中排队办理业务，站在队头的人最先办理业务。
3.4.2 队列的运算
队列的运算指的是对队列中的数据进行操作，其具体实现与队列的物理结构有关。队列常见的几种运算如下。
（1）判队空：判断队列是否为空。
（2）取头结点：获取队列头结点的数据。
（3）入队：将结点插入队列的尾部。
（4）出队：删除队列头结点。
3.5 队列的顺序存储
3.5.1
顺序队列的定义
返回目录
3.5.2
顺序队列的创建
3.5.3
入队
3.5.4
出队
3.5.5
整体测试
3.5 队列的顺序存储
队列采用顺序存储称为顺序队列，顺序队列是顺序表的一种，是运算受限制的顺序表，具有与顺序表相同的存储结构。
3.5.1 顺序队列的定义
在C语言程序中，顺序队列使用一维数组表示。队列的操作只能在队头与队尾进行，且不移动队列中的结点。代码如下所示。
3.5.1 顺序队列的定义
由以上代码可知，结构体中的第1个成员为一维数组，使用该数组表示队列，数组中保存的元素为队列的数据结点；结构体中的第2个成员front表示当前队头结点的数组下标，第3个成员rear表示当前队尾结点的数组下标。如图所示。
3.5.2 顺序队列的创建
在对队列中的数据结点进行操作之前，需要先创建一个空队列。假设一个结点所占的空间大小为L，队列中的结点有n个，则队列所占的空间为n*L。但实际的情况是队列中的结点数是不确定的，其占有的空间大小也是不确定的，因此需要先分配max*L个连续的内存空间，使其能存储max个结点。
通过代码实现创建空队列，示例代码参考教材3.5.2节。
由例可知，创建空顺序队列只需为结构体在内存上申请一块连续的空间，并将表示队头和队尾结点的数组下标置为0，表示顺序队列中没有任何结点。
3.5.3 入队
3.5.2节已经完成了创建空顺序队列的操作，接下来将通过代码展示如何向队列中添加数据结点。在添加数据结点之前，需要判断顺序队列是否为满，如果为满则不允许加入添加结点，否则会造成数据在内存上越界。
顺序队列的数据结点处理比较特殊，如图所示。
3.5.3 入队
图中，初始时顺序队列为空，front与rear初始值为0；当顺序队列为满时，front值不变，rear值为6；删除两个结点后，front值为2，rear值不变。
由图可知，删除前两个结点后，顺序队列未满，可以选择继续添加数据结点。添加数据结点意味着rear值继续增大，但此时rear值已经为最大值，无法继续增大，这导致存储前两个结点的空间将无法继续使用，这种情况称为“溢出”。
针对上述情况，为了满足队列未满即可插入以及队列未空即可删除的需求，需要将顺序队列抽象为一个循环的表，这种意义下的顺序队列称为循环队列，如图所示。
3.5.3 入队
为了实现循环并且能够判断队列的状态是空或满，队列中必须预留一个结点的空间，即这一个结点的空间不用来存储数据。图所示的循环队列只是一种逻辑上的抽象，为了达到这一效果，只需要让front与rear值执行循环。简单地说，即front与rear的值增加到最大后，可以从0开始继续增加。
将上述思想应用到实际的队列，如图所示。
3.5.3 入队
假设队列最多可存储的结点数N为4（数组大小为5）。如图（a）所示，初始队列为空时，front、rear初始值都为0。如图（b）所示，1个结点入队后，front值不变，rear值加1。如图（c）所示，4个结点入队后，队列状态为满，front值不变，rear值加4，最后一个结点空间不存储数据。如图（d），2个结点出队后，front值加2，rear值不变。如图（e）所示，再次插入2个结点后，front值不变，rear值加2后变为1。
综上所述，在rear值加到最大值N后，再添加结点，rear值会重新变为0。同理，在front值加到最大值N后，再删除结点，front值会重新变为0。
从图中可以得到的规律是，rear值在任何时刻都等于留空结点的数组下标值。
添加数据结点需要先判断队列是否为满，代码如下所示。（变量定义与例3-5一致）。
3.5.3 入队
图（c）与图（e）所示的队列都为满，且front值等于rear值加1。以上代码中rear值加1对N取余，使得rear值可以无限次增加，实现循环。
队列未满即可进行入队操作，代码如下所示。（变量定义与例3-5一致）。
3.5.4 出队
在执行出队之前，需要判断顺序队列是否为空，如果为空，没有数据可以移出。代码如下所示。（变量定义与例3-5一致）。
由图（a）可知，当front值与rear值相等时，顺序队列为空。除此之外，顺序队列在经历多次入队、出队（front、rear值多次增加、取余）后，也可能会出现两个值相等情况，如图所示。
3.5.4 出队
队列非空即可执行出队操作，代码如下所示。（变量定义与例3-5一致）。
3.5.5 整体测试
将3.5.3、3.5.4节的功能代码与例3-5结合，测试数据操作是否成功，示例代码参考教材3.5.5节。
例中，主函数主要用于测试子函数是否正确。首先执行入队操作，然后执行出队操作，并通过显示出队数据，判断顺序队列是否遵循先进先出的规则。输出结果如下所示。
由输出结果可知，数据入队成功，出队时，最早入队的数据先出队。
3.6 队列的链式存储
3.6.1
链式队列的定义
返回目录
3.6.2
链式队列的创建
3.6.3
入队
3.6.4
出队
3.6.5
整体测试
3.6 队列的链式存储
队列采用链式存储称为链式队列，链式队列是单链表的一种，是运算受限制的单链表，具有与单链表相同的存储结构。
3.6.1 链式队列的定义
链式队列作为单链表的一种，其插入操作在队尾进行，删除操作在队头进行。通过指向队列头部的指针与指向队列尾部的指针控制队列的操作，如图所示。
3.6.1 链式队列的定义
由图可知，front指针与rear指针用来完成队列的数据操作，代码定义如下所示。
以上代码中，第一个封装结构体表示链式队列中的数据结点，第二个封装结构体存放指向链式队列头尾结点的指针。
3.6.2 链式队列的创建
在对链式队列中的数据进行操作之前，需要先创建一个空的链式队列。通过代码实现创建一个空的链式队列，示例代码参考教材3.6.2节。
3.6.3 入队
3.6.2节已经完成了创建空链队列的操作，接下来将通过代码展示如何向链式队列中加入数据结点。链式队列不同于顺序队列，不需要设定队列的大小，因此也不需要判断队列是否为满。
入队采用单链表操作中的尾插法，代码如下所示。（变量定义与例3-7一致）。
3.6.4 出队
在出队之前，需要判断队列是否为空，如果为空，没有数据可以移出。代码如下所示。（变量定义与例3-7一致）。
3.6.4 出队
队列非空即可执行出队操作，出队采用单链表操作中的头删法。代码如下所示。（变量定义与例3-7一致）。
3.6.5 整体测试队
将3.6.3节和3.6.4节的功能代码与例3-7结合，测试数据操作是否成功，示例代码参考教材3.6.5节。
例中，主函数主要用于测试子函数是否正确。首先执行入队操作；然后执行出队操作，并通过显示出队数据，判断链式队列是否遵循先进先出的规则。输出结果如下所示。
由输出结果可知，数据入队成功，出队时，最早入队的数据先出队。
本章小结
本章主要介绍了两种特殊的线性表结构——栈与队列，分别讨论了二者在顺序结构与链式结构下数据结点的基本操作。栈与队列的数据操作类似于顺序表和单链表。望读者能在理解操作原理的前提下熟练编程操作，为后续结合算法思想解决实际问题奠定基础。

展开更多......

收起↑