06.第06节课第3章栈和队列

罗泽兵 · 发表于 2024-4-15 09:16:15

当在一个函数的运行期间，调用另一个函数的时候呢，在运行该被调函数之前，那么需要完成三项任务。将所有的时差。返回地址等信息呢，传递给被调用函数进行保存，为被调用函数的局部变量分配存储器，将控制转移到。被调用函数的入口。从被调用函数呢，返回调用函数之前应该完成三项任务，保存被调用函数的计算结果，释放被调函数的数据区，依照被调函数的返回地址，

将控制转移到调用函数。那么多个嵌套调用的规则呢？是后调用先返回那么大家呢？需要注意这样一个部分。多个函数调用的规则呢，是后调用先返回。此时呢，内存管理实现再次管理，比如说这样一个。在的这样一个部分后，调用的先返回啊，比如说数据函数b，然后呢，函数先调用a main，然后呢？

函数a，然后函数b那么这个时候呢，先调后调用的呢，就先返回。那么就是我们的。函数嵌套调用的方式递归函数执行的过程呢？可以视为同一函数进行嵌套调用，在执行递归函数的过程中也需要一个递归工作站。它的作用呢，是将递归调用的实际参数返回地址呢，传递给下一层执行的递归函数。那么，并且呢，保存本层的参数和局部变量，以便从下一层返回时呢，

重新使用它们。这是我们。递归函数的这样一个部分，接下来我们看一下队列。队列是什么呢？队列它也是一种。数据结构。并且呢，它是。线性表也就说队列呢，简称对它也是一种线性表，但是呢，它是。操作受限的线性表只允许了在表的一端进行插入，而在表的另一端。

进行删除，向队列中插入元素呢，称为入队或者进队删除元素呢，称为出队或离队。那么这个呢，和日常生活当中的排队是一样的，比如说在现实生活中呢，有很多情况，比如说在食堂打饭。在火车票，火车站买票，在超市付钱，那么这个时候食堂打饭呢，我们排的这个队伍呢，它也是一个队列。

我们排在最前面的呢，就从这个队列当中出出这个队列，我们排在最后面的呢就。最后要新加入队列的人呢？就从队伍的最后面呢？加入这个队列，那么火车站买票呢？也是一样，也是一个队伍，也是一个队列，那么这个时候呢？我们出队列呢，是从最前面呢出队列，然后进队列呢，是从最后面进队列，

那么超市目前也是一样，从最前面进队列，从最后面出队列。那么，这与我们日常生活中的排队是一致的，最早排队的呢？也是最早离队的，它的操作的特性呢？是先进。先出。那么所以呢，我们大家要记住我们队列的特点，队列的特点呢，就是先进先出，那么它的队列的特点呢？

是先进先出。先进队列就先出队列，它是一种运算受限的线性表，所以说我们这里呢，都要记住债是线性表。队列也是线性表，包括我们之后要讲的串和度数组呢，它也是一种线性表，那么队列呢，它也是一种线性表。我们允许插入的一端称为对头，允许删除的一端称为对头，允许插入的一端呢称为对尾。那么，线性表的特点呢？

就是线性代表的一端插入另一端删除，它是一种先进先出的first in first out这这fifo的这样一种结构。比如说我们对立了这样一个图，我们呢a1是对头。a an这个部分呢，是对尾我们出对了，就从我们a1这样一个部分出对，然后我们入队了，就从我们an这样一个位置出对。表尾呢，称为对尾，表头呢，称为对头，插入元素，称为入对，

删除元素呢，称为出对。我们来看一下队列的抽象，路型的定义AD tq数据，对象呢d=aii属于fn的set I=1到nn大于零。数据关系是r1 rar 1呢，等于ai- 1 AI，然后后面的AI和AI+1，那么ai- 1 AI呢，这些都属于di呢，属于一等于一二，一直到n。其中约定了i eae端为队列头an端呢，为队列尾还有这样一些操作initial q构造一个空对列q。destroy q那么队列已经存在，

那么如果它的初始条件呢？是队列已经存在操作结果呢？是队列q被销毁不再存在。那么，还有qa MT那么初始条件呢？是队列q已存在操作结果呢？是若q为空队列，则返回true，否则呢，返回FALSE。q lens如它的初始条件呢，是队列q已存在操作结果呢，是返回q的元素，就队列的长度。还有get k的q，

它的初始条件呢，是一为非q，为非空队列操作结果呢，是返回q的对头元素。还有clear q，它的初始条件呢，是队列q已存在操作结果呢，是将q清为空队列。还有因q那么队列q呢，已存在操作结果呢，是插入元素为一的新的对位元素。DQ那么，操作及初始条件呢？是1q为灰空队列操作结果呢？是删除q的对头元素，

