数据结构课件：第3章栈和队列

1、第三章 栈和队列3.1 栈3.1.1 栈的概念一、什么是栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除 能进行插入和删除的一端称为栈顶，另一端称为栈底。 称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。3.1 栈出栈进栈栈的特点后进先出第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素栈的示意图栈顶栈底ana2a13.1 栈二、栈的基本操作1）初始化操作 InitStack(&S) 功能：构造一个空栈S。2）销毁栈操作 DestroyStack(

2、&S) 功能：销毁一个已存在的栈。3）置空栈操作 ClearStack(&S) 功能：将栈S置为空栈。4）取栈顶元素操作 GetTop(S, &e) 功能：取栈顶元素，并用e 返回。3.1 栈二、栈的基本操作5）进栈操作 Push(&S, e) 功能：元素e进栈。6）退栈操作 Pop(&S, &e) 功能：栈顶元素退栈，并用e返回。7）判空操作 StackEmpty(S) 功能：若栈S为空，则返回True，否则，栈不空返回False。3.1 栈3.1.2 栈的顺序存储和实现一、栈的顺序存储结构#define STACK_INIT_SIZE 100 / 栈存储空间的初始分配量#define ST

3、ACKINCREMENT 10 / 空间的分配增量typedef struct ElemType *base; /栈空间基址 ElemType *top; /栈顶指针 int stacksize; /当前分配的栈空间大小SqStack;3.1 栈3.1.2 栈的顺序存储和实现顺序栈的图示S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等如何实现？3.1 栈3.1.2 栈的顺序存储和实现topbasebasetopABCDE空栈basetopAA进栈B C D E

4、进栈basetopABE D C出栈称为：栈满空栈 top = base 栈满 top-base = stacksize (无可分配空间)12340ABCDE3.1 栈不可扩充栈的操作top=012340栈空栈顶指针top，指向实际栈顶后的空位置，初值为 basetop进栈A栈满BCDE设数组大小为Mtop=M，栈满，此时入栈，则上溢 (overflow)toptoptoptoptoptoptoptoptoptop栈空top=base，栈空，此时出栈，则下溢(underflow)top12340出栈12340ABCDE3.1 栈可扩充栈的操作栈顶指针top，指向实际栈顶后的下一个位置，初值为

5、top=basetop进栈A出栈栈当前空间不足，需扩充BCDE 设栈的初始分配量为 Stacksize = STACK_INIT_SIZE。 若 top = Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充 STACK_INCREMENT； 若无可利用的存储空间，则上溢 (overflow)。toptoptoptoptoptoptoptoptoptop栈空若top=base, 栈空，此时出栈，则下溢(underflow)base栈空topbase base top12340123403.1 栈二、顺序栈基本操作的算法1）初始化操作 InitStack ( SqStack &S )参

6、数：S是存放栈的结构变量功能：建一个空栈SS.stacksizeS.topS.base10099nn-1n-2103.1 栈初始化操作算法Status InitStack ( SqStack &S ) /构造一个空栈S S.base = ( ElemType *) malloc ( STACK_INIT_SIZE * sizeof(ElemType) ); /为顺序栈动态分配存储空间 if ( ! S. base) exit(OVERFLOW); /分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; / InitStac

7、k99nn-1n-210anan-1a2a1S.stacksizeS.topS.base2） 销毁栈操作 DestroyStack(SqStack &S)功能：销毁一个已存在的栈100null0null3.1 栈Status DetroyStack ( SqStack &S ) if ( ! S.base ) return ERROR; /若栈未建立（尚未分配栈空间） free ( S.base ); /回收栈空间 S.base = S.top = NULL; S.stacksize = 0; return OK; /DetroyStack 销毁操作算法3.1 栈3）置空栈操作ClearSta

8、ck (SqStack &S)功能：将栈S置为空栈 S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1S.stacksizeS.topS.base10099nn-1n-210anan-1a2a13.1 栈Status ClearStack ( SqStack &S ) if ( ! S.base ) return ERROR; / 若栈未建立（尚未分配栈空间） S.top = S.base; return OK; /ClearStack 置空操作算法3.1 栈eanS.stacksizeS.topS.base10099nn-1n-210anan-1a2

9、a14）取栈顶元素操作GetTop ( SqStack S, ElemType &e )功能：取栈顶元素，并用e返回3.1 栈Status GetTop ( SqStack S, ElemType &e ) if ( S.top=S.base ) return ERROR; /栈空 e = *(S.top-1); return OK; /GetTop取栈顶元素操作算法3.1 栈5）进栈操作 Push ( SqStack &S, ElemType e )功能：元素 e 进栈。S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1e进栈前e进栈后S.stack

