数据结构：第03章 栈和队列

1、3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 1数据结构数据结构第三章第三章 栈和队列栈和队列2022年年3月月29日星期二日星期二3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基

2、本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 2第三章第三章 栈和队列栈和队列3.1 栈栈栈和队列也是线性表，只不过是栈和队列也是线性表，只不过是操作受限操作受限的线性表。的线性表。栈栈是限定在是限定在表尾表尾进行插入或删除操作的线性表。表尾进行插入或删除操作的线性表。表尾端称端称栈顶栈顶，表头端称，表头端称栈底栈底。如图。如图。an.a2a1栈底栈底栈顶栈顶出栈出栈进栈进栈 栈顶（栈顶（TOP）-允许插入和删除的一端。允许插入和删除的一端。 栈底栈底(bottom)-不允许插入和删除的一端。不允许插入和删除的一端。 空栈空栈-表中没有元素。

3、表中没有元素。进栈进栈-最先插入的元素放在栈的底部。最先插入的元素放在栈的底部。退栈退栈-最后插入的元素最先退栈。最后插入的元素最先退栈。所以栈又称为所以栈又称为后进先出后进先出的线性表的线性表（LIFO表，表，Last In First Out）3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 33.1 3.1 栈栈3.1.1 栈的类型定义

4、栈的类型定义ADT Stack 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系：R1 | ai-1, aiD, i=2,.,n 约定约定an 端端为栈顶，为栈顶，a1 端为栈底。端为栈底。基本操作基本操作：InitStack(&S) 操作结果：操作结果：构造一个空栈构造一个空栈S。DestroyStack(&S)初始条件：初始条件：栈栈S已存在。已存在。操作结果：操作结果：栈栈S被销毁。被销毁。ClearStack(&S)初始条件：初始条件：栈栈S已存在。已存在。操作结果操作结果：将：将S清为空栈。清为空栈。Stac

5、kEmpty(S)初始条件：初始条件：栈栈S已存在。已存在。操作结果：操作结果：若栈若栈S为空栈，则返回为空栈，则返回TRUE，否则，否则FALSE。3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 43.1 3.1 栈栈3.1.1 栈的类型定义栈的类型定义StackLength(S)初始条件：初始条件：栈栈S已存在。已存在。操作结果：操作结

6、果：返回返回S的元素个数，即栈的长度。的元素个数，即栈的长度。GetTop(S, &e)初始条件：初始条件：栈栈S已存在且非空。已存在且非空。操作结果：操作结果：用用e返回返回S的栈顶元素。的栈顶元素。Push(&S, e)初始条件：初始条件：栈栈S已存在。已存在。操作结果：操作结果：插入元素插入元素e为新的栈顶元素。为新的栈顶元素。Pop(&S, &e)初始条件：初始条件：栈栈S已存在且非空。已存在且非空。操作结果：操作结果：删除删除S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。 ADT Stack3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈

7、 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 53.1 3.1 栈栈3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示#define STACK_INIT_SIZE 100 /栈内存的初始分栈内存的初始分配量，以配量，以sizeof(ElemType)为单位为单位 #define STACKINCREMENT 10 /栈内存的分配栈内存的分配增量，以增量，以sizeof(ElemT

8、ype)为单位为单位 typedef struct SElemType *base; /存储空间的基址，数据元存储空间的基址，数据元素的数据类型约定为素的数据类型约定为SElemType SElemType * top; /表示栈顶，如果表示栈顶，如果top=base，表示空栈表示空栈 int stacksize; /当前分配的存储容量，以当前分配的存储容量，以sizeof(ElemType) 为单位为单位 SqStack 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3

9、.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 6 3 2 1 0Top=base 空栈空栈TopbaseA 3 2 1 0TOP A进栈进栈base 3 2 1 0DCBAB、C、D依次进栈依次进栈TOPbase 3 2 1 0BATOPD、C依次退栈依次退栈base 3 2 1 0B、A退栈退栈baseTOP3.1 3.1 栈栈3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2

