数据结构ppt-栈和队列

2023/2/11

第3章栈和队列本章主题：栈和队列的应用

教学目的：掌握栈和队列的应用方法,理解栈的重要作用

教学重点：利用栈实现行编辑,利用栈实现表达式求值

教学难点：利用栈实现表达式求值

栈，也叫堆栈，是最常用也是最重要的数据结构之一。比如编译器中的语法识别、数学表达式的处理、程序运行中的函数及过程的调用等，都要用到栈的有关特性。它们是栈应用于实际问题的典型。3.1栈

【课前思考】

1.什么是线性结构？简单地说，线性结构是一个数据元素的序列。

2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的,那么使用时候的次序应是什么样的？必然是依从上往下的次序，即n,…,2,1。它们遵循的是"后进先出"的规律，这正是本章要讨论的"栈"的结构特点。

3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？

是"排队"。在计算机程序中，模拟排队的数据结构是"队列"。2023/2/122023/2/131．栈的定义

栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。

特点：后进先出栈又称为“后进先出”的线性表，简称LIFO表。3.1.1栈的定义和运算

ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)2023/2/142．栈的基本运算初始化栈InitStack(S)设置一个空栈S。压栈Push(S,x)将元素x插入栈S中，使x成为栈S的栈顶元素。出栈Pop(S,x)当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素取栈顶元素GetTop(S,x)

若栈S不空，则由x返回栈顶元素。判栈空Empty(S)

若栈S为空栈，结果为1，否则结果为0。

2023/2/15例1：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB2023/2/16例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？

43512不可能实现，主要是其中的12顺序不能实现；

12345的输出可以实现，只需压入一个立即弹出一个即可。

435612中到了12顺序不能实现；

135426可以实现。例3：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：答：2023/2/17例4：计算机系2001年考研题（程序设计基础）设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：2023/2/18

3.1.2栈的顺序存储结构及其基本运算的实现

栈有两种存储表示方法:顺序存储和链式存储1.栈的顺序存储结构

栈的顺序存储结构简称为顺序栈。通常由一个一维数组和一个记录栈顶元素位置的变量组成。2023/2/19ElemType为栈中元素的数据类型，可以根据需要而指定为某种具体的类型。

data域:为一个一维数组，用于存储栈中元素。

top域:栈顶指针。取值范围为0～MaxSize-1。top=-1表示栈空，top=MaxSize-1表示栈满。#defineMaxSize<存储数据元素的最大个数>typedefstruct{ElemTypedata[MaxSize];inttop;}STACK;顺序栈的C++语言描述如下：2023/2/110。

顺序栈的几种状态（最大长度MaxSize为4）（a）当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值top=-1。（b）表示在（a）基础上执行Push(S,‘A’)后得到这种状态。（c）又有三个元素B、C、D先后入栈，此时栈顶元素的下标值top=3。栈已满。（d）表示在（c）状态下，执行一次Pop(S，x)运算得到。（e）表示在（d）状态下，执行三次Pop(S，x)运算得到。此时栈顶下标值top=-l，又变成栈空状态

2023/2/1112．基本运算在顺序存储结构的实现初始化栈InitStack(S)

voidInitStack(STACK*S){S->top=-1;}

压栈Push(S,x)

intPush(STACK*S,ElemTypex){if(S->top==MaxSize-1){Cout<<“Stackisfull!”;return0;}S->top++;S->data[S->top]=x;return1;}2023/2/112出栈Pop(S,x)intPop(STACK*S,ElemType*x){if(Empty(S)){cout<<“Stackisfree!”;return0;}*x=S->data[S->top];S->top--;return1;}2023/2/113

取栈顶元素GetTop(S,x)

intGetTop(STACK*S,ElemType*x){

if(Empty(S)){cout<<“Stackisfree!”;retrn0;}*x=S->data[S->top];return}

判栈空Empty(S)

intEmpty(STACK*S){return(S->top==-1?1:0);}顺序栈的操作演示2023/2/1143．栈的共享存储单元

