数据结构案例教程（CC++版）第2版 课件 第3章 操作受限的线性表：栈和队列

第3章操作受限的线性表：栈和队列导学问题1：数制转换问题【问题描述】

已知十进制数n，试将其转换成对应的八进制数。【分析】以n=1269为例

计算过程中，取余数的顺序正好与计算产生余数的顺序相反的，因此可将每次产生的余数依次保存起来，转换结束后，再按保存的逆序取出余数打印即可。

显然，保存的余数应该具备“后进先出”的特点，可用栈作为数据结构。导学问题2：银行排队问题【问题描述】

请设计一个简单的模拟银行排队系统，要求程序具有三项菜单：1）取号。选择该菜单后，为客户产生一个排队号。2）叫号。选择该菜单后，显示可服务的客户排队号。3）退出系统。【分析】

银行排队问题属于典型的先来先服务，因此需要将产生的排队号存放在具有“先进先出”特性的数据结构中，队列结构可以满足要求。

3.1栈3.1.1知识学习栈：限定仅在表尾进行插入和删除操作的线性表。空栈：不含任何数据元素的栈。允许插入和删除的一端称为栈顶，另一端称为栈底。（a1,a2,……,an）栈顶栈底abc入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图3.1栈栈的操作特性：后进先出abc入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶3.1栈栈的示意图例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：3.1栈例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶情况2：3.1栈出栈序列：b栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？3.1栈如何改造数组实现栈的顺序存储？

012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。

top栈的顺序存储结构及基本操作出栈：top减1进栈：top加1栈空：top=-1

012345678a1topa2topa3top栈满：top=MaxSize-1栈的顺序存储及基本操作constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; inttop;}SeqStack;顺序栈的类型定义voidInitStack(SeqStack&S){S.top=-1;}顺序栈的实现——初始化voidPush(SeqStack&S,ElemTypex){if(S.top==MAXSIZE-1){cout<<"栈已满"<<endl;exit(1);}

S.top++;

S.data[S.top]=x;}顺序栈的实现——入栈ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"栈已空"<<endl;exit(1);}

ElemTypex=S.data[S.top];

S.top--; returnx;}顺序栈的实现——出栈ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"栈已空"<<endl;exit(1);}

returnS.data[S.top];}顺序栈的实现——取栈顶元素boolStackEmpty(SeqStack&S){ returnS.top==-1;}顺序栈的实现——判断栈空boolStackEmpty(SeqStack&S){ returnS.top==MAXSIZE-1;}顺序栈的实现——判断栈满heada1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。栈的链式存储及基本操作栈顶栈底链栈：栈的链接存储结构topanan-1a1∧两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底栈的链式存储及基本操作typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}*LinkStack;链栈的类型定义voidInitStack(LinkStack&S){ S=NULL;}链栈的实现——初始化算法描述：voidPush(LinkStack&S,ElemTypex){LinkStackp=newNode;

p->data=x;

p->next=S;

S=p;}Sanan-1a1∧xpS链栈的实现——入栈算法描述：ElemTypePop(LinkStack&S){

if(S==NULL)

{cout<<"栈已空";exit(1);}

ElemTypex=S->data;//暂存栈顶元素

LinkStackp=S;

S=S->next;//删除栈顶结点

deletep;

returnx;}Sanan-1a1∧Sp

链栈的实现——出栈ElemTypeTop(LinkStack&S){ if(S==NULL) {cout<<"栈已空";exit(1);} returnS->data;}链栈的实现——取栈顶元素boolStackEmpty(LinkStack&S){ returnS==NULL;}链栈的实现——判断栈空voidDestroyListStack(LinkStack&S){LinkStackp;

while(S)

{

p=S;

S=S->next;

deletep;

}}链栈的实现——销毁顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。3.1.2知识应用——导学问题1voidconversion(intn){SeqStackS;InitStack(S);while(n){Push(S,n%8);n=n/8;}while(!StackEmpty(S))cout<<Pop(S);cout<<endl;}3.1.3知识拓展——算术表达式求值1、中缀表达式直接求值为实现算符优先算法，可以使用两个工作栈：

1）运算符OPTR栈,用以寄存运算符；2）操作数OPND栈,用以寄存操作数或运算结果。算法步骤：参见教材3.1.3知识拓展——算术表达式求值2、利用后缀表达式求值

将中缀表达式变成等价的后缀表达式时，表达式中操作数次序不变，而操作符次序会发生变化，同时需要去掉圆括号。因此设置一个栈OPTR用以存放操作符。。算法步骤：参见教材3.1.3知识拓展——栈和递归求阶乘的递归算法intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}3.1.3知识拓展——栈和递归递归函数的内部执行过程⑴运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；⑵每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；⑶每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。3.1.3知识拓展——栈和递归哪些问题可以用递归解决大问题可以分解为小问题可以确定递归到何时终止3.2队列3.2.1知识学习队列的基本概念

队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。队尾队头a1a2a3入队出队队列的操作特性：先进先出constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; intrear;}SeqQueue;队列的顺序存储及基本操作（循环队列）（1）循环队列的初始化voidInitQueue(SeqQueue&Q){Q.front=Q.rear=0;}（2）循环队列的入队操作voidEnQueue(SeqQueue&Q,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {cout<<"队列已满"<<endl;exit(1);}Q.rear=(Q.rear+1)%MAXSIZE; Q.data[Q.rear]=x;

}队列的顺序存储及基本操作（循环队列）（3）循环队列的出队操作ElemTypeDeQueue(SeqQueue&Q){if(Q.front==Q.rear) {cout<<"队列已空"<<endl;exit(1);} Q.front=(Q.front+1)%MAXSIZE; ElemTypex=Q.data[Q.front];returnx;}队列的顺序存储及基本操作（循环队列）（4）判断循环队列是否为空的操作boolQueueEmpty(SeqQueue&Q){ returnQ.front==Q.rear;}（5）判断循环队列是否为满的操作boolQueueFull(SeqQueue&Q){ return(Q.rear+1)%MAXSIZE==Q.front;}队列的顺序存储及基本操作（循环队列）链队列：队列的链接存储结构队头指针即为链表的头指针heada1a2an∧如何改造单链表实现队列的链接存储？rearfront队列的链式存储及基本操作（链队列）非空链队列fronta1a2an∧rear空链队列front∧rear队列的链式存储及基本操作（链队列）typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstruct{ Node*front; Node*rear;}LinkQueue;队列的链式存储及基本操作（链队列）voidInitQueue(LinkQueue&Q){Q.front=Q.rear=newNode; Q.front->next=NULL;}front∧rear链队列的操作——初始化xpfronta1an∧rearrearfrontxp∧∧rearrear算法描述：p->next=NULL;rear->next=p;rear=p;有了头结点两种情况下的处理是一致的。链队列的操作——入队∧voidEnQueue(LinkQueue&Q,ElemTypex){

Node*p=newNode;//产生新结点p p->data=x; p->next=NULL; Q.rear->next=p;//将结点p插入到队尾 Q.rear=p; }链队列的操作——入队fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;链队列的操作——出队fronta1a2an∧rearp考虑边界情况：队列中只有一个元素？fronta1p∧rear∧rear仅1个元素的队列判断：if(rear==p)rear=front;如何判断边界情况？链队列的操作——出队ElemTypeDeQueue(LinkQueue&Q){

if(Q.front==Q.rear)

{cout<<"队列已空"<<endl;exit(1);} Node*p=Q.front->next; ElemTypex=p->data; Q.front->next=p->next; if(Q.rear==p)

Q.r