10、顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 73.1.2 3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示顺序栈基本操作的实现顺序栈基本操作的实现Status InitStack(SqStack &S) /为栈为栈S分配存储空间，并置分配存储空间，并置S为空栈为空栈 S.base=(SElemType *)malloc(STACK_INIT_SIZE* sizeof( SElemType);if(!S.base)exit(OVERFLOW); S.top=S.base; /置栈置栈S为空栈为空栈

11、 S.stacksize=STACK_INIT_SIZE; return OK; /InitStack 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 83.1.2 3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示顺序栈基本操作的实现顺序栈基本操作的实现Status GetTop(SqStack S,SElemType &

12、e) /若栈不空，则用若栈不空，则用e返回返回S的栈顶元素并返回的栈顶元素并返回OK，否则返回否则返回ERROR if(S.top=S.base) return ERROR;e=*(S.top-1); return OK; /GetTop 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 93.1.2 3.1.2 栈的表示和实现栈的表示和实现

13、-顺序表示顺序表示顺序栈基本操作的实现顺序栈基本操作的实现Status Push(SqStack &S, SElemType e) /将将e插入栈插入栈S中并使之成为栈顶元素中并使之成为栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间栈满，追加存储空间 S.base=(SElemType *) realloc(S.base ,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW); /存储分配失败存储分配失败 S.stacksize+=STACKINCREME

14、NT; *S.top+=e; return OK;/Push3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 103.1.2 3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示顺序栈基本操作的实现顺序栈基本操作的实现Status Pop(SqStack &S,SElemType &e) /若栈若栈S不空，则删除不空，则

15、删除S的栈顶元素，用的栈顶元素，用e返回其值并返返回其值并返回回OK，否则返回，否则返回ERROR if(S.top=S.base) return ERROR;e=*-S.top; return OK; /Pop 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 113.1.2 3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示顺序栈

16、基本操作的实现顺序栈基本操作的实现 Status DestroyStack(SqStack &S) /释放栈释放栈S所占据的存储空间所占据的存储空间 if(!S.base)return ERROR; free(S.base); S.base=NULL; S.top= NULL; return OK; /DestroyStackStatus ClearStack(SqStack &S) /将栈将栈S清为空栈清为空栈 S.top=S.base; return OK; /ClearStack 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例

17、 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 123.1.2 3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示顺序栈基本操作的实现顺序栈基本操作的实现Status StackEmpty(SqStack S) /如果栈为空栈，则返回如果栈为空栈，则返回TRUE，否则返回，否则返回FALSE if(S.top=S.base)return TRUE; else return FALSE; /StackEmptyStatus

18、StackLength(SqStack S) /返回栈返回栈S的长度的长度 return S.top-S.base; /StackLength3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 133.1.2 3.1.2 栈的表示和实现栈的表示和实现-顺序表示顺序表示顺序栈基本操作的实现顺序栈基本操作的实现Status StackTravers

19、e(SqStack S, Status (*visit)(SElemType e) /从栈底到栈顶依次对栈中每个元素调用从栈底到栈顶依次对栈中每个元素调用visit函数，如函数，如果果visit失败，则操作失败失败，则操作失败 if(S.top=S.base)return ERROR; for(i=0;i S.top-S.base;i+) if(visit(S.basei)=ERROR) return ERROR; return OK; /StackTraverse 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达

20、式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 143.1.2 3.1.2 栈的表示和实现栈的表示和实现- - 链接表示链接表示链栈的表示链栈的表示struct Node/* 单链表结点结构单链表结点结构 */ElemType info; struct Node *link; ;struct LinkStack/* 链栈类型定义链栈类型定义 */struct Node *top;/* 指向栈顶结点指向栈顶结点 */ LinkStack, *PLinkStack;ba

21、t cat eat mat headtopbottom3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 153.1.2 3.1.2 栈的表示和实现栈的表示和实现- - 链接表示链接表示链栈基本操作的实现链栈基本操作的实现PLinkStack createEmptyStack_link( ) /创建一个空栈创建一个空栈 PLinkStack p

22、lstack; plstack = (struct LinkStack *)malloc( sizeof(struct LinkStack); if (plstack != NULL)plstack-top = NULL;elseprintf(Out of space! n); return plstack; DataType top_link( PLinkStack plstack ) /* 对非空栈求栈顶元素对非空栈求栈顶元素 */return plstack-top-info；3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换

23、 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 163.1.2 3.1.2 栈的表示和实现栈的表示和实现- - 链接表示链接表示链栈基本操作的实现链栈基本操作的实现int isEmptyStack_link( PLinkStack plstack ) /判单链形式栈是否为空栈判单链形式栈是否为空栈 return (plstack-top = NULL);void push_link( PLinkStack plstack, DataType x )/

24、* 在栈中压入一元素在栈中压入一元素x */struct Node * p; p = (struct Node *)malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!n); elsep-info = x;p-link = plstack-top;plstack-top = p;3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型

25、定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 173.1.2 3.1.2 栈的表示和实现栈的表示和实现- - 链接表示链接表示链栈基本操作的实现链栈基本操作的实现ElemType pop_link( PLinkStack plstack ) /* 在栈中删除栈顶元素在栈中删除栈顶元素 */ struct Node * p;ElemTypeelem; if( isEmptyStack_link( plstack ) )printf( Empty stack pop.n ); elsep = plstack-top;elem = p-info;plstack-top = p

26、lstack-top-link;free(p); return elem;3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 183. 2 3. 2 栈的应用举例栈的应用举例3.2.1数制转换数制转换将某十进制数将某十进制数N转换为其他转换为其他d进制数是计算机实现计进制数是计算机实现计算的基本问题，其解决方案很多，其中一个简单算法基于算的基本

27、问题，其解决方案很多，其中一个简单算法基于下面的原理：下面的原理： N=(N div d)d +N mod d (其中：其中：div为整除运算，为整除运算，mod为求余运算为求余运算) 比如，比如，(1348)10=(2504)8，其运算过程如下：，其运算过程如下： N N div 8 N mod 8 1348 168 4168 21 021 2 52 0 2 所以：所以：(1348)10=(2504)83.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3

28、.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 193. 2 3. 2 栈的应用举例栈的应用举例3.2.1数制转换数制转换假设现在要编制一个满足下列要求的程序：对于假设现在要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从的八进制数。由于上述计算过程是从低位到高位低位到高位顺序顺序产生八进制数的各个数位。而打印输出，一般来说应产生八进制数的各个数位。而打印输出，一般来说应从从高位到低位高位到低位进行，恰好和进行，恰好和计算

29、过程相反计算过程相反。因此，若。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。出栈序列打印输出的即为与输入对应的八进制数。3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 203. 2 3. 2 栈的应用举例栈的应用举例3.2.1数制转换数制转换

30、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 ); / conversion3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.

31、3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 213. 2 3. 2 栈的应用举例栈的应用举例3.2.2 括号匹配的检验括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（）或（其嵌套的顺序随意，即（）或（ ）等为正确的格式，（）等为正确的格式，（ ）或（）或（ ）或）或 ( )均为不正确的格式。均为不正确的格式。检验括号是否匹配的方法可用检验括号是否匹配的方法可用期待的急迫程度期待的急迫程度这个概念来描述。这个概念来描述。例如考虑下

32、列括例如考虑下列括号序列：号序列： ( ) 1 2 3 4 5 6 7 8分析可能出现的不匹配的情况分析可能出现的不匹配的情况:1.到来的右括弧到来的右括弧不是所不是所“期待期待”的的; 2.到来的是到来的是“不速之客不速之客”; 3.直到结束，也直到结束，也没有到来所没有到来所“期待期待”的。的。3. 2 3. 2 栈的应用举例栈的应用举例3.2.2 括号匹配的检验括号匹配的检验status matching(string& exp) / 检验表达式中所含括弧是否正确嵌检验表达式中所含括弧是否正确嵌套，若是，则返回套，若是，则返回 OK，否则返回，否则返回ERRORInitStack

33、(S); /构造空栈构造空栈Sint state = 1;while (i=length(exp) & state) swith of expi case 左括弧左括弧: Push(S,expi); i+; break; case ): if (NOT StackEmpty(S) & GetTop(S) = () Pop(S,e); i+; else state = 0 break; if ( state & StackEmpty(S) ) return OKelse return ERROR;3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3.

34、2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 233. 2 3. 2 栈的应用举例栈的应用举例3.2.3 行编辑程序问题行编辑程序问题 一个简单的行编辑程序的功能是：接受用户从终端输一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。入的程序或数据，并存入用户的数据区。每接受一个字符即存入用户数据区每接受一个字符即存入用户数据区“不恰当不恰当”。较好的做法是，设立一个输入缓冲区，用以

35、接受用户较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。输入出差错，并在发现有误时可以及时更正。例如，可用一个例如，可用一个退格符退格符“#”表示前一个字符无效；可表示前一个字符无效；可用一个用一个退行符退行符“”，表示当前行中的字符均无效。，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：例如，假设从终端接受了这样两行字符：whli#ilr#e（s#*s) outchaputchar(*s= #+);则实际有效的是下列两行：则实际有效的是下列两行

36、：while (*s)putchar(*s+);3. 2 3. 2 栈的应用举例栈的应用举例3.2.3 行编辑程序问题行编辑程序问题void LineEdit( ) / 利用字符栈利用字符栈S，从终端接收一行并传送至调，从终端接收一行并传送至调用过程用过程 的数据区。的数据区。InitStack(S); /构造空栈构造空栈Sch = getchar(); /从终端接收第一个字符从终端接收第一个字符while (ch != EOF) /EOF为全文结束符为全文结束符while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); br

