《数据结构》课件-项目三 栈和队列

队列3.2目录CONTENTE模块二线性结构栈和队列3.1栈芜湖职业技术学院说起队列，大家肯定在熟悉不过了。在我们日常生活中，我们做很多事情都需要排队。比如：学生在食堂窗口打饭要排队，去超市购物，在收银台付款时要排队，甚至去医院挂号也需要排队。总之，队列，在我们日常中，非常常见。毕竟排队，是遵守秩序的标志，而遵守秩序是文明的标志。我们都想要生活在一个文明的国度，如果，一个国家没有秩序，那情况真的不堪设想。（加图片）芜湖职业技术学院同样的在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上。.相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。洗盘子，简单的一项劳动，而劳动是日常生活的必需品，热爱劳动也是中华民族的优秀传统。劳动最光荣、劳动最崇高、劳动最伟大、劳动最美丽。其中，习近平总书记关于“劳动最美丽”的重要论述，是习近平新时代中国特色社会主义思想的重要组成部分，是马克思主义劳动美学理论中国化的最新成果。（加图片）芜湖职业技术学院本章我们要解决的问题：栈的顺序存储结构和基本操作的实现。栈的链式存储结构和基本操作的实现。队列的顺序存储结构(循环队列)和基本操作的实现。队列的链式存储结构和基本操作的实现。栈和队列的各自特点和适用场合。掌握栈和队列的定义、特点、典型算法及在实际中的应用。栈3.1数据结构模块二线性结构栈和队列3.1栈例

栈的例子现实生活中的栈3.1栈计算机中的栈3.1栈栈的定义栈是限制只能在表的一端进行插入和删除操作的线性表，在表中允许插入和删除的这一端称为栈顶(Top)，另一端称栈底(Bottom)。a1a2……an进栈出栈栈底栈顶3.1栈栈的定义当栈中没有元素时称为空栈。处于栈顶位置的数据元素称为栈顶元素。栈的插入操作被称为进栈或入栈，删除操作称为出栈或退栈。栈的特点：先进后出（LIFO）a1a2……an进栈出栈栈底栈顶3.1栈栈的定义a1a2……an进栈出栈栈底栈顶第一种：1，2，3进，再3，2，1出。出栈次序：321第二种：出栈次序：123第三种：出栈次序：213第四种：出栈次序：132第五种：出栈次序：231

栈对线性表的插入和删除的位置做了限制，但是值得注意的是，没有对元素插入和删除的时间进行限制。所以，并不是说元素依a1,a2,…,an的顺序进栈过程中不允许元素出栈。例如，1,2,3依次进栈，会有哪些出栈次序?

有没有312的出栈次序呢?3.1栈栈的定义动画演示：3.1栈栈的基本操作（1）InitStack(&S)名称：初始化。作用：构造一个空栈S。前置条件：无。（2）DestroyStack(&S)名称：销毁。作用：栈S被销毁。前置条件：栈S已存在。（3）ClearStack(&S)名称：清空。作用：将S清为空栈。前置条件：栈S已存在。3.1栈栈的基本操作（4）StackEmpty(S)名称：判空。作用：若栈S为空栈，则返回TRUE，否则FALSE。前置条件：栈S已存在。（5）StackLength(S)名称：栈长度。作用：返回S的元素个数，即栈的长度。前置条件：栈S已存在。（6）GetTop(S)名称：获取栈顶。操作结果：返回S的栈顶元素。前置条件：栈S已存在且非空。3.1栈栈的基本操作（7）Push(&S,x)名称：压入（插入）。作用：插入元素x为新的栈顶元素。前置条件：栈S已存在。（8）Pop(&S)名称：弹出（删除）。作用：删除S的栈顶元素，并返回栈顶数据元素。前置条件：栈S已存在且非空。（9）StackTraverse(S)名称：遍历。作用：从栈底到栈顶依次对栈S的每一个数据元素进行访问。前置条件：栈S已存在且非空。和线性表类似，栈也有两种存储表示方法。1．顺序栈栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的;设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。利用顺序存储方式表示的栈称为顺序栈。栈中的数据元素用一个预设的足够大的一维数组来实现datatypedata[StackSize];3.1栈栈的存储结构1．顺序栈#defineStackSize最大元素数

