数据结构-PPT第三章-栈和队列

1、 通常称，栈和队列是限定通常称，栈和队列是限定插入和删除插入和删除只只能在表的能在表的“端点端点”进行的线性表。进行的线性表。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型第三章 栈和队列3.1 栈栈3.2 栈的应用举例栈的应用举例3.4 队列队列学习提要：学习提要：1.1.掌握栈和队列这两种抽象数据类型的特点，掌握栈和队列这两种抽象数据类型的特点， 并能在

2、相应的应用问题中正确选用它们。并能在相应的应用问题中正确选用它们。2.2.熟练掌握栈类型的两种实现方法，即两种存熟练掌握栈类型的两种实现方法，即两种存 储结构表示时的基本操作实现算法，特别应储结构表示时的基本操作实现算法，特别应 注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.3.熟练掌握循环队列和链队列的基本操作实现熟练掌握循环队列和链队列的基本操作实现 算法，特别注意队满和队空的描述方法。算法，特别注意队满和队空的描述方法。重难点内容：重难点内容： 顺序栈的相关操作、循环队列的判空判满顺序栈的相关操作、循环队列的判空判满3.1 栈（栈（stack）3.1

3、.1 栈的类型定义栈的类型定义3.1.2 栈的表示和实现栈的表示和实现栈的定义和特点栈的定义和特点v定义：限定仅在定义：限定仅在表尾表尾进行插入或删除操进行插入或删除操作的线性表，表尾作的线性表，表尾栈顶栈顶，表头，表头栈底栈底，不含元素的空表称不含元素的空表称空栈空栈。ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)v特点：先进后出（特点：先进后出（FILO）或后进先出）或后进先出（LIFO）3.1.1 栈的类型定义 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1,

4、aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack 栈的类型定义栈的类型定义InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()顺序栈顺序栈3.1.2 栈的表示和实现栈的表示和实现 类似于线性表的顺序映象实现，类似于线性表的顺序映象实现，指向表尾的指针可以作为指向表尾的指针可以作为栈顶指针栈顶指针。/- 栈的顺序存储表示栈的顺序存储表示 -

5、 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;利用数组静态分配定义：利用数组静态分配定义：Typedef struct stackSelemType stackmaxsize;int top; /top=-1空栈空栈top=maxsize-1满满顺序栈示意图顺序栈示意图*base*topstacksize.a1.aian*base*topstacksize初始初始空空栈栈*top = *

6、base; stacksize = STACK_INIT_SIZE顺序栈顺序栈dcba实现：一维数组实现：一维数组sMtop123450进栈进栈A栈满栈满BCDEF设数组维数为设数组维数为M Mtop=base,top=base,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)underflow)top=M,top=M,栈满，此时入栈，则栈满，此时入栈，则上上溢溢（overflow)overflow)toptoptoptoptop123450空栈空栈topbasebasetop出栈出栈toptop栈空栈空base栈底指针栈底指针base,base,始终始终指向栈底位置；指向栈