37、eak; / 仅当栈非空时退栈仅当栈非空时退栈case : ClearStack(S); break; / 重置重置S为空栈为空栈default : Push(S, ch); break; / 有效字符进栈，未考虑栈满有效字符进栈，未考虑栈满ch = getchar(); / 从终端接收下一个字符从终端接收下一个字符将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S); / 重置重置S为空栈为空栈if (ch != EOF) ch = getchar();DestroyStack(S);3.1 栈 3.1.1栈的类型定义 3.1.2

38、顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 25表达式求值表达式求值算符优先法算符优先法 要想对算术表达式求值，首先要能正确解释表达要想对算术表达式求值，首先要能正确解释表达式。比如，按照算术运算规则，表达式式。比如，按照算术运算规则，表达式423105 的计算顺序应为：的计算顺序应为： 4231054610510105 1028 算符优先法就是根据这个运算优先关系的规定来算符优先

39、法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。实现对表达式的编译或解释执行的。 任何一个表达式都是由任何一个表达式都是由操作数操作数(operand)、运算符、运算符(operator)和界限符和界限符(delimiter)组成的。操作数可以是常组成的。操作数可以是常数也可以是被说明为变量或常量的标识符；运算符可以数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等界限符有左右括号和表达式结束符等3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3

40、.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 26表达式求值表达式求值算符优先法算符优先法为了叙述简洁，我们仅讨论表达式中只含有加、为了叙述简洁，我们仅讨论表达式中只含有加、减、乘、除四种运算符，并且操作数都是小于减、乘、除四种运算符，并且操作数都是小于10的整的整数数(这样只需输入一个字符就可以了这样只需输入一个字符就可以了)。我们将运算符和界限符统称为算符，它们构成我们将运算符和界限符统称

