第3章栈和队列

1、13.1 3.1 栈栈 3.2 3.2 队列队列 第第3章章 栈和队列栈和队列 2栈和队列的特点栈和队列的特点u两者的逻辑结构与线性表相同，但是两者的逻辑结构与线性表相同，但是插入插入和删除操作受到了限制和删除操作受到了限制；u栈只允许在线性表的一端进行插入和删除栈只允许在线性表的一端进行插入和删除操作，队列则允许在一端插入另一端删除；操作，队列则允许在一端插入另一端删除；u栈按照栈按照“后进先出后进先出”的规则进行操作，队的规则进行操作，队列则按照列则按照“先进先出先进先出”的规则进行。的规则进行。33.1.1 3.1.1 栈的定义栈的定义 3.1.2 3.1.2 顺序存储结构及其基本运算实

2、现顺序存储结构及其基本运算实现3.1.3 3.1.3 链式存储结构及其基本运算实现链式存储结构及其基本运算实现3.1.4 3.1.4 栈的应用举例栈的应用举例3.1 栈栈4 栈是一种只能在一端进行插入或删除操作的线性表。栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为表中允许进行插入、删除操作的一端称为栈顶。栈顶。 当栈中没有数据元素时，称为当栈中没有数据元素时，称为空栈。空栈。3.1.1 栈的定义栈的定义a1a2a3an栈顶栈顶 top栈底栈底 bottom入栈入栈出栈出栈5练练 习习 1 依次输入依次输入3个元素个元素A、B、C到栈中，可到栈中，可得到哪

3、几种不同的输出？得到哪几种不同的输出？ 解：共解：共5种种(1) A,B,C(2) A,C,B(3) B,A,C(4) B,C,A(5) C,B,A6 设一个栈的输入序列为设一个栈的输入序列为A、B、C、D,则借助一则借助一个栈所得到的输出序列不可能是个栈所得到的输出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C练练 习习 2答案：答案：D7栈的抽象数据类型栈的抽象数据类型 ADT Stack数据对象：数据对象：D=ai|1in,n0，ai 为为ElemType类型类型 数据关系：数据关系：R=| ai ，ai+1 D ，i=1,.,

4、n-1基本运算基本运算: InitStack(&s) /初始化栈：构造一个空栈初始化栈：构造一个空栈s DestroyStack(&s) /销毁栈：释放栈销毁栈：释放栈s占用的存储空间占用的存储空间 StackEmpty(s) /判断栈是否为空判断栈是否为空 Push(&S,e) /进栈：将元素进栈：将元素e插入到栈插入到栈s中作为栈顶元素中作为栈顶元素 Pop(&s,&e) /出栈：从栈出栈：从栈s中退出栈顶元素，并将其值赋给中退出栈顶元素，并将其值赋给e GetTop(s,&e) /取栈顶元素：返回当前的栈顶元素，并将其值赋给取栈顶元素：返回

5、当前的栈顶元素，并将其值赋给eADT Stack8a1a2an Push(&S, e)初始条件初始条件：栈栈 S 已存在已存在操作结果操作结果：插入插入e为新的栈顶元素为新的栈顶元素e9a1a2an-1 Pop(&S,&e)初始条件初始条件：栈栈 S 存在且非空存在且非空操作结果操作结果：删除删除S 的栈顶元素，赋值给的栈顶元素，赋值给ean10a1a2an GetTop(S,&e)初始条件初始条件：栈栈 S 已存在且非空已存在且非空操作结果操作结果：返回返回 S 的栈顶元素，赋值给的栈顶元素，赋值给e11 利用一组地址利用一组地址连续的连续的存储单元依次存放存

6、储单元依次存放自自栈底到栈顶栈底到栈顶的数据元素；的数据元素； 在数组上实现时，在数组上实现时，栈底栈底位置可以设置在数位置可以设置在数组的任一个端点（通常设置在组的任一个端点（通常设置在0下标处），而下标处），而栈顶栈顶是随着插入和删除而变化的，可以用一是随着插入和删除而变化的，可以用一个整形变量个整形变量top指示栈顶元素在顺序栈中的位指示栈顶元素在顺序栈中的位置；置； 数据入栈或出栈时，整形变量数据入栈或出栈时，整形变量 top分别执分别执行行加加1或或减减1的操作。的操作。3.1.2 顺序存储结构及其基本运算实现顺序存储结构及其基本运算实现12顺序栈进栈和出栈示意图顺序栈进栈和出栈示意