10、sizeS.topS.base10099nn-1n-210eanan-1a2a13.1 栈进栈操作算法Status Push ( SqStack &S, ElemType e ) /将元素e插入栈中，使其成为新的栈顶元素 if ( S.top-S.base=S.stacksize ) / 若栈满则追加存储空间 S.base = (ElemType * ) realloc ( S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType); if ( ! S. base ) exit(OVERFLOW); /存储分配失败 S.top = S.bas

11、e + S.stacksize; S.stacksize += STACKINCREMENT; * S.top + = e; /元素e 插入栈顶，后修改栈顶指针 return OK; /Push3.1 栈出栈操作前S.stacksizeS.topS.base10099nn-1n-210anan-1a2a16）出栈操作 Pop ( SqStack &S, ElemType &e )功能：栈顶元素退栈，并用 e 返回。3.1 栈ean出栈操作后S.stacksizeS.topS.base10099nn-1n-210an-1a2a1Status Pop ( SqStack &S, ElemType

12、&e ) if ( S.top=S.base ) return ERROR; / 栈空 e = * - S.top; / -S.top; e=*S.top; return OK; /Pop出栈操作算法3.1 栈栈的链式存储结构，也称链栈。栈顶栈底 在前面学习了线性链表的插入、删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法。3.1.3 栈的链式存储和实现3.1 栈Data nextSan-1a1an小 结1、栈是限定仅能在表尾一端进行插入、删除操作的线性表2、栈的元素具有后进先出的特点3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针3.1 栈1）问题的提

13、出从键盘一次性输入一串算术表达式，给出计算结果。2+3*(5-4)=5栈的应用举例表达式求值3.2 栈的应用举例2）表达式的构成 操作数+运算符+界符1234如何确定运算符的运算顺序？常数+、-、*、/( )、#3.2 栈的应用举例3）表达式的求值： 例：5+6(1+2)-4 按照四则运算法则，上述表达式的计算过程为： 5+6(1+2)-4 = 5+63-4 = 5+18-4 = 23-4 = 194）算符优先关系表 表达式中任何相邻运算符 1、2 的优先关系有： 1 2：1的优先级 高于 2+ 2 1 -*/()#+ - * / ( ) # = 注：1、2是相邻算符，1在左，2在右3.2 栈