41、为算符，它们构成的集合命名为的集合命名为OP。根据算术运算规则，在运算的每。根据算术运算规则，在运算的每一步中，任意两个相继出现的算符一步中，任意两个相继出现的算符1和和2之间的优先之间的优先关系至多有三种：关系至多有三种：12,即即1的优先权高于的优先权高于2 表达式求值表达式求值算符优先法算符优先法+ */()#+-*/(#栈顶运算符，则将其栈顶运算符，则将其压入压入运算符栈；运算符栈；若当前运算符若当前运算符栈顶运算符，则栈顶运算符，则弹出弹出栈顶运算符和栈顶运算符和操作数栈中的相应操作数，完成其运算，并把操作数栈中的相应操作数，完成其运算，并把计算结计算结果压入操作数栈果压入操作数栈中

42、；中；若当前运算符若当前运算符=栈顶运算符，则栈顶运算符，则弹出弹出运算符栈的栈运算符栈的栈顶符号，并顶符号，并读入下一单词读入下一单词，什么计算也不进行。，什么计算也不进行。反复执行上述过程，直至句末符反复执行上述过程，直至句末符“#”，操作数栈中，操作数栈中只剩下一个结果值只剩下一个结果值，表明分析，表明分析正确正确。否则出错处理。否则出错处理。3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3