typedefstruct{DataTypedata[StackSize];inttop;//记录栈顶位置}SeqStack；定义一个指向顺序栈的指针：

SeqStack*S;顺序栈的类型描述如下：3.1栈栈的存储结构1．顺序栈

通常0下标端设为栈底，这样空栈时栈顶指针S->top = -1；入栈时，栈顶指针加1，即S->top++；出栈时，栈顶指针减1，即S->top--。3.1栈栈的存储结构1．顺序栈3.1栈栈的存储结构顺序栈的基本操作：

3210top-1栈空//⑴置栈空（初始化）voidInitStack(SeqStack*S){S->top=-1;}//⑵判栈空intStackEmpty(SeqStack*S){returnS->top==-1;}3.1栈栈的存储结构1．顺序栈顺序栈的基本操作：

3D2C1B0Atop-1栈满//⑶判栈满intStackFull(SeqStack*S){returnS->top==StackSize-1;}注：StackSize为栈的空间大小是不是很简单呀3.1栈栈的存储结构1．顺序栈顺序栈的基本操作：

3210top-1进栈操作AB//⑷进栈voidPush(SeqStack*S,DataTypex){if(StackFull(S)) printf("Stackoverflow\n");//上溢

else { S->top++;//栈顶位置变量加1 S->data[S->top]=x;//将x入栈

}}3.1栈栈的存储结构1．顺序栈顺序栈的基本操作：

3210top-1出栈操作ABx=//⑸出栈DataTypePop(SeqStack*S){ DataTypex; if(StackEmpty(S)) { printf("Stackunderflow\n");//下溢

x='\0'; }else { x=S->data[S->top];//获取栈顶元素

S->top--;//栈顶位置减1 } returnx;//栈顶元素返回}3.1栈栈的存储结构顺序栈的基本操作：

321B0top-1取栈顶元素ABx=//(6)取栈顶元素DataTypeStackTop（SeqStack*S）{if(StackEmpty(S)) printf("Stackisempty");returnS->data[S->top];}注：只是读取栈顶元素，top位置不变3.1栈栈的存储结构1．顺序栈顺序栈的基本操作：⑴

对于顺序栈，入栈时，首先判断是否栈满。栈满时，不能入栈。⑵出栈和读栈顶元素操作，先判断栈是否为空，为空不能操作。栈满的条件为：s->top==StackSize-1说明：3.1栈栈的存储结构1．顺序栈3.1栈栈的存储结构2．双向栈一个程序中常常要用到多个栈，并且必须给每个栈预先分配一个足够大的存储空间，势必会造成系统空间浪费。多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补，这就是栈的共享邻接空间。双向栈在一维数组中的实现。栈的共享中最常见的是两栈的共享。假设两个栈共享一维数组stack[MAXNUM]，则可以利用栈的“栈底位置不变，栈顶位置动态变化”的特性，两个栈均为空时，两个栈顶分别为-1和MAXNUM，元素进栈时，两个栈顶都往中间方向延伸因此，只要整个数组stack[MAXNUM]未被占满，无论哪个栈的入栈都不会发生上溢，3.1栈栈的存储结构2．双向栈C语言定义的这种两栈共享邻接空间的结构如下：typedefstruct{Elemtypestack[MAXNUM];intlefttop;//左栈栈顶位置intrighttop;//右栈栈顶位置}dupsqstack;为了识别左右栈，必须另外设定标志：charstatus;status=’L’;//左栈status=’R’//右栈在进行栈操作时，需要指定栈号：status=’L’为左栈，status=’R’为右栈；判断栈满的条件为：s->lefttop+1==s->righttop;3.1栈栈的存储结构2．双向栈（1）初始化操作intInitDupStack(dupsqstack**s){if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)returnFALSE;(*s)->lefttop=-1;(*s)->righttop=MAXNUM;returnTRUE;}3.1栈栈的存储结构2．双向栈（2）进栈操作intPushDupStack(dupsqstack*s,charstatus,Elemtypex){if(s->lefttop+1==s->righttop)returnFALSE;//栈满if(status==’L’)s->stack[++s->righttop]=x;//左栈进栈elseif(status==’R’)s->stack[--s->righttop]=x;//右栈进栈elsereturnFALSE;//参数错误returnTRUE;}}3.1栈栈的存储结构2．双向栈（3）出栈操作ElemtypePopDupStack(dupsqstack*s,charstatus){if(status==’L’){if(s->lefftop<0)returnNULL;//左栈为空elsereturn(s->stack[s->lefttop--]);//左栈出栈}elseif(status==’R’){if(s->righttop>MAXNUM-1)returnNULL;//右栈为空elsereturn(s->stack[s->righttop++]);//右栈出栈}elsereturnNULL;//参数错误}3.1栈栈的存储结构2．双向栈动画演示如下：

(1)链栈的定义：栈的链式存储结构(2)链栈类型定义如下：

typedefstructstacknode{ DataTypedata; structstacknode*next;}StackNode;(3)链栈的示意图如下：

注：链栈采用的是链式存储结构，不存在栈满现象。3．链栈3.1栈栈的存储结构

3.1.3栈的存储结构(4)链栈的操作//初始化为栈空voidInitStack(StackNode**top){*top=NULL;}//判断栈是否为空intStackEmpty(StackNode*top){returntop==NULL;}

3.1.3栈的存储结构(4)链栈的操作(进栈)

3.1.3栈的存储结构(4)链栈的操作(进栈)//进栈操作voidPush(StackNode**top,DataTypex){ //将元素x插入链栈头部

StackNode*p=(StackNode*)malloc(sizeof(StackNode)); p->data=x; p->next=*top; *top=p;}

3.1.3栈的存储结构(4)链栈的操作(出栈)topabcdep∧ppppNULLDataTypePop(StackNode**top)//出栈操作{DataTypex;StackNode*p=*top;//保存栈顶指针

if(StackEmpty(*top)){ printf("Stackunderflow.");//下溢

x='\0';}else{ x=(*top)->data;//保存栈顶结点数据 *top=p->next;//将栈顶结点从链上摘下

free(p);}returnx;}