14、的应用举例5）算符优先算法从左向右扫描表达式： 遇操作数保存； 遇运算符号j与前面的刚扫描过的运算符i比较： 若ij 则保存j（因此已保存的运算符的优先关系为123j 则说明i是已扫描的运算符中优先级最高者，可进行运算 若i=j 则说明括号内的式子已计算完，需要消去括号 5 + 4 (1 + 2) - 6后面也许有优先级更高的算符+ +(后保存的算符优先级高用两个栈分别保存扫描过程中遇到的操作数和运算符3.2 栈的应用举例 在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符；一个是OPND栈，用以保存操作数或运算结果。算法的基本思想是： 1、首先置操作数栈为空栈，表达式起始符

15、“#”为运算符栈的栈底元素。 2、依次读入表达式中每个字符，若是操作数，则进OPND栈；若是运算符，则与OPTR栈的栈顶运算符比较优先级后作相应操作。 直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。3.2 栈的应用举例表达式求值示意：5 + 6 ( 1 + 2 ) - 4topbaseOPTR栈#OPND栈topbase5toptop+top6toptop(top1top+top2toptoptoptop3toptoptoptoptop18toptoptoptop23top-top4toptoptoptop19toptoptop5读入表达式过程：+6(1+2)-4

16、#= 191+2=363=185+18=2323-4=193.2 栈的应用举例算法描述operandType EvaluateExpression( ) /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符、界限符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=getchar( ); while ( c!=# | GetTop(OPTR)!=# ) if (! In (c, OP) / In(c, OP)判断c是否为运算符 Push(OPND, c); c=getchar( ); /不是运算符

17、则进栈 else3.2 栈的应用举例 switch ( Precede(GetTop(OPTR), c ) /判定OPTR的栈顶运算符1与读入的运算符2间的优先关系 case : /新输入的算符c优先级低，即栈顶算符优先权高 /出栈并将运算结果入栈OPND Pop ( OPTR, theta); Pop ( OPND, b); Pop(OPND, a); Push ( OPND, Operate(a, theta, b) ); /进行二元运算a b break; /switch /while return GetTop(OPND); /EvaluateExpression3.2 栈的应用举例

18、递归是很有用的工具，在数学和程序设计等许多领域中都会用到。 递归定义：简单说，一个用自己定义自己的概念，称为递归定义。 任何一个递归程序都可以通过非递归程序实现。3.3 栈与递归3.4.1 队列的概念一、什么是队列 队列是限定仅能在表头进行删除，表尾进行插入的线性表。（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除 能进行插入的一端称为队尾，能进行删除的一端称为队头。 称插入操作为入队，删除操作为出队。3.4 队列a1 a2 a3 an队头队尾出队列队列的示意图队列的特点先进先出第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出

19、队的元素为队尾元素出队列3.4 队列二、队列的基本操作1）初始化操作 InitQueue(&Q) 功能：构造一个空队列Q。2）销毁操作 DestroyQueue(&Q) 功能：销毁已存在队列Q。3）置空操作 ClearQueue(&Q) 功能：将队列Q置为空队列。4）出队操作 DeQueue(&Q,&e) 功能：删除Q的队头元素。5）取队头元素操作 GetHead(Q,&e) 功能：取队头元素，并用e返回。3.4 队列二、队列的基本操作6）入队操作 EnQueue(&Q, e ) 功能：将元素e插入Q的队尾。7）判空操作 QueueEmpty(Q) 功能：若队列Q为空，则返回True，否则返回

20、False。3.4 队列3.4.2 循环队列队列的顺序存储和实现一、队列的顺序存贮结构#define MAXSIZE 100 /最大队列长度typedef struct ElemType * base; /初始化时分配存储空间的基址 int front; /队头指针，指向队头元素 int rear; /队尾指针，指向队尾元素的下一个位置SqQueue;队头,队尾指针是用整型实现的3.4 队列Q.rearQ.frontJ1J2J3Q.rearQ.frontJ3(a)空队列(b)J1,J2和J3相继入队列(c)J1和J2相继出队(d)J4,J5和J6相继入队之后,J3出队Q.rearQ.front

21、012345Q.rearQ.frontJ6J5J4Q.front,Q.rear均为整数用箭头指示只是为了直观又有J7入队,该怎么办？3.4 队列3.4 队列队列基本操作123450队空front=0rear=0123450frontJ1,J2,J3入队J1J2J3rearJ4,J5,J6入队rear123450J4J5J6front设两个指针：front,rear。rear指向队尾元素的下一个位置；front指向队头元素。初值 front=rear=0队空条件：front=rear 入队列：Q.base rear+ = e; 出队列：e =Q.base front+ ;rearrearfron

22、trear123450J1,J2,J3出队J1J2J3frontfrontfront又有J7入队,该怎么办？Q.base3.4 队列存在问题设数组大小为M，则：当front=0，rear= M 时，再入队发生溢出真溢出当front0，rear= M 时，再入队发生溢出假溢出解决方案队首固定，每次出队后将剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让 Q.baseM-1 接在 Q.base0 之后，若rear+1=M，则令rear=0;rear123450J4,J5,J6入队J4J5J6front0M-11frontrear.3.4 队列实现：利用“模”运算入队：Q.basere

23、ar=e; rear=(rear+1)%M; 出队：e=Q.basefront; front=(front+1)%M; 队满、队空判定条件?012345rearfrontJ7J5J6012345frontJ4J9J8rearJ5J6J4012345rearfrontJ4,J5,J6出队J7,J8,J9入队队空：front=rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front队满：front=rear3.4 队列J4,J5,J6出队J7,J8入队队满：front=(rear+1)%M 少用一个元素空间： 队

24、空：front=rear 队满：(rear+1)%M=front队空：front=rearJ5J6J4012345rearfront012345rearfrontJ7J5J6012345frontJ4J8rear1）初始化操作 InitQueue_Sq ( SqQueue &Q ) 参数：Q是存放队列的结构变量功能：建一个空队列Q算法：Status InitQueue_Sq ( SqQueue &Q ) /构造一个空队列Q Q.base=(ElemType * )malloc (MAXSIZE * sizeof (ElemType); if ( !Q.base ) exit (OVERFLOW

25、); /存储分配失败 Q.front = Q.rear = 0; Return OK; /InitQueue_Sq二、循环队列的基本操作算法3.4 队列Q.frontQ.rear54 03 122）入队操作 EnQueue_Sq ( SqQueue &Q, ElemType e )功能：将元素 e 插入队尾Q.frontQ.rear54 03 12J1J3J2eQ.frontQ.rear54 03 12J1J3J2元素e入队前元素e入队后3.4 队列入队操作算法： Status EnQueue_Sq ( SqQueue &Q, ElemType e ) /将元素e插入队尾 if ( (Q.re

26、ar+1)%MAXSIZE= =Q.front ) return ERROR ; /队满 Q.baseQ.rear = e ; /将元素e插入队尾 Q.rear = (Q.rear+1)%MAXSIZE; /修改队尾指针 return OK; /EnQueue_Sq3.4 队列3)出队操作 DeQueue_Sq (SqQueue &Q, QElemType &e )功能：删除队头元素，用e返回其值Q.frontQ.rear54 03 12J1J3J2Q.frontQ.rear54 03 12J1J3J2出队操作前出队操作后eJ13.4 队列出队操作算法 ：Status DeQueue_Sq (

27、 SqQueue &Q, ElemType &e ) /删除队头元素，用e返回其值，并返回OK；否则返回ERROR if ( (Q.rear= =Q.front ) return ERROR ; /队空 e = Q.baseQ.front ; / 取队头元素 e Q.front = (Q.front+1)%MAXSIZE; /修改队头指针 return OK; /EnQueue_Sq3.4 队列3.4.3 链队列队列的链式存储结构和实现一、链队列Q.frontQ.rear空链队列J1Q.frontQ.rear J2链队列图示3.4 队列二、链队列的类型定义typedef struct QNod

28、e /链队列结点的类型定义 ElemType data; struct QNode * next;QNode, * QueuePtr;3.4 队列typedef struct / 链队列的表头结点的的类型定义 QueuePtr front; /队头指针，指向链表的头结点 QueuePtr rear; /队尾指针，指向队尾结点LinkQueue;头结点 .front队头队尾rearfront指向头结点，rear指向队尾3.4 队列链式队列的基本操作frontrearx入队xfrontreary入队xyfrontrearx出队xyfrontrear空队frontreary出队判断队空的条件：fro

29、nt=rear 三、队列的应用1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；3）离散事件的模拟模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。在操作系统课程中讲到3.4 队列小 结1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示；4、入队操作要修改队尾指针，出队操作要修改队头指针。3.4 队列栈和队列练习1、已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列：A）1234 B）4321 C）2143 D）4123

30、答案：D2、若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear和 front 的值分别为多少？A）1和5 B）2和4 C）4和2 D）5和1答案：B栈和队列3、写出循环队列队空、队满的判断方法及条件（一种）。答案：方法：少用一个存储单元判满条件 (Q.rear+1)%Q. queuesize = = Q.front判空条件 Q.rear = = Q.front栈和队列4、若将一个双端队列顺序表示在一维数组 Vm 中，两个端点设为 end1 和 end2，并组织成一个循环队列。试写出双端队列所用指

31、针 end1 和 end2 的初始化条件及队空与队满条件。答案：双端队列实际上就是一个双端的栈。假设：end1端顺时针进栈，end2端逆时针进栈初始化条件：end1 = end2 = 0;队空条件：end1 = end2;队满条件：( end1 + 1 ) % m = end2; end1end2栈和队列问题：编程判断一个字符序列是否是回文（回文是指一个字符序列以中间字符为基准两边字符完全相同）。算法设计 程序从键盘接受一个字符序列存入字符串str中，字符串长度80，输入字符序列以回车符为结束标记，字符串str中不包括回车换行符。 将字符串中字符逐个分别存入队列和栈，然后逐个出队和退栈，比较出

32、队的元素和退栈的元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。栈和队列#include stdio.h#define MAX 100#define OK 1#define ERROR 0typedef int Status; /* 返回值状态 */typedef struct char * base; char * top; int stacksize; SqStack; /* 栈 */SqStack s;栈和队列Status InitStack ( SqStack * s ) s-base = (char *)malloc( MAX*sizeof(char) ); s-top

33、= s-base; s-stacksize = MAX; return OK;Status Push ( SqStack * s, char e ) * s-top + =e;Status Pop ( SqStack * s, char * e ) *e = * - s-top;Status StackEmpty ( SqStack s ) return (s.top=s.base);栈和队列typedef struct char *base; int front, rear; SqQueue; /* 队列 */SqQueue q;栈和队列Status InitQueue ( SqQueue

34、* q ) q-base = (char *)malloc( MAX*sizeof(char) ); q-front = q-rear = 0; return OK;Status QueueEmpty ( SqQueue q ) return q.front = q.rear;Status EnQueue ( SqQueue * q, char e ) q-baseq-rear+=e;Status DeQueue ( SqQueue * q, char * e ) *e = q-baseq-front+;栈和队列main( ) char c, e; InitStack (&s); InitQu

35、eue (&q); while ( ( c=getchar() ) !=n ) /* 输入 */ Push ( &s, c); EnQueue (&q, c); while ( ! StackEmpty(s) ) /* 判断 */ Pop ( &s, &c); DeQueue (&q, &e); if ( c!=e ) printf(Errorn); exit ( ); else putchar(c); printf (nOK!);队列应用提出问题 某运动会设立 N 个比赛项目，每个运动员可以参加13个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又可使总的竞赛日程最短。问题抽象 若将此问题抽象成数学模型，则归属于“划分子集”问题。 N 个比赛项目构成一个大小为 n 的集合，有同一运动员参加的项目则抽象为“冲突”关系。 栈和队列例如：某运