43、.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 293.2.2 3.2.2 表达式求值表达式求值算符优先分析法（示例）：算符优先分析法（示例）：对对3*(2+5)-6*2的分析的分析输入串输入串:#3*(2+5)-6*2#符号栈符号栈操作数栈操作数栈符号寄存器符号寄存器# 33*(22+55 7) - 21-66*22# 12 9 结果为结果为9输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输

44、入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#输入串输入串:#3*(2+5)-6*2#3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 303.2.2 3.2.2 表达式求值表达式求值Oper

45、andType EvaluateExpression() /算术表达式求值的算符优先算法算术表达式求值的算符优先算法 /设设OPTR和和OPND分别为运算符栈和运算数栈，分别为运算符栈和运算数栈，OP为运算符集合为运算符集合 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while(c!=#|GetTop(OPTR)!=#) if(!In(c,OP) /如果不是运算符则认为是操作数，进如果不是运算符则认为是操作数，进OPND栈栈 Push(OPND,c-0); /真正的操作是真正的操作是c-0，而不是，而不是c c=g

46、etchar(); else GetTop(OPTR,topc); switch(Precede(topc,c) /比较比较OPTR栈顶运算符与栈顶运算符与c的优先权关系的优先权关系 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 313.2.2 3.2.2 表达式求值表达式求值case :/退栈并将运算结果入退栈并将运算结果入OPND栈栈

47、 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch /else /while GetTop(OPND,result); return result; /EvaluateExpression 3. 2 3. 2 栈的应用举例栈的应用举例3.2.6 实现递归实现递归当在一个函数的运行期间当在一个函数的运行期间调用另一个函数调用另一个函数时，在运行该被调时，在运行该被调用函数用函数之前之前，需先完成三件事，需先完成三件事:1.将所有的实在参数、返回地址等将所有的实在参数、返回

48、地址等信息信息传递给被调用函数传递给被调用函数保存保存; 2.为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区; 3.将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。 从被调用函数从被调用函数返回返回调用函数调用函数之前之前，应该完成，应该完成:1.保存保存被调函数的被调函数的计算结果计算结果; 2.释放释放被调函数的被调函数的数据区数据区; 3.依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移控制转移到调用函数。到调用函数。 多个函数嵌套调用的规则是多个函数嵌套调用的规则是:后调用先返回后调用先返回。此时的内存管理此时的内存管理实行实行“栈式管理栈

49、式管理”，递归过程占用的数据区称之为递归过程占用的数据区称之为递归工作栈递归工作栈。每一层的递归参数合成一个记录，称之为每一层的递归参数合成一个记录，称之为递归工作记录递归工作记录。栈顶记栈顶记录指示当前层的执行情况，称之为录指示当前层的执行情况，称之为当前活动记录当前活动记录。栈顶指针，栈顶指针， 称称之为之为当前环境指针当前环境指针。3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的

50、定义3.3.6循环队列3.4几种特殊的线性表 333.2 3.2 栈的应用举例栈的应用举例汉诺塔问题汉诺塔问题b问题：问题：将将X塔座上的塔座上的N个圆盘移动到个圆盘移动到Z塔座上，移动规塔座上，移动规则如下：则如下：1、每次只能移动一个圆盘；、每次只能移动一个圆盘；2、圆盘可插在、圆盘可插在X、Y、Z任意一个塔座上任意一个塔座上3、小圆盘必须在大圆盘之上、小圆盘必须在大圆盘之上3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3

51、.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 343. 2 3. 2 栈的应用举例栈的应用举例b如果只有一个盘，直接从如果只有一个盘，直接从X移动到移动到Z即可即可;b如果有如果有N个盘，就要把个盘，就要把N1个盘先移到个盘先移到Y上，然上，然后就可以把第后就可以把第N个盘移到个盘移到Z上，再把上，再把N1个盘从个盘从Y移到移到Z。void hanoi (int n, char x, char y, char z)/ 将塔座将塔座x上上按直径由小到大且至上而下编号为按直径由小到大且至上而下编号为1至至n的的n个圆盘按规则搬到塔个圆盘按规则搬到塔座座z上

52、，上，y可用作辅助塔座。可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从将编号为的圆盘从x移到移到z3 else hanoi(n-1, x, z, y); / 将将x上编号为至上编号为至n-1的圆的圆盘移到盘移到y, z作辅助塔作辅助塔4 move(x, n, z); / 将编号为将编号为n的圆盘从的圆盘从x移到移到z5 hanoi(n-1, y, x, z); / 将将y上编号为至上编号为至n-1的圆盘移的圆盘移到到z, x作辅助塔作辅助塔 6 3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数

53、制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 35多个栈的设计多个栈的设计两个栈的设计与实现两个栈的设计与实现设有设有m个连续的存储单元，现分成两个栈使用。每个个连续的存储单元，现分成两个栈使用。每个栈的容量不知且不相等。要求在任何时刻，只要两个栈中栈的容量不知且不相等。要求在任何时刻，只要两个栈中 已存储的元素个数之和小于已存储的元素个数之和小于m，便能满足用户的进栈申请。，便能满足用户的进栈申请。其结构如下图所示：其结构如下图所示：0 1

54、 2 3 4 。m-1 top1 top2两个栈上的运算算法自己完成。两个栈上的运算算法自己完成。3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 363.3 3.3 队列队列3.3.1. 定义定义是一种是一种先进先出先进先出的线性表（的线性表（FIFO)，只允许，只允许在表的一端进行插入，另一端进行删除。在表的一端进行插入，另一端进行删除。

55、在队列中，允许插入的一端叫做在队列中，允许插入的一端叫做队尾队尾(rear)，允许删除元素的一端则称为允许删除元素的一端则称为队头队头(front)。假设。假设队列为队列为q=(a1, a2, an)，那么，那么，a1就是队头元素，就是队头元素，an则是队尾元素。当队列中没有任何元素时，则是队尾元素。当队列中没有任何元素时，称为称为“空队列空队列”。 出队列出队列入队列入队列a1a2a3 an队头队头队尾队尾3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列

56、 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 373.3.2 3.3.2 队列的顺序表示和实现队列的顺序表示和实现队列的顺序存储结构称为队列的顺序存储结构称为顺序队列顺序队列，顺序队列实，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两由于队列的队头和队尾的位置是变化的，因而要设两个指针分别指示队头和队尾元素在队列中的位置，它个指针分

57、别指示队头和队尾元素在队列中的位置，它们的队列初始化时均应置为。们的队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元出队时，删去所指的元素，然后将加并返回被删元素。素。由此可见，当头尾指针相等时队列为空。由此可见，当头尾指针相等时队列为空。在非空在非空队列里，头指针始终指向队头元素，而尾指针始终指队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。向队尾元素的下一位置。3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换

58、3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 383.3.2 3.3.2 队列的顺序表示和实现队列的顺序表示和实现队满的标志是队满的标志是rear=m， 队空的标志是队空的标志是rear=front Frontrear(a)队列初始为空队列初始为空cbaFront rear（b）a,b,c入队入队 c b（c) a出队出队front rearfront rear (d) b,c出队，队为空出队，队为空3.1 栈 3.1.1栈的类型定义 3.1.2顺序