两个栈共享大小为m的内存空间时，分配方法的示意图如下两个栈的共享存储单元可用C++语言描述如下：#defineMaxSize<共享存储单元的最大长度>typedefstruct{ElemTypedata[MaxSize];inttop[2];}STACK;两个共享存储单元顺序栈的操作演示2023/2/115（1）两个栈共享存储单元的压栈算法intPush(STACK*S,ElemTypex,intk){if(S->top[0]+1==S->top[1]){cout<<“stackisfull!”;return0;}if(k==0){S->top[0]++;S->data[S->top[0]]=x;}else{S->top[1]--;S->data[S->top[1]]=x;}return1;}2023/2/116（2）两个栈共享存储单元的出栈算法intPop(STACK*S,intk,ElemType*x){if((k==0)&&(S->top[0]==-1)){cout<<“stackisfree!”;return0;}if((k==1)&&(S->top[1]==MaxSize)){cout<<“nstackisfree!”;return0;}if(k==0){*x=S->data[S->top[0]];S->top[0]--;}else{*x=S->data[S->top[1]];S->top[1]++;}return1;}2023/2/1173.1.3栈的链式存储结构及其基本运算的实现1.栈的链式存储结构

栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈链栈的C++语言描述如下：typedefstructsnode{//定义链栈结点类型

ElemTypedata;structsnode*next;}LinkSTACK;LinkSTACK*top;链栈结构示意图2023/2/118链栈的几种状态:2023/2/1192．基本运算在链式存储结构的实现栈初始化

voidInitStack(LinkSTACK**top){*top=(LinkSTACK*)malloc(sizeof(LinkSTACK));(*top)->next=NULL;}2023/2/120压栈运算

intPush(LinkSTACK**top,ElemTypex){LinkSTACK*s;s=(LinkSTACK*)malloc(sizeof(LinkSTACK));s->data=x;s->next=(*top)->next;(*top)->next=s;return1;}判断栈空

intEmpty(LinkSTACK**top){return((*top)->next==NULL?1:0);}2023/2/121出栈运算

intPop(LinkSTACK**top,ElemType*x)

{LinkSTACK*s;if(Empty(top)){cout<<“stackisfree!”;return0;}s=(*top)->next;*x=s->data;(*top)->next=s->next;free(s);return1;}2023/2/122取栈顶元素

intGetTop(LinkSTACK**top,ElemType*x){if(Empty(top)){cout<<“stackisfree!”;return0;}*x=(*top)->next->data;return1;}2023/2/123递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多问题的算法设计。在计算机内部，通过栈来实现递归算法。所以递归是栈的一个实际应用。

3.3栈与递归2023/2/124采用递归算法求解正整数n的阶乘n!数学定义求n的阶乘的递归函数算法如下:longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}2023/2/125进行fact(4)调用的系统栈的变化情况

2023/2/126函数fact(4)的递归调用过程的执行流程2023/2/127

3.4.1队列的定义和运算

1．队列的定义

队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。

特点：队列中数据元素的入队和出队过程是按照“先进先出”的原则进行的。因此，队列又称为“先进先出”的线性表，简称FIFO表。3.4队列2023/2/128

2．队列的基本运算队列初始化InitQueue(SQ)

设置一个空队列SQ。入队列EnQueue(SQ，x)

将x插入到队列SQ的队尾。出队OutQueue(SQ，x)

将队头元素赋给x，并删除队头元素。取队头元素GetHead(SQ，x)

由x返回队头结点的值。

判队列空Empty(SQ)队列SQ是否为空。若为空返回1，否则返回0。2023/2/129

3.4.2队列的顺序存储结构及其基本运算的实现队列有两种存储表示方法:顺序存储和链式存储1．队列的顺序存储结构队列的顺序存储结构简称顺序队。顺序队是用一维数组依次存放队列中的元素和分别指示队列的首端和队列的尾端的两个变量组成。这两个变量分别称为“队头指针”和“队尾指针”。顺序队列的数据类型定义如下#defineMaxSize<队列的最大容量>typedefstruct{ElemTypedata[MaxSize];intfront,rear;}SQUEUE;2023/2/130顺序队列（MaxSize=5）的几种状态