4．多个链栈3.1栈栈的存储结构在程序中同时使用两个以上的栈时，若用多个单链栈时，操作极为方便。多个链栈的操作可以将多个单链栈的栈顶指针放在一个一维数组slStacktype*top[M];中，让top[0]，top[1]，…，top[M-1]指向M个不同的链栈，操作时只需确定栈号i，然后以top[i]为栈顶指针进行栈操作即可实现各种操作。

4．多个链栈3.1栈栈的存储结构进栈intPushDupLs(slStacktype*top[],intI,Elemtypex){slStacktype*p;if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL)returnFALSE;//申请一个结点空间p->data=x;p->next=top[i];top[i]=p;returnTRUE;}

4．多个链栈3.1栈栈的存储结构（2）出栈ElemtypePopDupLs(slStacktype*top[],inti){slStacktype*p;Elemtypex;if(*top==NULL)returnNULL;//空栈

p=*top;*top=(*top)->next;x=p->data;free(p);returnx;}在上面的两个算法中，当指定栈号i（0≤i≤M-1）时，则只对第i个链栈操作，不会影响其他链队列3.2数据结构模块二线性结构栈和队列3.2队列例

队列的例子3.2队列例

队列的例子队列的定义3.2队列例

计算机中的队列队列的定义无论是多进程共享cpu的时间，还是用户共享，打印机都需要借助队列来实现优化分配。操作系统中的作业排队就是队列数据结构的典型应用，计算机系统中，同时有几个作业运行如果运行结果都需要通过通道输出，那就按请求输出的先后次序排队。3.2队列队列的定义队列（queue）是一种先进先出（FIFO）的线性表，它限制表的插入在一端进行，删除在另一端进行。允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。3.2队列队列的定义

