数据结构和算法设计-第3章 栈和队列lhf

第三章 栈和队列,3.1 栈 3.2 栈的应用举例 3.3 栈与递归3.4 队列,3.1 栈,3.1.1 栈的概念一、什么是栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,能进行插入和删除的一端称为栈顶，另一端称为栈底。 称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。,3.1 栈,栈的特点后进先出,第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素,3.1 栈,二、栈的基本操作1）初始化操作 InitStack(&S) 功能：构造一个空栈S。2）销毁栈操作 DestroyStack(&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 STACKINCREMENT 10 / 空间的分配增量typedef struct ElemType *base; /栈空间基址 ElemType *top; /栈顶指针 int stacksize; /当前分配的栈空间大小SqStack;,3.1 栈,3.1.2 栈的顺序存储和实现,顺序栈的图示,S.stacksizeS.topS.base,100,约定栈顶指针指向栈顶元素的下一个位置,3.1 栈,3.1.2 栈的顺序存储和实现,top,base,空栈,B C D E进栈,E D C出栈,称为：栈满,空栈 top = base 栈满 top-base = stacksize (无可分配空间),3.1 栈,不可扩充栈的操作,栈空,栈顶指针top，指向实际栈顶后的空位置，初值为 base,进栈,A,栈满,B,C,D,E,设数组大小为Mtop=M，栈满，此时入栈，则上溢 (overflow),栈空,top=base，栈空，此时出栈，则下溢(underflow),出栈,3.1 栈,可扩充栈的操作,栈顶指针top，指向实际栈顶后的下一个位置，初值为 top=base,进栈,A,出栈,栈当前空间不足，需扩充,B,C,D,E,设栈的初始分配量为 Stacksize = STACK_INIT_SIZE。 若 top = Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充 STACK_INCREMENT； 若无可利用的存储空间，则上溢 (overflow)。,栈空,若top=base, 栈空，此时出栈，则下溢(underflow),base,栈空,top,3.1 栈,二、顺序栈基本操作的算法1）初始化操作 InitStack ( SqStack &S )参数：S是存放栈的结构变量功能：建一个空栈S,100,3.1 栈,初始化操作算法Status InitStack ( SqStack / InitStack,2） 销毁栈操作 DestroyStack(SqStack &S)功能：销毁一个已存在的栈,100,3.1 栈,Status DetroyStack ( SqStack /DetroyStack,销毁操作算法,3.1 栈,3）置空栈操作ClearStack (SqStack &S)功能：将栈S置为空栈,3.1 栈,Status ClearStack ( SqStack /ClearStack,置空操作算法,3.1 栈,an,4）取栈顶元素操作GetTop ( SqStack S, ElemType &e )功能：取栈顶元素，并用e返回,3.1 栈,Status GetTop ( SqStack S, ElemType /GetTop,取栈顶元素操作算法,3.1 栈,5）进栈操作 Push ( SqStack &S, ElemType e )功能：元素 e 进栈。,3.1 栈,进栈操作算法Status Push ( SqStack /Push,3.1 栈,6）出栈操作 Pop ( SqStack &S, ElemType &e )功能：栈顶元素退栈，并用 e 返回。,3.1 栈,Status Pop ( SqStack /Pop,出栈操作算法,3.1 栈,栈的链式存储结构，也称链栈。,栈顶,栈底,在前面学习了线性链表的插入、删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法。,3.1.3 栈的链式存储和实现,3.1 栈,小 结1、栈是限定仅能在表尾一端进行插入、删除操作的线性表2、栈的元素具有后进先出的特点3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针,3.1 栈,3.2 栈的应用举例：数制转换,例如：（1348)10 = (2504)8 ,其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,计算时从低位到高位顺序产生八进制数的各个数位,输出显示时按从高位到低位的顺序输出,数制转换算法,void conversion ( ) /对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S); /建空栈 scanf (%d,N); /输入一个非负十进制整数 while (N) / N不等于零循环 Push(S, N % 8); / N/8第一个余数进栈 N = N/8; /整除运算 while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); /输出存放在栈中的八制数位 DestroyStack(S); /erorr in book / conversion,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。,合理的作法是：,行编辑过程分析,则实际有效的是下列两行： while (*s) putchar(*s+);,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,while (ch != EOF / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈if (ch != EOF) ch = getchar(); /为下一行准备,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的栈内字符传送至调用过程的数据区；,1）问题的提出从键盘一次性输入一串算术表达式，给出计算结果。,栈的应用举例表达式求值,3.2 栈的应用举例,2）表达式的构成 操作数+运算符+界符,1,2,3,4,常数,+、-、*、/,( )、#,3.2 栈的应用举例,3）表达式的求值： 例：5+6(1+2)-4 按照四则运算法则，上述表达式的计算过程为： 5+6(1+2)-4 = 5+63-4 = 5+18-4 = 23-4 = 19,4）算符优先关系表 表达式中任何相邻运算符 1、2 的优先关系有： 1 2：1的优先级 高于 2,注：1、2是相邻算符，1在左，2在右,3.2 栈的应用举例,5）算符优先算法,从左向右扫描表达式： 遇操作数保存； 遇运算符号j与前面的刚扫描过的运算符i比较： 若ij 则说明i是已扫描的运算符中优先级最高者，可进行运算 若i=j 则说明括号内的式子已计算完，需要消去括号,5 + 6 (1 + 2) - 6,后面也许有优先级更高的算符,+,+,(,后保存的算符优先级高,用两个栈分别保存扫描过程中遇到的操作数和运算符,3.2 栈的应用举例,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符；一个是OPND栈，用以保存操作数或运算结果。算法的基本思想是： 1、首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； 2、依次读入表达式中每个字符，若是操作数，则进OPND栈；若是运算符，则与OPTR栈的栈顶运算符比较优先级之后作相应操作； 直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。,3.2 栈的应用举例(17 Oct),表达式求值示意：5 + 6 ( 1 + 2 ) - 4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,= 19,1+2=3,63=18,5+18=23,23-4=19,3.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( ); /不是运算符则进栈 else,3.2 栈的应用举例,switch ( Precede(GetTop(OPTR), c ) /判定OPTR的栈顶运算符1与读入的运算符2(即c)间的优先关系 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); /EvaluateExpression,3.2 栈的应用举例,递归是很有用的工具，在数学和程序设计等许多领域中都会用到。 递归定义：简单说，一个用自己定义自己的概念，称为递归定义。 函数的递归调用：就是函数实现中存在自己调用自己的情况。 任何一个递归程序都可以通过非递归来程序实现，只是递归程序代码简洁、可读性好。,3.3 栈与递归,课堂练习,1、向一个栈顶指针为top的链栈中插入一个p所指的结点时，其操作步骤为：（ b ） a. top-next=p; b. p-next=top-next; top-next=p; c. p-next=top; top=p; d. p-next=top; top=top-next;2、对于栈操作数据的原则是：（ b ） a. 先进先出 b. 后进先出 c. 后进后出 d. 部分顺序3、若已知一个栈的入栈序列是1，2，3，,n, 其输出序列为p1,p2,p3,pn，若pn=n，则pi是：（ d ） a. i b. n-i c. n-i+1 d. 不确定3、若已知一个栈的入栈序列是1，2，3，,n, 其输出序列为p1,p2,p3,pn，若p1=n，则pi是：（ c ） a. i b. n-i c. n-i+1 d. 不确定,3.4.1 队列的概念一、什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表。,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,能进行插入的一端称为队尾，能进行删除的一端称为队头。 称插入操作为入队，删除操作为出队。,3.4 队列,a1 a2 a3 an,队头,队尾,出队列,队列的示意图,队列的特点“先进先出”,第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素,入队列,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，否则返回False。,3.4 队列,3.4.2 循环队列队列的顺序存储和实现一、队列的顺序存储结构,#define MAXSIZE 100 /最大队列长度typedef struct ElemType * base; /初始化时分配存储空间的基址 int front; /队头指针，指向队头元素 int rear; /队尾指针，指向队尾元素的下一个位置SqQueue;,队头,队尾指针是用整型实现的,3.4 队列,(a)空队列,(b)J1,J2和J3相继入队列,(c)J1和J2相继出队,(d)J4,J5和J6相继入队之后,J3出队,Q.front,Q.rear均为整数用箭头指示只是为了直观,3.4 队列,3.4 队列,队列基本操作,队空,J1,J2,J3,J4,J5,J6入队,设两个指针：front,rear。rear指向队尾元素的下一个位置；front指向队头元素。初值 front=rear=0,队空条件：front=rear 入队列：Q.base rear+ = e; 出队列：e =Q.base front+ ;,Q.base,3.4 队列,存在问题设数组大小为M，则：当front=0，rear= M 时，再入队发生溢出真溢出当front0，rear= M 时，再入队发生溢出假溢出解决方案队首固定，每次出队后将剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让 Q.baseM-1 接在 Q.base0 之后，若rear+1=M，则令rear=0;,rear,J4,J5,J6入队,J4,J5,J6,front,3.4 队列,实现：利用“模”运算入队：Q.baserear=e; rear=(rear+1)%M; 出队：e=Q.basefront; front=(front+1)%M; 队满、队空判定条件?,J7,J9,J8,队空：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,队满：front=rear,3.4 队列,队满：front=(rear+1)%M,少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,队空：front=rear,J7,J8,1）初始化操作 InitQueue_Sq ( SqQueue /InitQueue_Sq,二、循环队列的基本操作算法,3.4 队列,2）入队操作 EnQueue_Sq ( SqQueue &Q, ElemType e )功能：将元素 e 插入队尾,元素e入队前,元素e入队后,3.4 队列,入队操作算法： Status EnQueue_Sq ( SqQueue /EnQueue_Sq,3.4 队列,3)出队操作 DeQueue_Sq (SqQueue &Q, QElemType &e )功能：删除队头元素，用e返回其值,出队操作前,出队操作后,3.4 队列,出队操作算法 ：Status DeQueue_Sq ( SqQueue /EnQueue_Sq,3.4 队列,20080312(3),栈,1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。2、栈的元素具有后进先出的特点。3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针。,顺序栈的图示,S.stacksizeS.topS.base,100,1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示；4、入队操作要修改队尾指针，出队操作要修改队头指针。,队列,队列,少用一个元素空间：队头指针就无法追上队尾指针了队空：front = = rear队满：(rear+1)%M = = front,3.4.3 链队列队列的链式存储结构和实现一、链队列,3.4 队列,二、链队列的类型定义,typedef struct QNode /链队列结点的类型定义 ElemType data; struct QNode * next;QNode, * QueuePtr;,3.4 队列,typedef struct / 链队列的表头结点的类型定义 QueuePtr front; /队头指针，指向链表的头结点 QueuePtr rear; /队尾指针，指向队尾结点LinkQueue;,头结点,.,front,队头,队尾,rear,front指向头结点，rear指向队尾,3.4 队列,链式队列的基本操作,判断队空的条件：front=rear,三、队列的应用,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。,3.4 队列,栈和队列练习,1、已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列：A）1234 B）4321 C）2143 D）4123答案：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,栈和队列,问题：编程判断一个字符序列是否是回文（回文是指一个字符序列以中间字符为基准两边字符完全相同）。算法设计 程序从键盘接受一个字符序列存入字符串str中，字符串长度80，输入字符序列以回车符为结束标记，字符串str中不包括回车换行符。 将字符串中字符逐个分别存入队列和栈，然后逐个出队和退栈，比较出队的元素和退栈的元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。,栈和队列,#include stdio.h#de