并用一返回其值。q traverse它的初始条件呢？是q已存在且非空操作结果呢？是从对头到对尾，依次对q的每个数据元素呢？调用visit便利访问对中的所有元素。队列呢，是特殊的线性表，那么因此呢，也有两种不同的存储方法，那么第一个呢，是用链表存储的这样一个方式。就是我们的链对列。面对列呢。这个时候呢。

它的链式存储称为链对列，它实际上呢，是一个同时带有对头指针和对尾指针的这样一个链表。它是限制，仅在表头删除和表尾插入的单链表。循环队列呢，是队列的顺序表示和实现。循环队列呢，是队列的顺顺序表示和实现是限制己在表头删除和表尾删表尾插入的顺序表。利用一组地址连续的存储单元依次存放队列中的数据元素，那么我们首先来看一下链对列。队列的链式表示呢？称为链队列，它实际上呢？是一个同时带有对头指针和对尾指针的单链表。

头指针呢？指向对头结点。尾指针呢？指向对尾结点，也就是单链表的最后一个结点。一个链队列由一个头指针和一个尾指针呢，唯一确定，比如说我们呢，这样一个部分呢，我们的头指针。front.指向我们的头节点。为了操作的方便呢，我们给链队列呢，添加一个头结点，

因此呢，空队列的判重条件呢，是头指针和尾指针呢，都指向头结点，那么比如说我们的头指针呢，指向头结点，然后指向我们的对头，那么这样一个部分。面对的结构特节节点结构呢，我们看一下它的这样一个语句，看断一下，看它的结构的语句的结构，部分type defy struct q node element type data struct q no de星号next q no de星号。qp tr这是定义了一个数。数据类型，

一个结构体的这样一个名称q no de和一个指向结构体的指针的这样一个部分qp tr。那么，将对头和对尾指针呢封装在一起，作为链对列的数据类型，那么我们来看一下它的定义type define。q ptr front rear link two将对头对尾指针封装在一起。那么就是link q那么定义一个这样一个树结构体的，这样一个名结构体的，这样一个类型，那么就是我们的link q。那么，比如说有这样一个link q。q front.front.指向我们的头节点，

然后呢？指向我们的这样一个元素。rear呢指向队尾的这样一个节点，那么指向了单链表的最后一个节点，那么这是我们的链队列的这样一个。结构的运用方式。好吧，我们再看一下队列的基本操作，在链队列中的实现。面对队列的初始化操作，比如说state以initial q构造一个空节点的这样一个。空队列q front=q rear。等于。qp trm mlk it塞入我们q no de。那么，

分配一个存储空间，那么将将它的这个地址呢赋给我们的维指针和我们的头指针。那么，并且呢，头指针呢？指向的下一个。指针呢？等于null。这是我们的队列的初始化操作，那么销毁队列的操作呢？是我们的这样一个。status destroy.q while q指向front q指向rear=q指向front指向next。把q指向的front的这样一个next呢，赋给我们的rear。

然后呢？free q指向front，然后把q指向front呢？q指向rear呢？赋给我们的q指向front。那么，这是我们的节点的销毁操作，那么，这是我们销毁的节点，这样一个操作，然后它这样一个部分呢，是将头指针指向的下一个这样一个。节点的这样一个指针呢，赋给我们的rear。然后呢？

释放掉。我们的这样一个节点。然后呢，把我们的伪指针。把然后把我们的q rear付给我们的q front，然后呢，再进行这样一个循环，最后呢？释放掉。我们的。这样一个节点。直到呢，我们的q front呢，等于我们的空空空指针。那么，

结束掉这样一个循环，那么就是销毁队列的操作，那么接下来呢？我们看一下。插入操作在链队列中的实现，where的in q。qp trp.p=qptrmrk的size of q no de ifp=null print。f分配失败x负1p指向data=EP指向next。零到q指向real指向next=pq指向real=p。那么我们看一下插入操作在链队列中的实现，那么我们插入操作呢？那么首先呢，要我们为这样一个节点呢？分配一个存储单元，

那么这里呢qpr market side of q load分配一个节点，这么一个存储单元让p呢指向它。那么ifp=null，如果qp又控制成了，那么。printf分配失败，返x的负一，那么否则呢？p指向data=e，那么把e呢？那么赋给我们p指向data，然后null呢？等于p指向next。next p等于指向next=now把now呢赋给p指向next，然后呢q=real=next=p。

就是把p呢赋给q。指向的rear的next就是把这个p呢，这个指针呢，赋给为指针所指向的下一个节点，下一个节点，这个指针的这样一个部分。然后把p呢赋给q指向real，那么把p呢赋给伪指针，那么这个时候呢？这最后一个节点呢，那么就是我们这样一个p2指向的这个节点的部分，并且呢，尾指针呢，就指向了p的这样一个节点，就是插入插入在链队列中的实现。