3.2队列队列的定义入队、出队动画演示：3.2队列队列的基本操作（1）InitQueue(&Q)名称：初始化。操作结果：构造一个空队列Q。前置条件：无。（2）DestroyQueue(&Q)名称：销毁。操作结果：队列Q被销毁，不在存在。前置条件：队列Q已经存在。（3）ClearQueue(&Q)名称：清空。操作结果：将Q清为空队列。前置条件：队列Q已经存在。·3.2队列队列的基本操作（4）QueueEmpty(Q)名称：判空。操作结果：若Q为空列队，则返回TRUN，否则FALSE。前置条件：队列Q已经存在。（5）QueueLength(Q)名称：长度。操作结果：返回Q的元素个数，即队列的长度。前置条件：队列Q已经存在。（6）GetHead(&Q,e)名称：获取队头。操作结果：用e返回Q的队头元素。前置条件：Q为非空队列。3.2队列队列的基本操作（7）EnQueue(&Q,e)名称：插入队尾（入队）。操作结果：插入元素e为Q的新的队尾元素。前置条件：队列Q已存在。（8）DeQueue(&Q,&e)名称：删除队头（出队）。操作结果：删除Q的队头元素，并用e返回其值。前置条件：Q为非空队列。（9）QueueTraverse(Q)名称：遍历。操作结果：从队头到队尾，依次对Q的每一个数据元素进行访问。前置条件：Q已存在且非空。队列的存储结构3.2.3队列的存储结构1顺序队列利用顺序存储方式表示的队列称为顺序队列。顺序队列利用一组地址连续的存储单元依次存放队列中的数据元素。通常使用一维数组来作为队列的顺序存储空间，另外再设立两个指示器：一个为指向队头元素位置的指针（front），另一个为指向队尾元素位置的指针（rear）。初始化队列时，令front=rear=-1，当插入新的数据元素时，尾指示器rear加1，而当队头元素出队列时，队头指示器front加1。3.2.3队列的存储结构1顺序队列用C语言定义的顺序存储结构的队列如下：#defineMAXSIZE1024 /*队列的最大容量*/typedefstruct{

DataTypedata[MAXSIZE]; /*队列的存储空间*/ intrear,front; /*队头队尾指针*/}SeQueue;

顺序队列类型定义如下：3.2.3队列的存储结构1顺序队列定义一个指向队列的指针变量：SeQueue*sq;队列的数据区为sq->data[0]～sq->data[MAXSIZE - 1]。队头指针：sq->front。队尾指针：sq->rear。设队头指针指向当前队头元素前面一个位置，队尾指针指向队尾元素(这样的设置是为了某些运算的方便，并不是唯一的方法)。置空队则为：sq->front = -1;sq->rear = sq->front;不考虑溢出的情况下，入队操作队尾

指针加1，指向新位置后，元素入队。

sq->rear++;

sq->data[sq->rear] = x;3.2.3队列的存储结构1顺序队列不考虑队空的情况下，出队操作队头指针加1，表明队头元素出队。sq->front++;x = sq->data[sq->front];队中元素的个数：m = (sq->rear) - (q->front)。3.2.3队列的存储结构1顺序队列请大家看图思考GBCFEfrontrear0123456MAXSIZE-1DAH此时，再有元素入队列就会溢出，可是从图中看出队列并不满，请大家思考这是为什么呢？这种情况就称为“假溢出”3.2.3队列的存储结构1顺序队列解决假溢出的方法之一是将队列的数据区看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”如图所示：q->rear=(q->rear+1)%MAXSIZE;q->data[q->rear]=x;q->front=(q->front+1)%MAXSIZE;x=q->data[q->front];rear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLKfrontfrontfront入队操作为：出队操作为:3.2.3队列的存储结构1顺序队列“队满”和“队空”的条件相同。这显然是必须要解决的一个问题。解决方法：第一种是另设一个标志位以区别队列是空还是满。第二种是少用一个元素空间，少用一个元素空间，此时队满的条件是：(sq->rear+1)%MAXSIZE==sq->front；队空的条件是：sq->rear==sq->front。第三种方法是设置一个计数器用来记录对列中的元素总数，也就是实际的对列长度。下面我们就以第二种方法为例讲解循环队列的操作。3.2.3队列的存储结构1顺序队列#defineMAXSIZE1024 /*队列的最大容量*/typedefstruct{ DataTypedata[MAXSIZE]; /*队列的存储空间*/ intrear,front; /*队头队尾指针*/}CirQueue;循环队列的类型定义及基本运算如下：

voidInitQueue(CirQueue*q){ q->front=-1; q->rear=-1;}循环队列操作⑴置空队3.2.3队列的存储结构1顺序队列循环队列操作

intQueueEmpty(CirQueue*q){ if(q->front==q->rear) return1;else return0;}

intQueueFull(CirQueue*q){ if(q->front==(q->rear+1)%MAXSIZE) return1; else return0;}⑵判队空⑶判队满3.2.3队列的存储结构1顺序队列循环队列操作voidEnQueue(CirQueue*q,DataTypex){ if(QueueFull(q)) { printf("overflow!\n");//队满上溢

return; } else { q->data[q->rear]=x;q->rear=(q->rear+1)%MAXSIZE; }}⑷入队3.2.3队列的存储结构1顺序队列循环队列操作DataTypeDeQueue(CirQueue*q){ DataTypex;if(QueueEmpty(q)) { printf("underflow!\n");//队空下溢

x='\0'; } else { x=q->data[q->front];q->front=(q->front+1)%MAXSIZE; }returnx;}(5)出队3.2.3队列的存储结构1顺序队列3.2.3队列的存储结构2链队列判空条件：q->front->next==NULL;

