栈和队列课件

栈（Stack）栈的应用队列（Queue）队列的应用

栈和队列定义3.1栈与线性表相同，数据元素之间仍为一对一的关系。用顺序栈或链栈存储均可。只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈、出栈等函数，具体实现按顺序栈或链栈的存储结构的不同而不同。存储结构运算规则实现方式

逻辑结构限定只能在表的一端进行插入和删除运算的线性表。基本操作

建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。栈

是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶(top);表头(即a1端)称为栈底(bottom)。例如：栈

S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！栈的基本操作InitStack(S)：

构造一个空栈SClearStack(S)：

清除栈S中的所有元素StackEmpty(S)：判断栈S是否为空，若为空，则返回

true；否则返回falseGetTop(S)：

返回S的栈顶元素，但不移动栈顶指针Push(S,x)：插入元素x为新的栈顶元素（入栈操作)Pop(S)：删除S的栈顶元素并返回其值（出栈操作）顺序栈的存储结构和操作的实现

顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，预设一个数组的最大空间,栈底设置在0下标端，栈顶随着插入和删除元素而变化，用一个整型变量top来指示栈顶的位置。a1a2……an顺序栈Sai……0n栈底栈顶top压入(PUSH):

S[++top]=an+1弹出(POP):e=S[top--]顺序栈存储结构的描述：#defineMaxsize100/*设顺序栈的最大长度为100，可依实现情况而修改*/typedefintdatatype;typedefstruct{datatypestack[Maxsize];inttop；/*栈顶指针*/}SeqStack；/*顺序栈类型定义*/SeqStack*s；/*s为顺序栈类型变量的指针*/顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系

栈为空的条件：top==-1;栈满的条件：top==Maxsize-1若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；

对于向上生成的堆栈:入栈：栈指针top“先加后压”:S[++top]=an+1出栈：栈指针top“先弹后减”:e=S[top--]顺序栈的基本操作构造一个空顺序栈

SeqStack*InitStack(){SeqStack*S;S=(SeqStack*)malloc(sizeof(SeqStack));if(!S){printf(“空间不足”)；

returnNULL;}else{S->top=-1;returnS;}}

取顺序栈栈顶元素

datatypeGetTop(SeqStack*S)

{if(S->top==-1){printf("\n栈是空的!");

returnFALSE;}elsereturnS->stack[S->top];}

判别空栈intStackEmpty(SeqStack*S){if(S->top==-1)returnTRUE;elsereturnFALSE;}顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：顺序栈入栈函数PUSH（）SeqStack*Push(SeqStack*S，datatypex){if(S->top==Maxsize-1)

returnNULL;/*栈满*/

else{S->top++;S->stack[S->top]=x;returns;}}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop();顺序栈出栈函数POP()datatypePop(SeqStack*S)

{if(S->top==-1)/*栈空*/

{printf("\nThesequencestackisempty!");returnFALSE;}else{S->top--;returnS->stack[S->top+1];}}

Pop();Printf(Pop());例3-1链栈链栈的构造方式——用top指向栈顶，只能在栈顶插入或删除。栈顶栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈。topa1a2an-1annextdata链栈中每个结点由两个域构成：data域和next域，其定义为：Typedefstructnode{datatypedata;/*数据域*/

structnode*next;/*指针域*/

}LinkStack;LinkStack*top;/*top为栈顶指针*/