接下来我们看一下删除操作在链队列中的实现，那么我们删除操作呢？是在对头进行操作，以离销DQ。qp trp if q指向front=q指向，where那么retire force就是说如果呢？我们的这样一个节点，如果我们这个队列呢？是一个空队列。q指向front=q指向rear，那么我们这个时候呢，返回一个错误，那么否则呢p=q。指向real指向next，那么就把。

就把我们的。q指向的我们头指针的下一个节点的这样一个指针呢赋给p，然后把p的这样一个data呢赋给我们的赋给e。那么q指向front=next呢？等于q指向next。那么就是把p指向的。下一个。节点的这样一个指指针呢赋给。q指向的front。指向的这样一个next的这样一个值。那么if q=q指向rear=p那么q。指向向rear=q指向front，那么又说如果我们的去为指针呢？等于p的话。那么，

把头指针的值呢？那么，赋给维指针，赋给维指针。那么free p。那么，释放掉这样一个p指向的，这样一个值释放掉p指向的，这样一个节点，那么retail true？那么这个时候我们这样一个就进行删除了，这样一个删除了，这样一个部分。那么，这里呢？

if q指向real=p，那么就是说。我们的这样一个伪指针。等于p的话，那么就把头指针的值啊。那么，付给维持针？那么，这样一个部分。那么最后呢？free p释放掉我们的这样一个pp指向的这样一个节点，那么就是我们的删除操作。它的这样一个运用的方式，那么我们这里呢if q。指向real。

等于p。那么，这个唯指针呢？等于我们的p的这样一个指向的这样一个部分。那么这个时候呢，我们就把。show指向front呢。啊，指向real。那么free p。那么，这个伪指针呢？等于等于我们的这样一个p那么这个时候呢？我们就把头指针呢？赋给我们的。

维持着。那么就删除了这个元素呢，就把这样一个指针呢，头指针呢，赋给尾指针。那么，接下来我们看一下。循环队列，它的顺序表示和实现。是限制，仅在表头删除和表尾插入的顺序表，利用一组地址连续的存储单元依次存放队列中的数据元素。那么，因为对尾和对头的对尾是变化的，所以设头尾指针，

那么头尾指针呢？初始化的初初值呢，均为零入队了，为指针加一那么出队了，头指针加一那么头位指针相等时呢？队列为空。在非空队列里头，指针呢，始终指向对头元素。尾指针呢，始终指向对尾的下一位置。在顺序数组中，当为指针呢，已指向了队列的最后一个位置及数组上界的时候呢，若再有元素，

一出入入队，那么就会发生溢出。那么甲溢出了，是队列的存储空间未满，却发生了溢出，那么甲溢出的问题呢？有两种可行的方法，一种是平移元素，把元素呢平移到队列的首部，那么效率低。那么或者呢，向新元素插入到第一个位置上，或者循环队列，那么出队和入队呢，仍按在先进先出的原则进行。

那么我们看一下这样一个部分循环队列呢？我们把它看成是一个循环的这样一个队列，那么我们把它看成是循环的这样一个队列，那么可以呢？进行了一个判断的这样一个部分。而我们循环队列中判空判满的条件是什么呢？我们来看一下循环队列中。由于我们循环队列中呢，我们的头指针呢？可能呢？等于尾指针。那么，我们呢？把存储队列元素的表呢？从逻辑上视为一个环称为循环队列，

当对手指针呢？那么我们看一下循环队列。判空和判满的条件是什么呢？那么显然，对空的条件呢？是front=rear。那么就是说，若如果对元素的速度呢？快于出对元素的速度，那么对为指针和快感上对手指针，那么我们这个时候呢？对满的时候呢，也有q front=q rear，那么为了区分对空还是对满呢？有三种处理方式，

比如说。第一种呢，是另设一个标志了，以区别对空和对满的情况，第二种呢，是使用一个计数器记录队列中元素的个数的队列的长度。第三种呢，是少用一个存储空间，也就是说牺牲。一个存储牺牲一个单元来区，少用一个单元来区分对满和对空，入队时少用一个队列单元，这是一种比较普遍的做法。那么约定呢？以对头指针在对尾指针的下一位置作为对满的标志，

那么这是我们循环队列判空判满的这样一个情况。那么我们看一下队列的顺序，存储结构队列呢，是特殊的线性表，其顺序存储呢，与线性表的顺序存储类似。井号defy x size 100对应最大队列长度type defy struct q element type信号element element。存储队列元素的数组int frontin t rear，那么这是我们的头指针和我们的尾指针。循环队列的基本操作呢，可以有这样一些使用的方式in tin一些issue q构造一个空队列q。q呢指向element。那么等于我们的q。m的type信号。marck it.