或q->rear=q->front;为了操作的方便，给链队列添加一个头结点，并设定头指针指向头结点。frontrear^fronta1a2ai…an…rear^3.2.3队列的存储结构2链队列链队的描述如下：typedefstructnode{ datatypedata; structnode*next;}QNode;typedefstruct{ QNnode*front,*rear;}LQueue;LQueue*q;定义一个指向链队的指针：链队结点的类型将头尾指针封装在一起的链队3.2.3队列的存储结构2链队列按这种思想建立的带头结点的链队如下图所示：frontrear^qa1a2ai…an…^frontrearqvoidInit_LQueue(LQueue*q){ q->front=(QNode*)malloc(sizeof(Qnode)); q->rear=q->front; q->front->next=NULL; }链队的基本运算如下：(1)链队列初始化。申请一个头结点，令队头指针和队尾指针都指向它，并令该结点的next域为NULL。frontrear^q3.2.3队列的存储结构2链队列链队的基本运算如下：(2)入队voidIn_LQueue(LQueue*q,datatypex){ QNode*p; p=(QNode*)malloc(sizeof(QNode)); p->data=x; p->next=NULL; q->rear->next=p; q->rear=p;}a1a2ai…an…^frontrearq3.2.3队列的存储结构2链队列链队的基本运算如下：(3)判队空intEmpty_LQueue(LQueue*q){ if(q->front==q->rear) return0; else return1;}frontrear^q3.2.3队列的存储结构2链队列链队的基本运算如下：(4)出队a1a2ai…an…^frontrearq对头元素x出队3.2.3队列的存储结构2链队列链队的基本运算如下：voidOut_LQueue(LQueue*q,datatype*x){ QNode*p; if(Empty_LQueue(q)) printf(″队空″); else { p=q->front->next; q->front->next=p->next; *x=p->data;/*队头元素放x中*/ free(p); if(q->front->next==NULL) q->rear=q->front;/*只有一个元素时，出队后队空，此时还要修改队尾指针*/ }}对头元素x出队3.2.3队列的存储结构2链队列栈和队列的应用3.3数据结构模块二线性结构栈和队列

3.1.3栈的应用利用栈的结构实现十进制转换其他进制的算法数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下：

NN/8（整除）N%8（求余）

34674333低

4335415466606高所以：（3467）10=（6613）8

3.1.3栈的应用算法思想：数制转换问题（1）初始化栈，初始化N为要转换的数，r为进制数（2）判断N的值为0转（4），否则N%r压入栈s中（3）用N/r代替N转（2）（4）出栈，出栈序列即为结果voidmultibase(intn,intb){ inti;

SeqStacks;

InitStack(&s); while(n!=0) { Push(&s,n%b);//进栈

n=n/b; }

printf("转换后的结果："); while(!StackEmpty(&s))

printf("%d",Pop(&s));//输出出栈元素

printf("\n");}

3.1.3

队列的应用求迷宫的最短路径。问题：有一个迷宫,求从入口到出口的最短路径,其中0表示通路,1表示受阻,规定向下是X轴,向右是Y轴输入:第一个数迷宫x轴的长度,第二个数迷宫y轴的长度,紧接着入口点的坐标和出口的坐标,之后是一个迷宫输出:迷宫所走的路径的坐标

样例:INPUT:681168011101111010101001001111011100111001100001100110OUT:(1,1)-->(2,2)-->(3,3)-->(3,4)-->(4,5)-->(4,6)-->(5,7)-->(6,8)

3.1.3

队列的应用算法思想：求迷宫的最短路径。

从迷宫入口（1,1）出发，向四周搜索，记下所有一步能达到的坐标点；然后依次再从这些点出发，再记下所有已不能达到的坐标点；依次类推，直到迷宫的出口点（n，n）为止，然后从出口点沿搜索路径回溯到入口。这样就找到了一条迷宫的最短路径。

由于先到达的点先向下搜索，故引入一个