（a）表示空队列，

rear=front=0。（b）元素A入队后，

rear=1，front=0。（c）B，C依次入队后，

rear=3，front=0。（d）A，B，C依此出队后,rear=front=3。（e）D入队后,rear=4,front=3。（f）D出队后，rear=front=4。顺序队列的操作演示2023/2/131如图所示是具有五个存储单元的循环队列（a）表示空队列，

rear=front=0。（b）元素A入队后，

rear=1，front=0。（c）B，C，D依次入队后，

rear=4，front=0。（d）A出队后,front=1,rear=4。（e）B，C，D出队后,rear=front=4。

循环队列的操作演示2023/2/1322．基本运算顺序队列的实现队列初始化

voidInitQueue(SQUEUE*SQ){SQ->rear=SQ->front=0;}

入队列intEnQueue(SQUEUE*SQ,ElemTypex){if((SQ->rear+1)%MaxSize==SQ->front){cout<<“Queueisfull!”;return0;}SQ->rear=(SQ->rear+1)%MaxSize;SQ->data[SQ->rear]=x;return1;}2023/2/133出队intOutQueue(SQUEUE*SQ,ElemType*x){if(Empty(SQ)){cout<<“Queueisfree”;return0;}SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];return1;}判队列空intEmpty(SQUEUE*SQ){return(SQ->rear==SQ->front)?1:0;}

2023/2/134队空：Q.front=Q.rear队满：Q.rear=maxsize（假溢出）求队长：Q.rear-Q.front

入队：新元素按

rear

指示位置加入，再将队尾指针加一，即rear=rear+1

出队：将front指示的元素取出，再将队头指针加一，即front=front+1，非循环队列2023/2/135队空：Q.front=Q.rear队满：Q.front=(Q.rear+1)%maxSize入队:Q.rear=(Q.rear+1)%maxSize出队:Q.front=(front+1)%maxSize;求队长:(Q.rear-Q.front+maxSize)%maxSize循环队列2023/2/1363.4.3队列的链式存储结构及其基本运算的实现

1.队列的链式存储结构

队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。链队结构示意图2023/2/137链队的数据类型定义如下：typedefstructqnode{//链队结点的类型

ElemTypedata;structqnode*next;}QTYPE;typedefstructqptr{//链队指针类型

QTYPE*front,*rear;}SQUEUE;SQUEUELQ;

2023/2/138链队运算指针变化情况2023/2/1392．基本运算链队的实现队列初始化

voidInitQueue(SQUEUE*LQ){QTYPE*p;p=(QTYPE*)malloc(sizeof(QTYPE));p->next=NULL;LQ->front=LQ->rear=p;}2023/2/140入队列

intEnQueue(SQUEUE*LQ,ElemTypex){QTYPE*s;s=(QTYPE*)malloc(sizeof(QTYPE));s->data=x;s->next=LQ->rear->next;LQ->rear->next=s;LQ->rear=s;return1;}判队空intEmpty(SQUEUE*LQ){return(LQ->front==LQ->rear?1:0);}2023/2/141出队列intOutQueue(SQUEUE*LQ,ElemType*x){QTYPE*p;if(Empty(LQ)){cout<<“Queueisfree”;return0;}p=LQ->front->next;*x=p->data;LQ->front->next=p->next;if(LQ->front->next==NULL)LQ->rear=LQ->front;free(p);return1;}2023/2/142取队头元素