将x入栈，修改栈顶指针:top=pan出栈，修改栈顶指针:top=top->next链栈的入栈操作和出栈操作LinkStack*Push((LinkStack*top，datatypex){LinkStack*p;p=(Linkstack*)malloc(sizeof(LinkStack));p->data=x;

p->next=top;top=p;returntop;}链栈入栈操作

LinkStack*Pop(LinkStack*top){LinkStack*q;if(!top){printf("\n链栈是空的!");returnNULL;}else{q=top;/*q指向要删除的栈顶结点*/top=top->next;/*栈顶指针下移*/free(q);

/*释放q指向结点空间*/return

top;}}链栈出栈操作1、数制转换（十进制数N转换为r进制数）

设计思路：用栈暂存余数（低位值）2、括号匹配问题

设计思路：用栈暂存左括号3、子程序的调用

设计思路：用栈暂存指令地址4、逆置一个单链表

设计思路：用栈暂存每一结点的数据3.2栈的应用举例例3.2将十进制整数转换成二至九之间的任一进制数输出

将一个十进制数4327转换成八进制数(10347)8：

⑴

当N≠0，将N%r压入栈s中；⑵

N/r⇒

N；⑶若N＞0，则重复⑴、⑵两步；若N=0，则将栈s的内容依次出栈。解题思路如下：voidconversion(intN,intr){intx=N,y=r;SeqStack*s;s=InitStack();while(N!=0){Push(s,N%r);N=N/r;}printf(“\n十进制数%d所对应的%d进制数是:”，x,y);while(!StackEmpty(s))printf(“%d”,Pop(s));printf(“\n”);}

例3.5利用一个顺序栈将一个带头结点的单链表（a1,a2,…,an）（其中n>=0）逆置为（an,an-1,…，a1）。1、建立一个带头结点的单链表head；2、输出该单链表；3、建立一个空栈s（顺序栈）；4、依次将单链表的数据入栈；5、依次将单链表的数据出栈，并逐个将出栈的数据存入单链表的数据域（自前向后）;6、再输出单链表。

解题思路如下：linklist*backlinklist(linklist*head){linklist*p;p=head->next;initstack();while(p){push(&s,p->data);p=p->next;}p=head->next;while(!stackempty(s)){p->data=pop(&s);p=p->next;}return(head);}；

3.3队列与线性表相同，仍为一对一关系。顺序存储方式：顺序队列(循环队列)和链式存储方式：链队列。只能在队尾入队、队头出队，并遵循先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现按存储方式的不同(顺序队列或链队列)而不同。存储结构运算规则实现方式

逻辑结构只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。基本操作

入队、出队、建空队列、判队空或队满等。尾部插入头部删除队列定义队列（Queue）是仅在表尾进行插入操作、在表头进行删除操作的线性表。它是一种先进先出（ＦＩＦＯ）的线性表。例如：队列

Q=(a1

,a2,a3,……….,an-1,an)在队尾插入元素称为入队；在队首删除元素称为出队。队首队尾

队列的实现方式是本节重点，关键是掌握入队和出队等操作。

具体实现按存储结构的不同（顺序队列或链队列）而不同。队列的基本操作（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）ClearQueue(Q)：清除队列Q中的所有元素

链队列类型定义：

typedefstruct

{Qnode*front;/*队头指针*/

Qnode*rear;/*队尾指针*/}LinkQueue;

LinkQueue*q;/*q是链队列指针,其中封装了队头指针和队尾指针*/链队列结点类型定义：

typedefStructQnode

{datatypedata;

/*数据域*/

StructQnode*next;/*指针域*/}Qnode;

链队列的几种状态示意图：此时，front==rear修改rear指针修改头结点的指针域①链队列为空的特征：front==rear②链队列会满吗？一般不会，因为删除时有free动作，除非内存不足！修改rear指针入队（尾部插入）：rear->next=S;rear=S;出队（头部删除）：front->next=front->next->next;③怎样实现链队列的入队操作和出队操作？假设S所指结点为入队结点，则有LinkQueue*InitQueue()

{LinkQueue*q;/*q为链队列指针,q中封装了队头指针和队尾指针*/Qnode*p;/*p为指向链队列结点的指针*/Q=(LinkQueue*)malloc(sizeof(LinkQueue));p=(Qnode*)malloc(sizeof(Qnode));p->next=NULL;q->front=q->rear=p;returnq;}构造一个空链队列datatypeGetHead(LinkQueue*Q){if(Q->front==Q->rear)

{printf(“\n链队列为空!”);

returnFALSE;}else

returnQ->front->next->data；/*返回队头元素的值*/

}取链队列的队头元素voidEnQueue(LinkQueue*Q，datatypex)

{

Qnode*p;/*p为指向链队列结点的指针*/

p=(Qnode*)malloc(sizeof(Qnode))；

p->data=x；

p->next=NULL；

Q->rear->next=p；

Q->rear=p；

}

链队列的入队操作datatypeDeQueue(LinkQueue*Q)

{Qnode*p;/*p为指向链队列结点的指针*/

datatypex;

if(Q->front==Q->rear)

{printf("队列为空，无法删除！");returnFALSE;}

else{p=Q->front->next；/*p指向链队列的队头结点*/

x=p->data；/*将队头元素的值赋给变量x*/

Q->front->next=p->next；/*出队列，修改队头指针*/

if(Q->rear==p)Q->rear=Q->front；/*若出队列后队列为空，则还应当修改队尾指针，使队尾指针指向头结点*/

free(p)；/*释放空间*/

returnx;/*返回已出队元素（即原队头元素）的值*/

}}链队列的出队操作循环（顺序）队列的类型定义：#defineMAXSIZE100/*最大队列长度*/typedefstruct{datatypedata[MAXSIZE]；

/*存储队列的数据空间*/intfront；

/*队头指针，若队列不空，则指向队头元素*/intrear；

/*队尾指针，若队列不空，则指向队尾元素的下一个位置*/}SeqQueue;

头、尾指针与队列中元素之间的关系示意图：入队操作时的尾指针运算:rear=(rear+1)%Maxsize出队操作时的头指针运算:front=(front+1)%Maxaize问题：在循环队列中，由于队空时有front==rear；队满时也有front==rear；因此我们无法通过front==rear来判断队列是“空”还是“满”。循环队列示意图循环队列的几种状态循环队列空的条件

:front==rear循环队列满的条件：front==(rear+1)%

MAXSIZE循环队列长度为：L=（rear－front+MAXSIZE）%MAXSIZE

J2J3 J1J4

J5frontrear解决办法：少用一个元素空间，约定以“队头指针在队尾指针的下一位置(指环状的下一位置)”作为队列“满”的标志。也就是说，若数组的大小是MAXSIZE，则该数组所表示的循环队列最多允许存储MAXSIZE-1个结点。注意：rear所指的结点始终为空。循环队列满的示意图：经过约定后的循环队列操作示意图（p.70，图3.13改）循环队列的基本操作实现以创建队列、入队和出队三种基本操作为例1、构造（初始化）一个空队列算法要求：生成一空队列算法步骤：

①为队列分配存储空间；

②设置队列为空队列，其特征为：

front=rear=0构造一个空队列qSeqQueue*InitQueue(){SeqQueue*q；

q=(SeqQueue*)malloc(sizeof(SeqQueue))；

/*开辟一个足够大的存储队列空间*/q->front=q->rear=0；

/*将队列头尾指针置为零*/returnq；

/*返回队列的首地址*/}算法说明：向循环队列的队尾插入一个元素。分析：(1)入队前应当先判断队列是否已满？

if((q->rear+1)%Maxsize)==q->front)returnfalse;(2)入队动作如下:q->data[q->rear]=x;q->rear=(q->rear+1)%Maxsize;2、入队操作intEnQueue(SeqQueue*q,datatypex){if((q->rear+1)％MAXSIZE==q->front)

{printf(“\n循环队列满!”);

returnFALSE;}q->data[q->rear]=x；

q->rear=(q->rear+1)%MAXSIZE;returnTRUE;}循环队列入队操作3、出队操作算法说明：