数据结构第3章-栈和队列ppt

第3章栈和队列3.1栈3.2队列3.3应用本章学习目标理解栈的定义及其基本运算掌握顺序栈和链栈的各种操作实现理解队列的定义及其基本运算掌握循环队列和链队列的各种操作实现学会利用栈和队列解决一些问题•栈和队列是两种重要的线性结构•栈和队列是操作受限的线性表出进排队买票汉诺塔进出3.1栈3.1.1栈的基本概念栈：限制仅在表的一端进行插入和删除操作的线性表栈的操作特性：按先进后出(FILO)或后进先出(ＬIＦＯ)的原则栈顶(top)：允许插入和删除的一端。约定top始终指向栈顶位置。栈底(bottom):不允许插入和删除的一端。入栈顺序：e0e1e2…en-2en-1出栈顺序：en-1en-2…e2e1e0栈可以对序列实现求逆en-1e0e1en-2…进栈（Push）出栈（Pop）栈顶top栈底bottom栈的基本运算：InitStack(s)初始化操作，初始化为空栈s。IsEmpty(s)判断栈空函数。如果s是空栈，返回“true”，否则返回“false”。IsFull(s)判断栈满函数。主要应用在顺序存储结构中，如果s栈满，返回“true”，否则返回“false”。Push(s，x)压栈操作。将元素x插入到栈s中，并使x成为新的栈顶元素。Pop(s)出栈函数。如果栈s非空，那么返回栈顶元素，并删除该栈顶元素，否则返回空值NULL。GetTop(s)获取栈顶元素。如果栈s非空，那么返回值为栈顶元素，否则返回空值NULL。EmptyStack(s)清空栈操作。将栈s中的所有元素清除掉，使之成为一个空栈。DestroyStack()销毁栈。释放栈占用的存储空间。栈有两种存储结构：顺序存储结构和链式存储结构。3.1.2栈的顺序存储结构顺序栈：顺序存储结构的栈。顺序栈：用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示栈顶指针：指示栈顶位置ABACBA(a)空栈（b）元素A进栈（c）元素B、C进栈（d）出栈一次（e）出栈二次top-1toptoptoptop-14321043210432104321043210顺序栈类型定义：#defineStackSize100/*顺序栈的初始分配空间*/typedefstruct{DataTypedata[StackSize];/*保存栈中元素*/inttop;/*栈指针*/}SeqStack;top为int型，取值范围为0--StackSize-1。top=-l表示栈空；top=StackSize-1表示栈满。栈的长度：栈顶指针top+1顺序栈的基本运算：(1)初始化栈运算功能：创建一个空栈，并将初始化栈顶下标top=-1。intInitStack(SeqStack*&sq){sq=(SeqStack*)malloc(sizeof(SeqStack));if(!sq){printf(“memoryisnotenough!”);return0;}sq-top=-1;return1；}(2)进栈运算功能：栈顶指针加1，将进栈元素放进栈顶指针所指的位置上。intPush(SeqStack*sq,DataTypex){if(sq-top==StackSize-1)/*栈满*/return0;else{sq-top++;sq-data[sq-top]=x;return1;}}(3)出栈运算功能：先将栈顶元素取出，然后将栈顶指针减1。intPop(SeqStack*sq,DataType&x){if(sq-top==-1)/*栈空*/return0;else{x=sq-data[sq-top];sq-top--;return1;}}(4)取栈顶元素运算功能：将栈中top处的元素取出赋给变量x。intGetTop(SeqStack*sq,DataType&x){if(sq-top==-1)/*栈空*/return0;else{x=sq-data[sq-top];return1;}}(5)判断栈空运算算法功能：若栈为空(top==-1)则返回值l，否则返回值0。intStackEmpty(SeqStack*sq){if(sq-top==-1)return1;elsereturn0;}3.1.3栈的链式存储结构链栈：栈的链式存储结构。第一个结点为栈顶结点优点：链式栈无栈满问题，空间可扩充特点：插入与删除仅在栈顶处执行…∧ls栈顶栈底datanext（栈顶指针）链栈的类型定义：typedefstructstnod{DataTypedata;/*存储结点数据*/structstnode*next;/*指针域*/}LinkStack;栈的基本运算算法：(1)初始化栈运算功能：创建一个带头结点的链栈，头结点指针ls；用ls-next=NULL标识栈为空栈。voidInitStack(LinkStack*&ls){ls=(LinkStack*)malloc(sizeof(LinkStack));ls-next=NULL;}(2)判断栈空运算功能：若栈为空则返回值1，否则返回值0。intStackEmpty(LinkStack*ls){if(ls-next==NULL)return1;elsereturn0;}(3)进栈运算voidPush(LinkStack*ls,DataTypex){LinkStack*p;p=(LinkStack*)malloc(Sizeof(LinkStack));p-data=x;p-next=ls-next;ls-next=p;}(4)出栈运算功能:将栈顶结点的data域值赋给x,然后删除该栈顶结点。intPop(LinkStack*ls，DataType&x){LinkStack*p;if(ls-next==NULL)/*栈空，下溢出*/return0;else{p=ls-next;x=p-data;ls-next=p-next;free(p);return1;}}(5)取栈顶元素运算算法功能：将栈顶结点的data域值赋给x。intGetTop(LinkStack*ls,DataType&x){if(ls-next==NULL)/*栈空，下溢出*/return0;else{x=ls-next-data;return1;}}3.2队列3.2.1队列的基本概念队列：限制插入操作只能在一端进行，而删除操作只能在另一端进行的线性表操作特性：按先进先出(FIFO)或后进后出(LILO)的原则。队首（front）：能进行删除的一端队尾（rear）：能进行插入操作的一端。出队入队队首（front）队尾（rear）队列的基本操作主要：1)InitQueue(Q)：构造一个空队列Q。2)QueueEmpty(Q)：判断队列是否为空。3)QueueLength(Q)：求队列的长度。4)GetHead(Q)：返回Q的队头元素，不改变队列状态。5)EnQueue(Q，x)：插入元素x为Q的新的队尾元素。6)DeQueue(Q)：删除Q的队头元素。7)C1earQueue(Q)：清除队列Q中的所有元素。队列有两种存储表示：顺序队列和链队列。3.2.2队列的链式存储结构…^front队首指针队首队尾rear队尾指针链队：链式存储结构的队列；为一个同时带有首指针和尾指针的单链表队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。链队的类型定义：typedefstructQNode{DataTypedata;structQNode*next;}QType;/*链队中结点的类型*/typedefstructqptr{QType*front,*rear;}LinkQueue;/*链队类型*/队空的条件:lq-front==lq-next==NULL。链队基本运算算法：(1)初始化队列运算功能：置队列lq的rear和front均为NULL。voidInitQueue(LinkQueue*&lq){lq=(LinkQuene*)malloc(sizeof(LinkQuene));lq-rear=lq-front=NULL;/*初始情况*/}(2)入队运算功能：创建一个新结点，将其链接到链队列的末尾，并由rear指向它。VoidEnQueue(LinkQueue*lq,DataTypex){QType*s;/*创建新结点，插入到链队的末尾*/s=(QType*)malloc(sizeof(QType));/*创建新结点，插入到链队的末尾*/s-data=x;s-next=NULL;if(lq-front==NULL&&lq-rear==NULL)/*空队*/lq-rear=lq-front=s;else{lq-rear-next=s;lq-rear=s;}}(3)出队运算功能：将front结点的data域值赋给x，并删除该结点。DataTypeDeQueue(LinkQueue*lq){QType*p;DataTypex;if(lq-front==NULL&&lq-rear==NULL)/*空队*/exit(-1);p=lq-front;x=p-data;if(lq-rear==lq-front)/*若原队列中只有一个结点，删除后队列变空*/lq-rear=lq-front=NULL;elselq-front=p-next;free(p);returnx;}(4)取队头元素运算功能：将front指向结点的data域值赋给xDataTypeGetHead(LinkQueue*lq){DataTypex;if(lq-front==NULL&&lq-rear==NULL)/*空队*/exit(-1);x=lq-front-data;returnx;}(5)判断队空运算算法功能：若链队为空，则返回1；否则返回0intQueueEmpty(LinkQueue*lq){if(lq-front==NULL&&lq-rear==NULL)return1;elsereturn0;}3.2.3循环队列顺序队列：顺序存储结构的队列，即用一组地址连续的存储单元依次存放队头到队尾的元素；顺序队列：实质是运算受限的顺序表；543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空队（b）a、b入队（c）a、b出队，c、d入队（d）假溢出3.2.3循环队列由于队列的队头和队尾的位置是变化的，设立两个指针front和rear，指针front队头，rear指示队尾下一个元素；每插入一新元素，rear增1，每删除一元素，front增1。front=rear=0表示空队列，rear=MAXSIZE表示队满。543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空队（b）a、b入队（c）a、b出队，c、d入队（d）假溢出543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空队（b）a、b入队（c）a、b出队，c、d入队（d）假溢出避免假溢出有两种办法：1)每次一个元素出队，将整个队列向前移动一个位置。2)采用循环队列：将顺序队列的数据区data[0～MAXSIZE-1]看成一个首尾相接的圆环，头尾指针的关系不变循环队列的类型定义：#defineMAXSIZE100/*最大队列长度*/typedefstruct{datatypedata[MAXSIZE];/*存储队列的数据空间*/intfront;/*队头指针，若队列不空，则指向队头元素*/intrear;/*队尾指针，若队列不空，则指向队尾元素的下一个位置*/}SeqQueue;e4e3循环队列特点rearfront0123(3)队空将头尾连接