intGetHead(SQUEUE*LQ,ElemType*x){if(Empty(LQ)){cout<<“Queueisfree”;return0;}*x=LQ->front->next->data;return1;}2023/2/143典型题解1、利用栈的基本操作，写一个返回栈S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?2023/2/144intStackSize(SeqStackS){ //计算栈中结点个数

intn=0; if(!EmptyStack(&S)) { Pop(&S); n++; } returnn;}2023/2/145我们要计算栈中元素个数就要弹出元素才能"数"得出来，那如果用指针做参数的话，就会把原来的栈中元素"弹"光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。2023/2/1462、回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)2023/2/147intIsHuiwen(char*S){ SeqStackT; inti,l; chart; InitStack(&T); l=strlen(S); //求向量长度

for(i=0;i<l/2;i++) //将一半字符入栈

Push(&T,S[i]); while(!EmptyStack(&T)) { //每弹出一个字符与相应字符比较

t=Pop(&T); if(t!=S[l-i]){return0;}//不等则返回0 i--; } return-1; //比较完毕均相等则返回-1}2023/2/148//以下程序用于验证上面的算法//以下是栈定义(存为stack.h)//出错控制函数#include<stdlib.h>#include<stdio.h>voidError(char*message){ fprintf(stderr,"Error:%s\n",message); exit(1);}//定义栈类型#defineStackSize100typedefcharDatatype;typedefstruct{ Datatypedata[StackSize]; intTop;}SeqStack;2023/2/149voidInitStack(SeqStack*S){ //初始化(置空栈) S->Top=-1;}intEmptyStack(SeqStack*S){ //判栈空

returnS->Top==-1; }intFullStack(SeqStack*S){ //判栈满returnS->Top==StackSize-1;}voidPush(SeqStack*S,Datatypex){ //进栈

if(FullStack(S)) Error("Stackoverflow"); S->data[++S->Top]=x;}DatatypePop(SeqStack*S){ //出栈(退栈) if(EmptyStack(S)) Error("Stackunderflow"); returnS->data[S->Top--];}2023/2/150//以下是主程序#include<string.h>#include<malloc.h>#include"stack.h>#include"ishuiwen.h"voidmain(){ charStr[100]=""; printf("输入一个字符串:\n"); scanf("%s",Str); if(IsHuiwen(Str)) printf("\n这个字符串是回文。"); elseprintf("\n这个字符串不是回文。");}2023/2/1513、用第二种方法，即少用一上元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。2023/2/152intEmptyQueue(CirQueue*Q){ //判队空

returnQ->front==Q->rear;}intFullQueue(CirQueue*Q){ //判队满//如果尾指针加1后等于头指针，则认为满

return(Q->rear+1)%QueueSize==Q->front;}2023/2/153DatatypeDeQueue(CirQueue*Q){ //出队

if(EmptyQueue(Q)) Error("队已空，无元素可以出队"); Datatypetemp; temp=Q->Data[Q->front];//保存元素值

Q->front=(Q->front+1)%QueueSize;//循环意义上的加1 returntemp; //返回元素值}2023/2/154voidEnQueue(CirQueue*Q,Datatypex){ //入队

if(FullQueue(Q)) Error("队已满，不可以入队"); Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize;//rear指向下一个空元素位置}2023/2/155DatatypeFrontQueue(CirQueue*Q){ //取队头元素

if(EmptyQueue(Q)) Error("队空，无元素可取"); returnQ->Data[Q->front];}2023/2/156//为了验证上述算法是否正确，设计了以下程序//循环队列的定义存入StructQ.h文件中#defineQueueSize10//为便与验证，这里假设为10个元素的空间typedefcharDatatype;//设元素的类型为char型typedefstruct{ intfront; intrear; DatatypeData[QueueSize];}CirQueue;2023/2/157//以下是主程序,用来验证算法#include<stdio.h>#include<string.h>#include"StrctQ.h" //包含队列结构#include"Queue2.h"//包含算法头文件2023/2/158//------------------------主函数-----voidmain() { inti; CirQueueQ;//定义一个循环队列

InitQueue(&Q);//初始化队列

printf("pleaseentercharacters:\n"); for(i=0;i<QueueSize-1;i++) EnQueue(&Q,getchar()); printf("\n"); if(!EmptyQueue(&Q)) //先输出一个头元素

printf("frontDatais%c",FrontQueue(&Q