第3章 栈和队列 3.1 栈 3.2 队列.

Presentation on theme: "第3章 栈和队列 3.1 栈 3.2 队列."— Presentation transcript:

1 第3章 栈和队列 3.1 栈 3.2 队列

2 栈和队列的特点 两者的逻辑结构与线性表相同，但是插入和删除操作受到了限制；
栈只允许在线性表的一端进行插入和删除操作，队列则允许在一端插入另一端删除； 栈按照“后进先出”的规则进行操作，队列则按照“先进先出”的规则进行。

3 3.1 栈 3.1.1 栈的定义 3.1.2 顺序存储结构及其基本运算实现 3.1.3 链式存储结构及其基本运算实现
3.1 栈 3.1.1 栈的定义 3.1.2 顺序存储结构及其基本运算实现 3.1.3 链式存储结构及其基本运算实现 3.1.4 栈的应用举例

4 3.1.1 栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶。
当栈中没有数据元素时，称为空栈。 入栈 出栈 栈顶 top an … a3 a2 栈底 bottom a1

5 练 习 1 依次输入3个元素A、B、C到栈中，可得到哪几种不同的输出？ 解：共5种 (1) A,B,C (2) A,C,B
(3) B,A,C (4) B,C,A (5) C,B,A

6 练 习 2 设一个栈的输入序列为A、B、C、D,则借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A
(C) A,C,D,B (D) D,A,B,C 答案：D

7 栈的抽象数据类型 ADT Stack{ 数据对象：D={ai|1≤i≤n,n≥0，ai 为ElemType类型}
数据关系：R={<ai ，ai+1 >| ai ，ai+1  D ，i=1,...,n-1} 基本运算: InitStack(&s) //初始化栈：构造一个空栈s DestroyStack(&s) //销毁栈：释放栈s占用的存储空间 StackEmpty(s) //判断栈是否为空 Push(&S,e) //进栈：将元素e插入到栈s中作为栈顶元素 Pop(&s,&e) //出栈：从栈s中退出栈顶元素，并将其值赋给e GetTop(s,&e) //取栈顶元素：返回当前的栈顶元素，并将其值赋给e }ADT Stack

8 Push(&S, e) 初始条件：栈 S 已存在 操作结果：插入e为新的栈顶元素 a1 a2 … … an e

9 Pop(&S,&e) 初始条件：栈 S 存在且非空 操作结果：删除S 的栈顶元素，赋值给e a1 a2 … … an-1 an

10 GetTop(S,&e) 初始条件：栈 S 已存在且非空 操作结果：返回 S 的栈顶元素，赋值给e a1 a2 … … an

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

12 顺序栈进栈和出栈示意图

13 顺序栈的类型定义 typedef struct { ElemType data[MaxSize]； int top； /*栈顶指针*/
} SqStack； 采用栈指针的方式建立和使用顺序表 SqStack *s；

14 在顺序栈中实现栈的基本运算 (1) 初始化栈InitStack(s) 建立一个新的空栈s，实际上是将栈顶指针指向-1即可。
void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; }

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 在栈不满的条件下，先将栈顶指针增1，然后在该位置上插入元素e。 bool Push(SqStack *&s,ElemType e)
(4) 进栈Push(s,e) 在栈不满的条件下，先将栈顶指针增1，然后在该位置上插入元素e。 bool Push(SqStack *&s,ElemType e) { if (s->top==MaxSize-1) return false; /*栈满的情况，即栈向上溢出*/ s->top++; s->data[s->top]=e; return true; }

18 在栈不为空的条件下，先将栈顶元素赋给e，然后将栈顶指针减1。 bool Pop(SqStack *&s,ElemType &e)
(5) 出栈Pop(s,e) 在栈不为空的条件下，先将栈顶元素赋给e，然后将栈顶指针减1。 bool Pop(SqStack *&s,ElemType &e) { if (s->top==-1) return false; /*栈为空的情况，即栈向下溢出*/ e=s->data[s->top]; s->top--; return true; }

19 bool GetTop(SqStack *s,ElemType &e)
(6) 取栈顶元素GetTop(s,e) 在栈不为空的条件下，将栈顶元素赋给e。 bool GetTop(SqStack *s,ElemType &e) { if (s->top==-1) return false; /*栈为空的情况，即栈向下溢出*/ e=s->data[s->top]; return true; }

20 (7) 显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。 void DispStack(SqStack *s)
{ int i; for (i=s->top;i>=0;i--) printf("%c ",s->data[i]); printf("\n"); }