7、图13顺序栈的类型定义顺序栈的类型定义typedef struct ElemType dataMaxSize； int top；/*栈顶指针栈顶指针*/ SqStack； 采用采用栈指针栈指针的方式建立和使用顺序表的方式建立和使用顺序表SqStack *s；14 (1) 初始化栈初始化栈InitStack(s) 建立一个新的空栈建立一个新的空栈s s，实际上是将栈顶指针指，实际上是将栈顶指针指向向-1-1即可。即可。 void InitStack(SqStack *&s) s=(SqStack *)malloc(sizeof(SqStack); s-top=-1; 在顺序栈中实现栈的基

8、本运算在顺序栈中实现栈的基本运算15 (2) 销毁栈销毁栈DestroyStack(s) 释放栈释放栈s占用的存储空间。占用的存储空间。 void DestroyStack(SqStack *&s) free(s); 16 (3) 判断栈是否为空判断栈是否为空StackEmpty(s) 栈栈S为空的条件是为空的条件是s-top=-1。 bool StackEmpty(SqStack *s) return(s-top=-1); 17 (4) 进栈进栈Push(s,e) 在栈不满的条件下，先将栈顶指针增在栈不满的条件下，先将栈顶指针增1，然，然后在该位置上插入元素后在该位置上插入元素e。

9、bool Push(SqStack *&s,ElemType e) if (s-top=MaxSize-1) return false;/*栈满的情况，即栈向上溢出栈满的情况，即栈向上溢出*/s-top+; s-datas-top=e;return true; 18 (5) 出栈出栈Pop(s,e) 在栈不为空的条件下，先将栈顶元素赋给在栈不为空的条件下，先将栈顶元素赋给e，然后将栈顶指针减，然后将栈顶指针减1。 bool Pop(SqStack *&s,ElemType &e) if (s-top=-1) return false; /*栈为空的情况，即栈向下溢出栈为

10、空的情况，即栈向下溢出*/e=s-datas-top;s-top-;return true; 19 (6) 取栈顶元素取栈顶元素GetTop(s,e) 在栈不为空的条件下，将栈顶元素赋给在栈不为空的条件下，将栈顶元素赋给e。 bool GetTop(SqStack *s,ElemType &e) if (s-top=-1) return false; /*栈为空的情况，即栈向下溢出栈为空的情况，即栈向下溢出*/e=s-datas-top;return true; 20 (7) 显示栈中元素显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。从栈顶到栈底顺序显示栈中所

11、有元素。 void DispStack(SqStack *s) int i;for (i=s-top;i=0;i-) printf(%c ,s-datai);printf(n); 21例例3.4 编写一个算法利用顺序栈判断一个字符串是否是对编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的称串。所谓对称串是指从左向右读和从右向左读的序列相同。序列相同。 【算法思想算法思想】对于字符串对于字符串str,先将其所有元素进栈，先将其所有元素进栈，然后从头扫描然后从头扫描str，并弹出栈顶元素，将两者进行，并弹出栈顶元素，将两者进行比较，若不相同则返回比较，若不相

12、同则返回false。当。当str扫描完毕时返回扫描完毕时返回true。 实际上，从头开始扫描实际上，从头开始扫描str是从左向右读，出栈是是从左向右读，出栈是从右向左读，两者相等说明该串是对称串。从右向左读，两者相等说明该串是对称串。22bool symmetry(ElemType str)int i;ElemType e;SqStack *st;InitStack(st);for (i=0;stri!=0;i+)/将串所有元素进栈将串所有元素进栈Push(st, stri);for (i=0;stri!=0;i+)Pop(st,e);/退栈元素退栈元素eif (stri!=e)/若若e与当前

13、串元素不同则不是对称串与当前串元素不同则不是对称串DestroyStack(st);return false;DestroyStack(st);return true;23 采用链式存储的栈称为采用链式存储的栈称为链栈链栈，这里采用单链表，这里采用单链表实现实现 链栈的优点？链栈的优点？ 入栈出栈操作在哪一端进行？入栈出栈操作在哪一端进行？ 下图中，栈中元素自栈顶到栈底依次是下图中，栈中元素自栈顶到栈底依次是a1、a2、an3.1.3 链式存储结构及其基本运算的实现链式存储结构及其基本运算的实现不存在栈满上溢的情况不存在栈满上溢的情况单链表的表头单链表的表头24 链栈中数据结点的类型链栈中数据

14、结点的类型LiStack定义定义如下如下: typedef struct linknode ElemType data;/*数据域数据域*/ struct linknode *next;/*指针域指针域*/ LiStack;25 (1) 初始化栈初始化栈InitStack(s) 建立一个空栈建立一个空栈s。实际上是创建链栈的头结。实际上是创建链栈的头结点，并将其点，并将其next域置为域置为NULL。 void InitStack(LiStack *&s) s=(LiStack *)malloc(sizeof(LiStack);s-next=NULL; 在链栈中实现栈的基本运算在链栈中

15、实现栈的基本运算26 (2) 销毁栈销毁栈DestroyStack(s) 释放栈释放栈s s占用的全部存储空间。占用的全部存储空间。 void DestroyStack(LiStack *&s) LiStack *p=s，*q=s-next; while (q!=NULL) free(p);p=q;q=p-next; free(p); 27 ( (3) 求栈的长度求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表，用从第一个数据结点开始扫描单链表，用i记录访问的记录访问的数据结点个数，最后返回数据结点个数，最后返回i值。值。 int StackLength(LiSt

16、ack *s) int i=0;LiStack *p=s-next;while (p!=NULL) i+; p=p-next; return(i); 28 (4) 判断栈是否为空判断栈是否为空StackEmpty(s) 栈栈s为空的条件是为空的条件是s-next=NULL，即单链，即单链表中没有数据结点。表中没有数据结点。 bool StackEmpty(LiStack *s) return(s-next=NULL); 29 (5) 进栈进栈Push(s,e) 将新数据结点插入到头结点之后。将新数据结点插入到头结点之后。 void Push(LiStack *&s,ElemType e

17、) LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;p-next=s-next; /*插入插入*p作为第一个数据结点作为第一个数据结点*/ s-next=p; 30 (6) 出栈出栈Pop(s,e) 在栈不为空的条件下，将头结点的指针域所指数在栈不为空的条件下，将头结点的指针域所指数据结点的数据域赋给据结点的数据域赋给e，然后将该数据结点删除。，然后将该数据结点删除。 bool Pop(LiStack *&s,ElemType &e) LiStack *p;if (s-next=NULL) return false

18、; /*栈空的情况栈空的情况*/p=s-next;/*p指向第一个数据结点指向第一个数据结点*/e=p-data;s-next=p-next;free(p);return true; 31 (7) 取栈顶元素取栈顶元素GetTop(s,e) 在栈不为空的条件下，将头结点的指针域所指数在栈不为空的条件下，将头结点的指针域所指数据结点的数据域赋给据结点的数据域赋给e。 bool GetTop(LiStack *s,ElemType &e) if (s-next=NULL) return false; /*栈空的情况栈空的情况*/e=s-next-data;return true; 32 (

19、8) 显示栈中元素显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表，并输出当前访从第一个数据结点开始扫描单链表，并输出当前访问结点的数据域值。问结点的数据域值。 void DispStack(LiStack *s) LiStack *p=s-next; while (p!=NULL) printf(%d ,p-data);p=p-next; printf(n); 33 例例3.5 编写一个算法判断输入的表达式中括编写一个算法判断输入的表达式中括号是否号是否配对（假设只含有左、右圆括号）。配对（假设只含有左、右圆括号）。 解解: 设置一个栈设置一个栈st，扫描表达式，扫描表达

20、式exp，遇到左括，遇到左括号时进栈；遇到右括号时：若栈顶为左括号，则出号时进栈；遇到右括号时：若栈顶为左括号，则出栈，否则，返回栈，否则，返回0。 当表达式扫描完毕，栈为空时返回当表达式扫描完毕，栈为空时返回1，表示括号，表示括号正确匹配，否则返回正确匹配，否则返回0。34 int Match(char exp,int n)int i=0;char e;SqStack *st;InitStack(st);while (in)if (expi=()/当前字符为左括号当前字符为左括号,将其进栈将其进栈Push(st,expi);else if (expi=)/当前字符为右括号当前字符为右括号if

21、 (GetTop(st,e)=1) if (e!=() return(0); /括号不匹配时返回括号不匹配时返回0 else Pop(st,e); /将栈顶元素出栈将栈顶元素出栈else return(0);/取栈元素下溢出时返回取栈元素下溢出时返回0i+;/继续处理其他字符继续处理其他字符if (StackEmpty(st)=1) return(1);else return(0);353.2 队队 列列 3.2.1 队列的定义队列的定义 3.2.2 顺序存储结构及其基本运算的实现顺序存储结构及其基本运算的实现 3.2.3 链式存储结构及其基本运算的实现链式存储结构及其基本运算的实现3.2.4

22、 队列的应用举例队列的应用举例 36队列：队列：仅允许在表的一端进行插入，而在表的另仅允许在表的一端进行插入，而在表的另一端进行删除。一端进行删除。队尾队尾(rear)：进行插入的一端：进行插入的一端队首队首(front)：进行删除的一端：进行删除的一端向队列中插入新元素称为向队列中插入新元素称为进队进队或或入队入队，新元素进，新元素进队后就成为新的队尾元素；队后就成为新的队尾元素；从队列中删除元素称为从队列中删除元素称为出队出队或或离队离队，元素出队后，元素出队后，其后继元素就成为队首元素。其后继元素就成为队首元素。 3.2.1 队列的定义队列的定义 出队出队入队入队队首队首a1a2a3an

23、-1队尾队尾37队列的抽象数据类型队列的抽象数据类型 ADT List数据对象：数据对象：D=ai|1in,n0，ai 为为ElemType类型类型 数据关系：数据关系：R=| ai , ai+1 D ，i=1,.,n-1基本运算：基本运算： InitQueue(&q)：初始化队列：初始化队列DestroyQueue(&q)：销毁队列：销毁队列QueueEmpty(q)：判断队列是否为空判断队列是否为空enQueue(&q,e)：入队列，将元素入队列，将元素e入队作为队尾元素入队作为队尾元素deQueue(&q,&e)：出队列，从队列出队列，从队列q中出

24、队一个元素，中出队一个元素，赋给赋给e ADT List383.2.2 顺序存储结构及其基本运算的实现顺序存储结构及其基本运算的实现 用数组实现队列用数组实现队列typedef struct ElemType dataMaxSize； int front,rear；/*队首和队尾指针队首和队尾指针*/ SqQueue；012n-2n-1a1a2a3.an-1anfrontrear39 存在的问题存在的问题1 队空时，队头和队尾指针都为队空时，队头和队尾指针都为-1。 此时若进行入队操作，队头和队尾指针都增此时若进行入队操作，队头和队尾指针都增1，再将新数，再将新数据元素放入该位置。据元素放入该

25、位置。 用这种方法设置队头、队尾指针位置，在进行入队操作用这种方法设置队头、队尾指针位置，在进行入队操作时，时，空队与非空队需要执行的操作不完全一样空队与非空队需要执行的操作不完全一样。 解决方法：解决方法：让队头指针指向队列真正队头元素的让队头指针指向队列真正队头元素的前前一个位置一个位置。队列的顺序存储结构队列的顺序存储结构012.n-2n-1front=rear =-140u队头指针队头指针front指向队头元素的前一个位置指向队头元素的前一个位置u队尾指针队尾指针rear指向队尾元素指向队尾元素u空队时：空队时：front=rear=-1u入队原则：队尾指针入队原则：队尾指针rear

26、= rear + 1，再将新元素，再将新元素按按 rear 指示位置加入指示位置加入u出队原则：队头指针出队原则：队头指针front = front + 1，再将下标，再将下标为为 front 的元素取出的元素取出u队中元素的个数：队中元素的个数：m=rear-front012n-2n-1a1a2a3.an-1anfrontrear41队列的入队和出队操作示意图队列的入队和出队操作示意图队中元素的个数：队中元素的个数：m=rear-frontfront=rear=-1rear = rear + 1front = front + 1 思考：能不能用思考：能不能用rear=MaxSize-1作为队

27、满的条件？作为队满的条件？ 显然不能，在图显然不能，在图(d)中，队列为空，但仍满足该条件。中，队列为空，但仍满足该条件。 这时入队，出现这时入队，出现“假溢出假溢出”-问题问题242 为了能够充分地使用数组中的存储空间，把数组为了能够充分地使用数组中的存储空间，把数组的前端和后端连接起来，形成一个的前端和后端连接起来，形成一个环形的顺序表环形的顺序表，称为称为循环队列。循环队列。入队：入队： rear = (rear + 1)% MAXSIZE出队：出队： front= (front + 1)% MAXSIZE元素个数：元素个数：m=(rear-front+MAXSIZE)% MAXSIZE

28、循环队列循环队列(b)a,b,c 入队入队 rear 0 1 2 3 4 front a b c 43用数组实现队列存在的问题用数组实现队列存在的问题3front=4,rear=8有有4个元素个元素front=4,rear=4队列满队列满front=8,rear=8队空队空front=4,rear=3少用一个元素空少用一个元素空间时的队列满间时的队列满44怎样区分这两者之间的差别呢怎样区分这两者之间的差别呢?在入队时在入队时少用一个数据元素空间少用一个数据元素空间，以队尾指针加，以队尾指针加1等等于队首指针判断队满，即于队首指针判断队满，即队满条件队满条件为为: (rear+1) % MaxS

29、ize=front队空条件队空条件仍为仍为: rear=front45typedef struct datatype dataMAXSIZE; /*数据的存储区数据的存储区*/ int front,rear; /*队头队尾指针队头队尾指针*/ int num; /*队中元素的个数队中元素的个数*/c_SeQueue; /*循环队循环队*/设置计数器设置计数器46 (1) 初始化队列初始化队列InitQueue(q) 构造一个空队列构造一个空队列q。将。将front和和rear指针均设置指针均设置成初始状态即成初始状态即0值。值。 void InitQueue(SqQueue *&q)

30、q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0; 47 (2) 销毁队列销毁队列DestroyQueue(q) 释放队列释放队列q占用的存储空间。占用的存储空间。 void DestroyQueue(SqQueue *&q) free(q); 48 (3) 判断队列是否为空判断队列是否为空QueueEmpty(q) 若队列若队列q满足满足q-front=q-rear条件，则条件，则返回返回true；否则返回；否则返回false。 bool QueueEmpty(SqQueue *q) return(q-front=q-rear

31、); 49 (4) 进队列进队列enQueue(q,e) 在队列不满的条件下，先将队尾指针在队列不满的条件下，先将队尾指针rear循环增循环增1，然后将元素添加到该位置。然后将元素添加到该位置。 bool enQueue(SqQueue *&q,ElemType e) if (q-rear+1)%MaxSize=q-front) /*队满队满*/return false;q-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;return true; 50 (5) 出队列出队列deQueue(q,e) 在队列在队列q不为空的条件下，将队首指针不为空的条件下，将

32、队首指针front循环循环增增1，并将该位置的元素值赋给，并将该位置的元素值赋给e。 bool deQueue(SqQueue *&q,ElemType &e) if (q-front=q-rear) /*队空队空*/return false;q-front=(q-front+1)%MaxSize;e=q-dataq-front;return true; 51 链队组成链队组成: (1) 存储队列元素的单链表存储队列元素的单链表 (2) 存储队头和队尾指针的链队存储队头和队尾指针的链队头结点头结点 3.2.3 链式存储结构及其基本运算的实现链式存储结构及其基本运算的实现rear

33、fronta1ana2a352 front rear q (a)(a)链队初态链队初态 front rear q (b)(b)入队入队 3 3 个元素个元素 a b c front rear q (c)(c)出队出队 1 1 个元素个元素 b c 链列的入队和出队操作示意图链列的入队和出队操作示意图53单链表中数据结点类型单链表中数据结点类型QNode定义如下定义如下: typedef struct qnode ElemType data;/*数据元素数据元素*/struct qnode *next; QNode;链队中头结点类型链队中头结点类型LiQueue定义如下定义如下: typedef

34、 struct QNode *front; /*指向单链表队头结点指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点指向单链表队尾结点*/ LiQueue; 54 (1) 初始化队列初始化队列InitQueue(q) 构造一个空队列，即只创建一个链队头结构造一个空队列，即只创建一个链队头结点，其点，其front和和rear域均置为域均置为NULL，不创建数，不创建数据元素结点。据元素结点。 void InitQueue(LiQueue *&q) q=(LiQueue *)malloc(sizeof(LiQueue); q-front=q-rear=NULL; 55

35、 (2) 销毁队列销毁队列DestroyQueue(q) 释放队列占用的存储空间，包括释放队列占用的存储空间，包括链队头结点链队头结点和和所所有数据结点有数据结点的存储空间。的存储空间。 void DestroyQueue(LiQueue *&q) QNode *p=q-front,*r;if (p!=NULL) /*释放数据结点占用空间释放数据结点占用空间*/ r=p-next; while (r!=NULL) free(p); p=r; r=p-next; /*p和和r指针同步后移指针同步后移*/ free(p);free(q);/*释放链队头结点占用空间释放链队头结点占用空间*/

36、 56 (3) 判断队列是否为空判断队列是否为空QueueEmpty(q) 若链队结点的若链队结点的rear域值为域值为NULL，表示队列为空，表示队列为空，返回返回true；否则返回；否则返回false。 bool QueueEmpty(LiQueue *q) return(q-rear=NULL); 57 (4) 进队列进队列enQueue(q,e) 创建创建data域为域为e的数据结点的数据结点*s。若原队列为空，则将链队。若原队列为空，则将链队结点的两个域均指向结点的两个域均指向*s结点，否则，将结点，否则，将*s链到单链表的末尾，链到单链表的末尾，并让链队结点的并让链队结点的rear

37、域指向它。域指向它。 void enQueue(LiQueue *&q,ElemType e) QNode *p; p=(QNode *) malloc(sizeof(QNode);p-data=e;p-next=NULL; if (q-rear=NULL) /*若原链队为空若原链队为空,新结点是队首结点又是队尾结点新结点是队首结点又是队尾结点*/ q-front=q-rear=p;else q-rear-next=p; /*将将*s结点链到队尾结点链到队尾,rear指向它指向它*/ q-rear=p; 58 (5) 出队列出队列deQueue(q,e) 若原队列不为空，则将第一个数据

38、结点的若原队列不为空，则将第一个数据结点的data域值赋给域值赋给e，并删除之。若出队之前队列中只有一个结点，则需将链队结并删除之。若出队之前队列中只有一个结点，则需将链队结点的两个域均置为点的两个域均置为NULL，表示队列已为空。，表示队列已为空。 bool deQueue(LiQueue *&q,ElemType &e) QNode *t;if (q-rear=NULL) return false; /*队列为空队列为空*/t=q-front;/*t指向第一个数据结点指向第一个数据结点*/if (q-front=q-rear) /*原链队中只有一个结点时原链队中只有一个结点

39、时*/ q-front=q-rear=NULL;else/*原链队中有多个结点时原链队中有多个结点时*/ q-front=q-front-next;e=t-data; free(t);return true; 59 例例3.8 采用一个不带头节点只有一个尾节点指针采用一个不带头节点只有一个尾节点指针rear的循的循环单链表存储队列，设计队列的初始化、进队和出队算法。环单链表存储队列，设计队列的初始化、进队和出队算法。reara1ana2队头队头队尾队尾这样的链队通过尾节点指针这样的链队通过尾节点指针rear唯一标识。唯一标识。队空条件：队空条件：rear=NULL队满条件：队满条件：不考虑不考

40、虑进队进队e操作：操作：将包含将包含e的节点插入到单链表表尾的节点插入到单链表表尾出队操作：出队操作：删除单链表首节点删除单链表首节点链队的链队的4 4要素：要素：60void initQueue(LinkList *&rear)/初始化队运算算法初始化队运算算法rear=NULL;bool queueEmpty(LinkList *rear) /判队空运算算法判队空运算算法 return(rear=NULL);61void enQueue(LinkList *&rear,ElemType x)/进队运算算法进队运算算法 LinkList *p; p=(LinkList *)m

41、alloc(sizeof(LinkList);/创建新节点创建新节点 p-data=x; if (rear=NULL)/原链队为空原链队为空 p-next=p;/构成循环链表构成循环链表rear=p; else p-next=rear-next;/将将*p节点插入到节点插入到*rear节点之后节点之后rear-next=p;rear=p; /让让rear指向这个新插入的节点指向这个新插入的节点 reara1ana2队头队头队尾队尾px62bool deQueue(LinkList *&rear,ElemType &x)/出队运算算法出队运算算法 LinkList *q; if

42、(rear=NULL) return false;/队空队空 else if (rear-next=rear)/原队中只有一个节点原队中只有一个节点 x=rear-data;free(rear);rear=NULL; else /原队中有两个或以上的节点原队中有两个或以上的节点 q=rear-next;x=q-data;rear-next=q-next;free(q); return true;reara1ana2队头队头队尾队尾63这里限定的表达式求值问题是：这里限定的表达式求值问题是：用户输入一个包含用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数、正整数和圆括号的合

43、法数学表达式，计算该表达式的运算结果。学表达式，计算该表达式的运算结果。 3.1.4 栈的应用举例栈的应用举例-表达式求值表达式求值 表达式的三种表示方法：表达式的三种表示方法：设设 Exp = S1 + OP + S2称称 OP + S1 + S2 为为前缀前缀表示法表示法 S1 + OP + S2 为为中缀中缀表示法表示法 S1 + S2 + OP 为为后缀后缀表示法表示法 操作数操作数运算符运算符64例如例如: Exp = a b + (c d / e) f前缀式前缀式: + a b c / d e f中缀式中缀式: a b + c d / e f后缀式后缀式: a b c d e /

44、f + 结论结论:1）操作数之间的相对次序不变）操作数之间的相对次序不变;2）运算符的相对次序不同）运算符的相对次序不同;3）中缀式丢失了括号信息，致使运算次序被改变）中缀式丢失了括号信息，致使运算次序被改变;4) 前缀式的运算规则为前缀式的运算规则为: 连续出现的两个操作数和在它们之前且紧靠它连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式们的运算符构成一个最小表达式;5) 后缀式的运算规则为后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序，运算符在式中出现的顺序恰为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数每个运算符和在它之前出现且紧

45、靠它的两个操作数构成一个最小表达式构成一个最小表达式;栈的应用栈的应用:表达式求值表达式求值65如何从后缀式求值？如何从后缀式求值？ 先找运算符先找运算符 再找操作数再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e)f66 对后缀表达式求值过程是对后缀表达式求值过程是: 从左到右读入后缀表达式；从左到右读入后缀表达式； 若读入的是一个操作数，若读入的是一个操作数，就将它入数值栈；就将它入数值栈； 若读入的是一个运算符若读入的是一个运算符op，就从数值栈中连续就从数值栈中连续出栈两个元素出栈两个元素(两个操作数两个操作数)，假设为，假设为x和和y，计，计算

46、算x op y之值，并将计算结果入数值栈；之值，并将计算结果入数值栈； 对整个后缀表达式读入结束时，栈顶元素就是对整个后缀表达式读入结束时，栈顶元素就是计算结果。计算结果。 算术表达式求值过程是：算术表达式求值过程是：先将算术表达式转换成后先将算术表达式转换成后缀表达式，然后对该后缀表达式求值缀表达式，然后对该后缀表达式求值67postexp5 6 # 2 0 # - 4 # 2 # + /运算数栈运算数栈5620-3642+6/668while (从从exp读取字符读取字符ch,ch!=0) 若若ch为数字为数字,将后续的所有数字均依次存放到将后续的所有数字均依次存放到postexp中中,并

47、以并以字符字符“#”标志数值串结束。标志数值串结束。 若若ch为左括号为左括号“(”,则将此括号进栈到运算符栈则将此括号进栈到运算符栈op中。中。 若若ch为右括号为右括号“)”,则将运算符栈则将运算符栈op中左括号中左括号“(”以前的运以前的运算符依次出栈并存放到算符依次出栈并存放到postexp中中,然后将左括号然后将左括号“(”删除。删除。 若若ch运算符优先级小于或等于运算符优先级小于或等于op栈顶运算符的优先级栈顶运算符的优先级 (除栈除栈顶运算符为顶运算符为“(”外外)的优先级的优先级,则依次出栈并存入到则依次出栈并存入到postexp中中,然然后将后将ch进栈。进栈。 若字符串若

48、字符串exp扫描完毕扫描完毕,则将运算栈则将运算栈op中的所有运算符依次出中的所有运算符依次出栈并存放到栈并存放到postexp中。最后得到后缀表达式中。最后得到后缀表达式postexp。中缀表达式中缀表达式后缀后缀表达式表达式69a + b c d / e f 0exppostexp+a b cd ef运算符栈运算符栈chchchchchch -/ 中缀表达式中缀表达式后缀后缀表达式表达式70表达式求值：算符优先法表达式求值：算符优先法 x = 4 - 6 / 3 + 2 * ( 3 + 8 ) 操作数操作数(operand)+运算符运算符(operator)+界限符界限符(delimite

49、r ) 把运算符和界限符统称为算符把运算符和界限符统称为算符 算符优先法算符优先法 4 - 6 / 3 + 2 * ( 3 + 8 )=4-2 + 2 * ( 3 + 8 )=2+ 2 * ( 3 + 8 )=2+2*11=2+22=24运算规则：运算规则： 从左到右；从左到右； 先乘除，后加减；先乘除，后加减； 先括号内，后括号外；先括号内，后括号外；71表达式求值：算符优先法表达式求值：算符优先法不论操作数或运算符，不论操作数或运算符，先输入，后参与运算先输入，后参与运算可以考虑使用栈实现可以考虑使用栈实现算法算法设置设置两个栈两个栈opnd和和optr，分别存放，分别存放操作数操作数和和

50、运算符运算符；运算过程就是运算过程就是比较运算符优先级比较运算符优先级的过程（的过程（a 1 b 2 ) 1 优先权低于优先权低于 2，不能运算不能运算 1 优先权等于优先权等于 2 ，结束（结束（#）或退括号）或退括号（） 1 优先权高于优先权高于 2，可以运算可以运算72算符间的优先关系算符间的优先关系u设两个设两个运算符运算符： 1 和和 2 1 2, 1 优先权高于优先权高于 2+*/()#+*/(#=0&ch=9) Push( opnd, ch); scanf(&ch); else switch( precede (StackGetTop( optr ), ch )c

51、ase : /栈顶元素优先级高栈顶元素优先级高theta=Pop( optr );b=Pop( opnd );a=Pop (opnd );Push( opnf, operate( a, theta, b );break;/ switchreturn (StackGetTop( opnd );77u十进制数十进制数N转换为转换为d进制的原理：进制的原理： N = (N / d)*d + N % d（/为整除，为整除，%为取余）为取余）（1348)10 转换成转换成 (2504)8 的过程如下：的过程如下： N N / 8 N % 8计计算算顺顺序序输输出出顺顺序序1348 168 4 168 2

52、1 0 21 2 5 2 0 2栈的应用：数制转换栈的应用：数制转换78栈的应用：数制转换栈的应用：数制转换void convert( ) / 将非负十进制整数转换为八进制整数将非负十进制整数转换为八进制整数 StackInit ( S ); scanf( “%d”, &N ); while( N!=0 ) Push( S, N%8 );N = N/8; while( !StackEmpty( S ) ) e=Pop( S ); printf( “%d”, e ); 79 迷宫问题就是求出从入口到出口的路径。迷宫问题就是求出从入口到出口的路径。 在求解时，通常用的是在求解时，通常用的是

53、“穷举求解穷举求解”的方法，的方法，即从入口出发，顺某一方向向前试探，若能即从入口出发，顺某一方向向前试探，若能走通，则继续往前走；走通，则继续往前走； 否则沿原路退回，换一个方向再继续试探，否则沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。直至所有可能的通路都试探完为止。 为了保证在任何位置上都能沿原路退回（称为了保证在任何位置上都能沿原路退回（称为为回溯回溯），需要用一个后进先出的栈来保存），需要用一个后进先出的栈来保存从入口到当前位置的路径。从入口到当前位置的路径。栈的应用：迷宫问题栈的应用：迷宫问题800 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9(i-1,j