7、底位置；栈顶栈顶指针指针top,top,其初值指向其初值指向栈底，始终在栈顶元栈底，始终在栈顶元素的下一个位置素的下一个位置123450ABtop=实现：一维数组实现：一维数组sM Status InitStack (SqStack &S)/ 构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (

8、SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; Status Pop (S

9、qStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;*S.top+ = ee = *-S.top 0M-1栈栈1底底栈栈1顶顶栈栈2底底栈栈2顶顶在一个程序中同时使用两个栈在一个程序中同时使用两个栈链栈链栈 栈的链式存储结构。栈顶指针就是栈的链式存储结构。栈顶指针就是链表的头指针。链表的头指针。栈顶指针a1an注意注意: 链栈中链栈中指针的方向指针的方向an-1注意：注意：链栈中的指针方向链栈

10、中的指针方向v 入栈操作入栈操作v 出栈操作出栈操作 .栈底栈底toptopxptop .栈底栈底topqp-next=s-top ; s-top=p q=s-top ; s-top=s-top-next 链栈存储表示及入栈、出栈操作链栈存储表示及入栈、出栈操作Typedef struct Lnode SelemType data; struct Lnode *next;Lnode,*Linkstack;Status push(Linkstack &S,SelemType e) p=(Linkstack)malloc(sizeof(LNode); p-data=e; p-next=S-next

11、;S-next=p;Status pop(Linkstack &S,SelemType &e) if(!S-next)return ERROR; p=S-next;S-next=p-next; e=p-data;free(p); return OK;3.2 栈的应用栈的应用3.2.1 数制转换数制转换3.2.2 括号匹配的检验括号匹配的检验3.2.3 行编辑程序问题行编辑程序问题3.2.4 迷宫求解迷宫求解3.2.5 表达式求值表达式求值3.2.1 数制转换数制转换十进制十进制N和其他和其他d进制数的转换原进制数的转换原理理: N=( N div d )*d + N mod d 其中：其中：d

12、iv为为整除整除运算，运算，mod为为求余求余运算运算toptop4top40top405 例如：例如： (1348)10=(2504)8，其运算过程如下：，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序top4052 void conversion( ) initstack(S); scanf (“%d”,N); while(N) push(S，N%8); N=N/8; while(! Stackempty(s) pop(S,e); printf(“%d”,e); /conversion#define S

13、TACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 0typedef struct int *base; int *top; int stacksize;sqstack;栈使用的完整C程序实例int initstack(sqstackint initstack(sqstack * *s)s) s-base=(int s-base=(int * *)malloc)malloc (STACK_INIT_SIZE (STACK_INIT_SIZE* *sizeof(intsiz

14、eof(int);); s-top=s-base; s-top=s-base; s-stacksize=STACK_INIT_SIZE; s-stacksize=STACK_INIT_SIZE; return OK; return OK; void pop(sqstack void pop(sqstack * *s,ints,int * *e)e) if(s-top=s-base)return ERROR; if(s-top=s-base)return ERROR; * *e=e=* *(-s-top);(-s-top); void push(sqstack void push(sqstack

15、 * *s,ints,int e) e) if(s-top if(s-top- -s-base=s-stacksize)s-base=s-stacksize) s-base=(int s-base=(int* *)realloc(s-base,(s- )realloc(s-base,(s- stacksize+STACKINCREMENT)stacksize+STACKINCREMENT)* *sizeof(intsizeof(int);); if (!s-base)exit(OVERFLOW); if (!s-base)exit(OVERFLOW); s-top=s-base+s-stack

16、size; s-top=s-base+s-stacksize; s-stacksize+=STACKINCREMENT; s-stacksize+=STACKINCREMENT; * *(s-top+)=e;(s-top+)=e; main()() sqstack sqstack s; s; int n,m,e; n,m,e; initstack(&s initstack(&s);); clrscr clrscr(); /(); /清屏幕清屏幕 scanf(“%d(“%d %d”,&n,&m);/n %d”,&n,&m);/n为输入为输入数，数，m m为基数为基数 while(n) push(

17、&s,n%m);n=n/m; (n) push(&s,n%m);n=n/m; while(!(s.top=s.base)(!(s.top=s.base) pop(&s,&e); pop(&s,&e); printf(%d,e(%d,e); ); 3.3.2 括号匹配的检验括号匹配的检验 则则 检验括号是否匹配检验括号是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。假设在表达式中假设在表达式中（）或（）或（ ）等为正确的格式，等为正确的格式，（ ）或（）或（ ）或）或 （）（）)均均为不正确的格式。为不正确的格式。分析可能出现的分析可能出现的不匹配不匹

18、配的情况的情况: :到来的括弧到来的括弧并非是所并非是所“期待期待”的；的；例如：例如：考虑下列括号序列：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括弧。的括弧。算法的设计思想：算法的设计思想：1）凡出现）凡出现左括左括号号，则，则进栈进栈；2）凡出现）凡出现右括右括号号，首先检查栈是否空，首先检查栈是否空 若若栈空栈空，则表明该，则表明该“右括右括号号”多余多余， 否则否则和栈顶元素和栈顶元素比较，比较， 若若相匹配相匹配，则，则“左括左括号号出栈出栈” ， 否则表明否则表明不匹配不匹配。3）表达式检验结束时，）表达式

19、检验结束时， 若若栈空栈空，则表明表达式中，则表明表达式中匹配正确匹配正确， 否则表明否则表明“左括左括号号”有有多多余余。Status matching(string& exp) int state = 1; while (i - * / ( # =Precede: 判定运算符栈的栈顶运算符判定运算符栈的栈顶运算符1 1与读入的运算与读入的运算符符2 2之间的优先关系的函数。之间的优先关系的函数。Operate: 进行二元运算进行二元运算abab的函数的函数. .例：例：3 * ( 7 2 )OPND栈栈OPTR栈栈CCC3*(C7CC2C275C*5315例：例：3 * ( 7 2 ) O

20、PTR栈栈 OPND栈栈 输入输入 操作操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 * ( 7 2 ) # PUSH( OPTR, * )3 # * 3 ( 7 2 ) # PUSH( OPTR, ( )4 # * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate

21、( 3, *, 5 )10 # 15 # return GetTop( OPND )OperandType EvaluateExpression() / 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是运算符则进栈 else / while return GetTop(OPND);

22、/ EvaluateExpression switch ( precede(GetTop(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch*3.3 栈与递归的实现栈与递归的实现将所有的实在参数、返回地址将所有的实在参数、返回地址等等信息信息传递给被调用函数传递给被调用函数保存保存；为被调用函数的局部变量为被调用函数的局部变量分配分配存储区存储区；将将控制转移控制转移到被调用函数的入到被调用函数的入

23、口。口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：保存保存被调函数的被调函数的计算结果计算结果；释放释放被调函数的被调函数的数据区数据区；依照被调函数保存的返回地依照被调函数保存的返回地址将址将控制转移控制转移到调用函数。到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 递归

24、工作栈：递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：当前活动记录：栈顶记录指示当前层的 执行情况。当前环境指针：当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数同一函数进行嵌套调用，例如：void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从x移到z3 else 4 hanoi(n-1, x,

25、z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔5 move(x, n, z); / 将编号为n的圆盘从x移到z6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔7 8 8 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char z)1 2 if (n=1)3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y,

26、x, z); 8 9 执行函数执行函数hanoi(3,a,b,c) 例：汉诺塔问题：例：汉诺塔问题：将将x柱子上的盘移到柱子上的盘移到 z柱，用柱，用 y柱放临时盘柱放临时盘 要求：一次只能移动一个盘，大盘不可放于小盘上要求：一次只能移动一个盘，大盘不可放于小盘上。xyzhanoi塔问题:栈的递归实现3.4 队列队列3.4.1 队列的类型定义队列的类型定义3.4.2 链队列链队列3.4.3 循环队列循环队列队列队列是限定只能在表的一端进行插入，在是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。表的另一端进行删除的线性表。a1 a2 a3.an 入队入队出队出队frontrear队列

27、队列Q=(a1,a2,an)v队列特点：先进先出队列特点：先进先出( (FIFOFIFO) )3.4.1 队列的类型定义队列的类型定义v队尾队尾(rear)允许允许插入插入的一端的一端v队头队头(front)允许允许删除删除的一端的一端 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中约定其中a1 端为端为队列头队列头， an 端为端为队列尾队列尾基本操作：基本操作：队列的类型定义 ADT Queue队列的基本操作：队列的基本操作： InitQueue(&Q)

28、DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()typedef struct QNode/ 结点类型结点类型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /链队列类型链队列类型 QueuePtr front ; /队头指针 QueuePtr rear ; /队尾指针 LinkQueue;3.4.2 链队

29、列队列的链式表示和实现链队列队列的链式表示和实现a1anQ.frontQ.rearQ.frontQ.rear空队列空队列frontrearx入入队队xfrontreary入入队队xyfrontrearx出出队队xyfrontrear空空队队front reary出出队队Q.rear - next=pQ.rear=pp= Q.front - nextQ.front - next = p - next Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!

30、Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElem

31、Type &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;3.4.3 循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现 #define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存

32、储空间 int front; / 头指针，若队列不空， /指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;实现：用一维数组实现实现：用一维数组实现sqM123450空队列空队列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J1,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfrontv存在问题：存在问题：l当当front=0,rear=M时再有元素入队发生溢出时再有元素入队发生溢出

33、真溢出真溢出l当当front0,rear=M时再有元素入队发生溢出时再有元素入队发生溢出假溢出假溢出rearv解决方案解决方案l队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪浪费时间费时间l循环队列循环队列u 基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让sq0接接在在sqM-1 之后，若之后，若rear+1=M,则令则令rear=0;u实现：利用实现：利用“模模”运算运算u入队：入队： baserear=x; rear=(rear+1)%M; u出队：出队： x=basefront; front=(front+1)%M; u队满、队空判定条件队满、队空判定条件012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=rear解