21 例3.4 编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。
【算法思想】对于字符串str,先将其所有元素进栈，然后从头扫描str，并弹出栈顶元素，将两者进行比较，若不相同则返回false。当str扫描完毕时返回true。 实际上，从头开始扫描str是从左向右读，出栈是从右向左读，两者相等说明该串是对称串。

22 bool symmetry(ElemType str[])
{ int i; ElemType e; SqStack *st; InitStack(st); for (i=0;str[i]!='\0';i++) //将串所有元素进栈 Push(st, str[i]); for (i=0;str[i]!='\0';i++) Pop(st,e); //退栈元素e if (str[i]!=e) //若e与当前串元素不同则不是对称串 { DestroyStack(st); return false; } } DestroyStack(st); return true;

23 3.1.3 链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈，这里采用单链表实现 链栈的优点？ 入栈出栈操作在哪一端进行？
链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈，这里采用单链表实现 链栈的优点？ 入栈出栈操作在哪一端进行？ 下图中，栈中元素自栈顶到栈底依次是a1、a2、…、an 不存在栈满上溢的情况 单链表的表头

24 链栈中数据结点的类型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; }

26 (2) 销毁栈DestroyStack(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(LiStack *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 void Push(LiStack *&s,ElemType e)
(5) 进栈Push(s,e) 将新数据结点插入到头结点之后。 void Push(LiStack *&s,ElemType e) { LiStack *p; p=(LiStack *)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; /*插入*p作为第一个数据结点*/ s->next=p; }

30 在栈不为空的条件下，将头结点的指针域所指数据结点的数据域赋给e，然后将该数据结点删除。
(6) 出栈Pop(s,e) 在栈不为空的条件下，将头结点的指针域所指数据结点的数据域赋给e，然后将该数据结点删除。 bool Pop(LiStack *&s,ElemType &e) { LiStack *p; if (s->next==NULL) return false; /*栈空的情况*/ p=s->next; /*p指向第一个数据结点*/ e=p->data; s->next=p->next; free(p); return true; }

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

32 (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，扫描表达式exp，遇到左括号时进栈；遇到右括号时：若栈顶为左括号，则出栈，否则，返回0。 当表达式扫描完毕，栈为空时返回1，表示括号正确匹配，否则返回0。

34 int Match(char exp[],int n)
{ int i=0; char e; SqStack *st; InitStack(st); while (i<n) if (exp[i]=='(') //当前字符为左括号,将其进栈 Push(st,exp[i]); else if (exp[i]==')') //当前字符为右括号 if (GetTop(st,e)==1) if (e!='(') return(0); //括号不匹配时返回0 else Pop(st,e); //将栈顶元素出栈 } else return(0); //取栈元素下溢出时返回0 i++; //继续处理其他字符 if (StackEmpty(st)==1) return(1); else return(0);

35 3.2 队 列 3.2.1 队列的定义 3.2.2 顺序存储结构及其基本运算的实现 3.2.3 链式存储结构及其基本运算的实现
3.2.4 队列的应用举例

36 3.2.1 队列的定义 队列：仅允许在表的一端进行插入，而在表的另一端进行删除。 队尾(rear)：进行插入的一端
队首(front)：进行删除的一端 向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素； 从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。 入队 出队 a1 a2 a3 an-1 …… 队首 队尾

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

38 3.2.2 顺序存储结构及其基本运算的实现 用数组实现队列 ... typedef struct {
ElemType data[MaxSize]； int front,rear；/*队首和队尾指针*/ } SqQueue； 1 2 n-2 n-1 a 3 ... n front rear

39 队列的顺序存储结构 存在的问题1 解决方法：让队头指针指向队列真正队头元素的前 一个位置。 队空时，队头和队尾指针都为-1。
1 2 ... n-2 n-1 front=rear =-1 存在的问题1 队空时，队头和队尾指针都为-1。 此时若进行入队操作，队头和队尾指针都增1，再将新数 据元素放入该位置。 用这种方法设置队头、队尾指针位置，在进行入队操作 时，空队与非空队需要执行的操作不完全一样。 解决方法：让队头指针指向队列真正队头元素的前 一个位置。

40 ... 队头指针front指向队头元素的前一个位置 队尾指针rear指向队尾元素 空队时：front=rear=-1
1 2 n-2 n-1 a 3 ... n front rear 队头指针front指向队头元素的前一个位置 队尾指针rear指向队尾元素 空队时：front=rear=-1 入队原则：队尾指针rear = rear + 1，再将新元素按 rear 指示位置加入 出队原则：队头指针front = front + 1，再将下标为 front 的元素取出 队中元素的个数：m=rear-front

41 队列的入队和出队操作示意图 front=rear=-1 rear = rear + 1 front = front + 1
队中元素的个数：m=rear-front 思考：能不能用rear==MaxSize-1作为队满的条件？ 显然不能，在图(d)中，队列为空，但仍满足该条件。 这时入队，出现“假溢出” 问题2

42 循环队列 为了能够充分地使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形的顺序表，称为循环队列。 入队：
rear = (rear + 1)% MAXSIZE 出队： front= (front + 1)% MAXSIZE 元素个数： m=(rear-front+MAXSIZE)% MAXSIZE

43 用数组实现队列存在的问题3 front=4,rear=3 少用一个元素空间时的队列满 front=8,rear=8 队空
有4个元素 front=4,rear=4 队列满

44 怎样区分这两者之间的差别呢? 在入队时少用一个数据元素空间，以队尾指针加1等于队首指针判断队满，即队满条件为: (rear+1) % MaxSize==front 队空条件仍为: rear==front

45 设置计数器 typedef struct { datatype data[MAXSIZE]; /*数据的存储区*/
int front,rear; /*队头队尾指针*/ int num; /*队中元素的个数*/ }c_SeQueue; /*循环队*/

46 构造一个空队列q。将front和rear指针均设置成初始状态即0值。 void InitQueue(SqQueue *&q)
(1) 初始化队列InitQueue(q) 构造一个空队列q。将front和rear指针均设置成初始状态即0值。 void InitQueue(SqQueue *&q) { 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); }

49 在队列不满的条件下，先将队尾指针rear循环增1，然后将元素添加到该位置。
(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->data[q->rear]=e; return true; }

50 在队列q不为空的条件下，将队首指针front循环增1，并将该位置的元素值赋给e。
(5) 出队列deQueue(q,e) 在队列q不为空的条件下，将队首指针front循环增1，并将该位置的元素值赋给e。 bool deQueue(SqQueue *&q,ElemType &e) { if (q->front==q->rear) /*队空*/ return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; }

51

52 3.2.3 链式存储结构及其基本运算的实现 链队组成: … (1) 存储队列元素的单链表 (2) 存储队头和队尾指针的链队头结点 rear
front a1 an ∧ a2 a3

53 链列的入队和出队操作示意图

54 单链表中数据结点类型QNode定义如下: typedef struct qnode
{ ElemType data; /*数据元素*/ struct qnode *next; } QNode; 链队中头结点类型LiQueue定义如下: typedef struct { QNode *front; /*指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点*/ } LiQueue;

55 构造一个空队列，即只创建一个链队头结点，其front和rear域均置为NULL，不创建数据元素结点。
(1) 初始化队列InitQueue(q) 构造一个空队列，即只创建一个链队头结点，其front和rear域均置为NULL，不创建数据元素结点。 void InitQueue(LiQueue *&q) { q=(LiQueue *)malloc(sizeof(LiQueue)); q->front=q->rear=NULL; }

56 (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); /*释放链队头结点占用空间*/

57 (3) 判断队列是否为空QueueEmpty(q) 若链队结点的rear域值为NULL，表示队列为空，返回true；否则返回false。
bool QueueEmpty(LiQueue *q) { return(q->rear==NULL); }

58 void enQueue(LiQueue *&q,ElemType e)
(4) 进队列enQueue(q,e) 创建data域为e的数据结点*s。若原队列为空，则将链队结点的两个域均指向*s结点，否则，将*s链到单链表的末尾，并让链队结点的rear域指向它。 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; }

59 (5) 出队列deQueue(q,e) 若原队列不为空，则将第一个数据结点的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) /*原链队中只有一个结点时*/ q->front=q->rear=NULL; else /*原链队中有多个结点时*/ q->front=q->front->next; e=t->data; free(t); return true; }