mma xq size size of.q element type.那么，这是分配一个存储空间。那么q=q指向element=0，那么分配空间失败，分配空间失败，那么return 0，那么否则呢？q=front=q指向rear rear=0，那么就是一个空队列，最后呢？返回一个一。那么，这是队列的初始值。

循环队列当中，队列初始化的这样一个。的语句。然后接下来呢，我们来看一下这样一个部分。求循环队列的长度in tq once。那么，返回对应元素的个数rq指向rear-q指向front，加上max size来模上max size。就是对尾指针减去对头指针来加上我们的这样一个数组长度来除，用来模上我们数组长度取。那就说我们数组呢，最为指针呢，减去对头指针。那么，

它的这样一个值呢？那么，如果比它比它大的话呢？再加上这个呢？再磨上它，那么结果呢？那么是一样的，这样一个结果的，这样一个情况都是这样一个值。差的这样一个情况，如果呢？我们的qr呢？是小于q front，那么减去这个值了，那么就是这样一个。

那么减去的那么值的部分，那么是那么就比较小的话呢？那么减去这个值了，那么是这样一个值的部分，那么最后呢？来加上一个。max size.那么是。这样一个它的这样一个数量的部分，最后呢，再磨上max size，那么得到了是我们的这样一个数量的元素个数的，这样一个部分。那么，这是我们返求循环队列的长度的这样一个方式。

接下来我们看一下插入操作，在循环队列中的实现in tin q。if q加指向real+1模上m max size=q front，那么当我们的对为？对头，当我们的对头指针呢？在对尾指针的下一位置。那么这个时候呢？那么，当对头指针。在对尾指针。在下一位置的时候呢。这个时候对满那么不能入队。那么另外呢？那么否则呢？

q指向element q指向real=e在对尾的插入元素。q指向rear=q指向m rear+1 max size。那么维指针呢？加一那么考虑到循环队列呢？那么维指针呢？加一还要磨上这个max size，最后retell 1就是插入操作这个实现。接下来我们看一下循环操，循插入操操删除操作，在循环队列中的实现in TD q if q指向front=rear。那么就是头指针指向为指针，那么就说明了对为空那么返回一个错误，那么对列为空那么返回一个错误，那么否则呢，星号e=q指向element front。

从队列头呢出队。q from.q指向front=q front+1。那除以模上max size队列的头指针呢？加一那么考虑到循环情况呢？那么还要模上一个max size？那么，接下来我们看一下。队列的应用，我们的面试基数，排序基数，排序呢，属于低位优先排序法，通过反复进行与收集操作来完成排序。那么，

我们来看一下介绍技术排序的思想，比如说我们一组关键字，那么我们采用技术排序的方法来对其进行排序。比如说我们将上述关键字呢看成若干个关键字复成而成，在这组关键字的值呢都在k小。k属于零到999之间，我们把每一个数位上的十进制数呢看成一个关键字，最关键字是k呢，有三个关键字k0k1k2组成。其中呢k0是百位上的数字k1是十位上的数字k2是个位上的数字，因为十进制的基数是十，因此呢，每个数字上的数字呢，可以是零到九中的任何一个。我们先按关键字k2呢来分配所有参与排序的元素，

将k2=0的元素放在一组k2=1的元素放在一组k2=9的元素放在一组。啊，比如说一套分配前的一套分配前的一个元素呢，那么我们可以呢把它写写在这样一个部分，那么我们按个位数的大小呢，将元素分为十组，那么就是我们分。这样一个排序的，这样一个部分在k2的值呢，到零到九的顺序呢，收集各组元素，形成这样一个序列。那么最后呢？对这样一些元素呢，再按k1来进行分配，

那么按照零到九的顺序呢来收集各组元素，那么再按十位数大小呢，这元素分为十组。那么，对再对这些元素呢？按关键字k0来进行分配，然后按k0的值到零到九的顺序来收集各组元素，那么这是我们按百位的数字呢来进行。分配的这样一个方式。那么最后呢，我们就形成了这样一个序列，就是我们排序的这样一个序列，那么我们各组记录呢？是收集本着该先进入该组的记录呢？首先被收集的原则。

这与队列的先进先出的原则相一致，那么各组序列呢？就以队列来进行描述，那么因此要进入多次的分配与收集，为节约存储空间和运算，方便我们采用链队列呢？来存储各组序列。好同学们，今天呢，我们为大家讲解了我们债和队列这两种数据结构，其中呢，债和队列呢，都是我们的线性表，但是呢。它是操作受限的线性表，

所以这里大家去注意。那么大家呢，要了解我们债和队列它的特点，它的操作，它的构成以及它的应用，那么大家呢，要了解它的这样一个使用方式。那么大家下来的时候呢，那么再看一下我们这样一些内容部分，做到一个了解和掌握好今天的课呢，就讲到这里，谢谢大家。

		自动登录	找回密码
密码			立即注册