59、栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 393.3.3 3.3.3 队列的基本操作队列的基本操作w初始化：初始化：InitQueue(&Q)w注销队列：注销队列：DestroyQueue(&Q)w清空队列：清空队列：ClearQueue(&Q)w入队列：入队列：EnQueue(&Q,e)w出队列：出队列：OutQueue(&Q,&e)

60、w判断是否为空：判断是否为空：QueueEmpty(Q)w取队列头：取队列头：GetHead(Q,&e)w得到队列长度：得到队列长度：QueueLength(Q)w遍历队列：遍历队列：QueueTraverse(Q,visit()3.1 栈 3.1.1栈的类型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应用举例 3.2.1数制转换 3.2.2表达式求值 3.2.3汉诺塔问题 3.3队列 3.3.2顺序队列 3.3.3队列的基本操作 3.3.4队列的类型定义 3.3.5链队列的定义3.3.6循环队列3.4几种特殊的线性表 403.3.4 3.3.4 队列的类型定义队列的类型定义ADT Queue 数据对象：数据对象：Dai | aiElemSet, i=1,2,.,n, n0数据关系：数据关系：R1 | ai-1, ai D, i=2,.,n约定其中约定其中a1 端为队列头，端为队列头，an 端为队列尾。端为队列尾。基本操作：基本操作：In