60 这样的链队通过尾节点指针rear唯一标识。
队头 队尾 rear … a1 a2 an 这样的链队通过尾节点指针rear唯一标识。 链队的4要素： 队空条件：rear=NULL 队满条件：不考虑 进队e操作：将包含e的节点插入到单链表表尾 出队操作：删除单链表首节点

61 void initQueue(LinkList *&rear)//初始化队运算算法
{ 　　rear=NULL; } bool queueEmpty(LinkList *rear) //判队空运算算法 return(rear==NULL);

62 void enQueue(LinkList *&rear,ElemType x) //进队运算算法 { LinkList *p;
队头 队尾 rear … p a1 a2 an x void enQueue(LinkList *&rear,ElemType x) //进队运算算法 { LinkList *p; p=(LinkList *)malloc(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指向这个新插入的节点

63 bool deQueue(LinkList *&rear,ElemType &x) //出队运算算法 { LinkList *q;
队头 队尾 rear … a1 a2 an bool deQueue(LinkList *&rear,ElemType &x) //出队运算算法 { LinkList *q; if (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;

64 3.1.4 栈的应用举例----表达式求值 这里限定的表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。 表达式的三种表示方法： 操作数 运算符 设 Exp = S1 + OP + S2 称 OP + S1 + S 为前缀表示法 S1 + OP + S 为中缀表示法 S1 + S2 + OP 为后缀表示法

65 栈的应用:表达式求值 例如: Exp = a  b + (c  d / e)  f
结论: 5) 后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式; 4) 前缀式的运算规则为: 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式; 3）中缀式丢失了括号信息，致使运算次序被改变; 1）操作数之间的相对次序不变; 2）运算符的相对次序不同;

66 如何从后缀式求值？ a b  c d e /  f  + 先找运算符 再找操作数 例如： d/e c-d/e (c-d/e)f

67 对后缀表达式求值过程是: 从左到右读入后缀表达式； 若读入的是一个操作数，就将它入数值栈；
若读入的是一个运算符op，就从数值栈中连续出栈两个元素(两个操作数)，假设为x和y，计算x op y之值，并将计算结果入数值栈； 对整个后缀表达式读入结束时，栈顶元素就是计算结果。 算术表达式求值过程是：先将算术表达式转换成后缀表达式，然后对该后缀表达式求值

68 运算数栈 postexp 5 6 # 2 0 # - 4 # 2 # + / + - / 2 20 6 4 36 56 6

69 中缀表达式后缀表达式 while (从exp读取字符ch,ch!='\0')
{ 若ch为数字,将后续的所有数字均依次存放到postexp中,并以字符“#”标志数值串结束。 若ch为左括号“(”,则将此括号进栈到运算符栈op中。 若ch为右括号“)”,则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中,然后将左括号“(”删除。 若ch运算符优先级小于或等于op栈顶运算符的优先级 (除栈顶运算符为“(”外)的优先级,则依次出栈并存入到postexp中,然后将ch进栈。 } 若字符串exp扫描完毕,则将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。

70 中缀表达式后缀表达式 运算符栈 a + b  c  d / e  f `\0`   / - + exp postexp a b
ch ch ch ch ch ch postexp   / a b c d e f - +

71 表达式求值：算符优先法 x = 4 - 6 / 3 + 2 * ( 3 + 8 ) 把运算符和界限符统称为算符 算符优先法 运算规则：
操作数(operand)+运算符(operator)+界限符(delimiter ) 把运算符和界限符统称为算符 算符优先法 4 - 6 / * ( ) = * ( ) =2+ 2 * ( ) =2+2*11 =2+22 =24 运算规则： 从左到右； 先乘除，后加减； 先括号内，后括号外；

72 表达式求值：算符优先法 不论操作数或运算符，先输入，后参与运算 算法 可以考虑使用栈实现
设置两个栈opnd和optr，分别存放操作数和运算符； 运算过程就是比较运算符优先级的过程（a 1 b 2 ) 1 优先权低于 2，不能运算 1 优先权等于 2，结束（‘#’）或退括号（‘）’） 1 优先权高于 2，可以运算

73 算符间的优先关系 设两个运算符： 1 和 2 1< 2, 1 优先权低于 2 1= 2, 1 优先权等于 2
1< 2, 1 优先权低于 2 1= 2, 1 优先权等于 2 1> 2, 1 优先权高于 2 + － * / ( ) # > < =

74 【例】# * 3 – 8 / ( 7 – 5 ) # opnd optr opnd optr opnd optr opnd optr 4 # 2 4 + # 3 2 4 * + # 4 + # a=3；b=2；op=*；c=2*3=6； opnd optr opnd optr opnd optr opnd optr 6 4 + # # 10 # 8 10 / - # a=6；b=4；op=+； c=4+6=10；

75 【例】# * 3 – 8 / ( 7 – 5 ) # opnd optr opnd optr opnd optr opnd optr 8 10 （ / - # 5 7 8 10 - （ / # 8 10 （ / - # 2 8 10 （ / - # a=5；b=7；op=-；c=7-5=2； opnd optr opnd optr opnd optr opnd optr 2 8 10 / - # 10 - # 4 10 - # # a=2；b=8；op=/；c=8/2=4； a=4；b=10；c=10-4=6；

76 栈的应用：表达式求值 int CalculExp( ) { //表达式求值的算符优先算法，设optr和opnd分别为运算符栈和操作数栈
StackInit ( optr ); Push( optr , ‘#’ ); StackInit ( opnd ); scanf(&ch); while( !((ch==‘#’)&&(StackGetTop( optr ) == ‘#’))) if(ch>=‘0’&&ch<=‘9’) { Push( opnd, ch); scanf(&ch); } else switch( precede (StackGetTop( optr ), ch )) {case ‘<’ : Push( optr, ch ); //栈顶元素优先级低 break; case ‘=‘ : Pop( optr ); // c为’)’，退括号

77 栈的应用：表达式求值 case ‘>’: //栈顶元素优先级高 theta=Pop( optr ); b=Pop( opnd );
a=Pop (opnd ); Push( opnf, operate( a, theta, b )); break; }// switch return (StackGetTop( opnd )); }

78 N = (N / d)*d + N % d（/为整除，%为取余）
栈的应用：数制转换 十进制数N转换为d进制的原理： N = (N / d)*d + N % d（/为整除，%为取余） （1348)10 转换成 (2504)8 的过程如下： N N / N % 8 输出顺序 计算顺序

79 栈的应用：数制转换 void convert( ) { // 将非负十进制整数转换为八进制整数 StackInit ( S );
{ // 将非负十进制整数转换为八进制整数 StackInit ( S ); scanf( “%d”, &N ); while( N!=0 ) { Push( S, N%8 ); N = N/8; } while( !StackEmpty( S ) ) { e=Pop( S ); printf( “%d”, e ); } }

80

81 栈的应用：迷宫问题 迷宫问题就是求出从入口到出口的路径。
在求解时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前试探，若能走通，则继续往前走； 否则沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。 为了保证在任何位置上都能沿原路退回（称为回溯），需要用一个后进先出的栈来保存从入口到当前位置的路径。

82 所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。
　　所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。 入口 (i-1,j)方位0 (i,j-1)方位3 (i,j+1)方位1 (i，j) 出口 (i+1,j)方位2

83 　　为了便于回溯，对于可走的方块都要进栈，并试探它的下一可走的方位，将这个可走的方位保存到栈中，为此将栈定义为:
typedef struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一可走相邻方位的方位号 } Box; //定义方块类型 { Box data[MaxSize]; int top; //栈顶指针 } StType; //顺序栈类型

84 3.2.4 队列的应用：迷宫问题 使用一个队列qu记录走过的方块，该队列的结构如下: typedef struct
队列的应用：迷宫问题 使用一个队列qu记录走过的方块，该队列的结构如下: typedef struct { int i,j; //方块的位置 int pre; //本路径中上一方块在队列中的下标 } Box; //方块类型 { Box data[MaxSize]; int front,rear; //队头指针和队尾指针 } QuType; //定义顺序队类型 这里使用的队列qu不是环形队列（因为要利用出队的元素找路径），因此在出队时，不会将出队元素真正从队列中删除，因为要利用它输出路径。

85 搜索从(1,1)(M,N)路径 (1) 首先将(1,1)入队;
(2) 在队列qu不为空时循环：出队一次（由于不是环形队列，该出队元素仍在队列中），称该出队的方块为当前方块，front为该方块在qu中的下标。 ①如果当前方块是出口，则输出路径并结束。 ②否则按顺时针方向找出当前方块的四个方位中可走的相邻方块（对应的mg数组值为0），将这些可走的相邻方块均插入到队列qu中，其pre设置为本搜索路径中上一方块在qu中的下标值，也就是当前方块的front值，并将相邻方块对应的mg数组值置为-1，以避免回过来重复搜索。 (3) 若队列为空仍未找到出口，即不存在路径。

86 主要思想：从(1,1)开始，利用队列的特点，一层一层向外扩展可走的点，直到找到出口为止
这个方法就是将在图一章介绍的图的广度优先搜索方法。

87 本章小结 (1) 理解栈和队列的特性以及它们之间的差异，知道在何时使用哪种数据结构。
(2) 重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3) 重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队上队满和队空的条件。 (4) 灵活运用栈和队列这两种数据结构解决一些综合应用问题。

88 作 业 教材P95 练习题3 习题3.1、3.3、3.5 学习指导 第3章 P P 、5