1、第三章第三章一、栈一、栈2第一节栈第一节栈n栈是限定仅在表尾栈是限定仅在表尾( (top)top)进进行插入或删除操作的线性行插入或删除操作的线性表。表。n允许插入和删除的一端称允许插入和删除的一端称为栈顶为栈顶( (toptop，表尾表尾) )，另一，另一端称为栈底端称为栈底( (bottombottom，表头表头) )n特点：后进先出特点：后进先出 ( (LIFO)LIFO)第章栈和队列第章栈和队列a1topbottoman.进栈进栈 出栈出栈二、栈的实现二、栈的实现3第一节栈第一节栈n栈的存储结构主要有两种：栈的存储结构主要有两种：1. 1. 顺序栈顺序栈2. 2. 链式栈链式栈第章栈和
2、队列第章栈和队列a1topbasean.进栈进栈 出栈出栈top data next栈底栈顶一、顺序栈一、顺序栈4第二节顺序栈第二节顺序栈n顺序栈是栈的顺序存储结构顺序栈是栈的顺序存储结构n利用一组地址连续的存储单元依次利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素存放自栈底到栈顶的数据元素n指针指针toptop指向栈顶元素在顺序栈中的指向栈顶元素在顺序栈中的下一个位置，下一个位置，nbasebase为栈底指针，指向栈底的位置。为栈底指针，指向栈底的位置。第章栈和队列第章栈和队列a1topbasean.进栈进栈 出栈出栈二、顺序栈的定义二、顺序栈的定义5第二节顺表栈第二节顺表栈n采用
3、采用C C语言中动态分配的语言中动态分配的一维数组一维数组表示顺序表表示顺序表第章栈和队列第章栈和队列#define STACK_INIT_SIZE 100/ 栈存储空间的初始分配量#define STACKINCREMENT 10/ 栈存储空间的分配增量Typedef struct SElemType*base/ 栈底指针，也是栈的基址SElemType*top;/ 栈顶指针int stacksize;/ 当前分配的存储容量(元素数) SqStack;三、顺序栈的特性三、顺序栈的特性6第二节顺序栈第二节顺序栈ntop=0 top=0 或或top=base top=base 表示空栈表示空栈n
4、base=NULLbase=NULL表示栈不存在表示栈不存在n当插入新的栈顶元素时当插入新的栈顶元素时, ,指针指针top+1top+1n删除栈顶元素时，指针删除栈顶元素时，指针top-1top-1n当当topstacksizetopstacksize时，栈满，溢出时，栈满，溢出第章栈和队列第章栈和队列a1topbasean.进栈进栈 出栈出栈四、顺序栈的主要操作四、顺序栈的主要操作7第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列nADT Stack 数据对象：D = ai | aiElemSet, i=1,2,3,n 数据关系：R = | ai-1,aiD 基本操作：InitStack(&
5、S)/ 构造空栈 Push(&S, e)/ 进栈 Pop(&S, &e)/ 出栈 GetTop(S, &e)/ 取栈顶元素值StackEmpty(S)/ 栈是否为空 ADT Stack五、创建顺序栈五、创建顺序栈8第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status InitStack(SqStack &S) S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!S.base) exit(OVERFLOW);/ 存储分配失败S.top = S.base;S.stacksize = STACK_INI
6、T_SIZE;return OK; / InitStacktopbase 空栈空栈六、进栈（插入新元素）六、进栈（插入新元素）9第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status Push(SqStack &S, SElemType e) if (S.top S.base = S.stacksize) / 栈满，追加存储空间 S.base = (SElemType *) realloc(S.base, (S.stacksize + STACKINCRMENT* sizeof(SElemType); if (!S.base) exit(OVERFLOW); S.top = S.base
7、 + S.stacksize; S.stacksize += STACKINCRMENT;*S.top+ = e; return OK; / Pushtopbaseeba e进栈进栈topbaseba 操作前操作前七、出栈（删除元素）七、出栈（删除元素）10第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status Pop(SqStack &S, SElemType &e) if (S.top = S.base) return ERROR;e = *-S.top; return OK; / Poptopbaseeba e出栈出栈topbaseeba 操作前操作前八、取栈顶元素八、取栈顶元素1
8、1第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status GetTop(SqStack S, SElemType &e) if (S.top = S.base) return ERROR;e = *(S.top-1); return OK; / GetToptopbaseeba e进栈进栈topbaseeba 操作前操作前一、数值转换一、数值转换( (八进制八进制) )12第三节栈的应用举例第三节栈的应用举例n将十进制转换为其它进制将十进制转换为其它进制( (d)d)，其原理为：其原理为： N = (N/d) N = (N/d)* *d + N mod dd + N mod d例如：（例
9、如：（1348)10 = (2504)8 1348)10 = (2504)8 ，其运算过程如下：，其运算过程如下： N N N /8 N mod 8N /8 N mod 813481348 168 4 168 4 168 168 21 21 0 0 21 21 2 2 5 5 2 2 0 0 2 2第章栈和队列第章栈和队列输出顺序输出顺序计算顺序计算顺序一、数值转换一、数值转换( (八进制八进制) )13第三节栈的应用举例第三节栈的应用举例void conversion () InitStack(S); / 创建新栈S scanf (“%d”,N);/ 输入一个十进制数N while (N)
10、Push(S, N % 8);/ 将余数送入栈中 N = N/8;/ 求整除数 while (!StackEmpty(S) / 如果栈不空 Pop(S,e); / 将栈中数出栈 printf ( %d, e ); / conversion第章栈和队列第章栈和队列二、行编辑程序二、行编辑程序14第三节栈的应用举例第三节栈的应用举例n用户输入一行字符用户输入一行字符n允许用户输入出差错，并在发现有误时，可以允许用户输入出差错，并在发现有误时，可以用退格符用退格符“# #”及时更正及时更正n假设从终端接受两行字符：假设从终端接受两行字符： whli#ilr#ewhli#ilr#e（s#s#* *s)
11、 s) n实际有效行为：实际有效行为： while (while (* *s)s)第章栈和队列第章栈和队列二、行编辑程序二、行编辑程序15第三节栈的应用举例第三节栈的应用举例n对用户输入的一行字符进行处理，直到行结束对用户输入的一行字符进行处理，直到行结束( (“ n n”) )ch = getchar();/ 从终端输入一个字符while (ch != n) switch(ch) case #: Pop(S, c);break; / 仅当栈非空时退栈default: Push(S, ch);break; / 有效字符进栈ch = getchar(); / 从终端输入一个字符将从栈底到栈顶的栈
12、内字符传送到调用过程的数据区;第章栈和队列第章栈和队列三、表达式求值三、表达式求值16第三节栈的应用举例第三节栈的应用举例算术表达式中包含了算术运算符和算术量(常量、变量、函数)，而运算符之间又存在着优先级，不能简单地进行从左到右运算，编译程序在求值时，不能简单从左到右运算，必须先算运算级别高的，再算运算级别低的，同一级运算才从左到右(C+中有些从右到左)。 栈和队列栈和队列因此，要实现表达式求值，必须设置两个栈，一个栈存放运算符，另一个栈存放操作数（算术量），在进行表达式求值时，编译程序从左到右扫描，遇到操作数，一律进入操作数栈，遇到运算符，则应与运算符栈的栈顶比较，若运算符优先级高于栈顶则
13、进栈，否则退栈，退栈后，在操作数栈中退出两个元素(先退出在运算符右，后退出在运算符左)，然后用运算符栈中退出的栈顶元素进行运算，运算的结果存入操作数栈中，直到扫描完毕。这时运算符栈为空，操作数栈中只有一个元素，即为运算的结果。例求表达式1+2*3-4/2的值，栈的变化如下 步骤 操作数栈 运算符栈 说明 开始两栈均为空111进入操作数栈+进入运算符栈2进入操作数栈*进入运算符栈3进入操作数栈退栈2*3进入操作数栈退栈1+6进入操作数栈234567891+12+12+1117+*236+*+步骤 操作数栈 运算符栈 说明 107-进入运算符栈4进入操作数栈/进入运算符栈2进入操作数栈退栈4/2进
14、入操作数栈退栈7-2进入操作数栈111213141516177 4-7 4- /7 4 2- /77 2-5当然，算术表达式除了简单求值外，还会涉及到算术表达式的两种表示方法，即中缀表示法和后缀表示法。刚才的例3-3中的表达式就是中缀表达式，中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律， 例如，对于下列各中缀表达式：（1） 3/5+8（2） 18-9*(4+3)（3） (25+x)*(a*(a+b)+b)对应的后缀表达式为：(1)3 5 / 8 +(2)18
15、9 4 3 + * -(3)25 x + a a b + * b + *2中缀表达式变成等价的后缀表达式中缀表达式变成等价的后缀表达式将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。 将中缀
16、表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。 现在用栈来实现该运算，栈的变化及输出结果如 下步骤栈中元素 输出结果 说明1( （进栈2(1输出13( +1+进栈4( +1 2输出25 1 2 +退栈输出，退栈到（止6*1 2 +*进栈7* (1 2 +（进栈8* ( (1 2 +（进栈9* ( (1 2 + 8输出810* ( ( -1 2 + 8 - 进栈11* ( ( -1 2 + 8 2输出212* (1 2 + 8 2 -退栈输出，退栈到（止13* ( /1 2 + 8 2 -/ 进栈14* ( / (1 2 + 8 2 -（ 进栈15* ( / (1 2 + 8 2
17、 - 7输出716* ( / ( -1 2 + 8 2 - 7- 进栈17* ( / ( -1 2 + 8 2 - 7 4输出418* ( /1 2 + 8 2 - 7 4 -退栈输出，退栈到（止19*1 2 + 8 2 - 7 4 - /退栈输出，退栈到（止20 1 2 + 8 2 - 7 4 - / * *退栈并输出步骤 栈中元素 输出结果 说明3后缀表达式的求值后缀表达式的求值将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，
18、则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。例，求后缀表达式：1 2 + 8 2 - 7 4 - / *的值，栈的变化情如下：步骤栈中元素 说明111进栈21 22进栈3 遇+号退栈2和1431+2=3的结果3进栈53 88进栈63 8 22进栈73遇-号退栈2和883 68-2=6的结果6进栈93 6 77进栈103 6 7 44进栈步骤栈中元素 说明113 6遇-号退栈4和7123 6 37-4=3的结果3进栈133遇/号退栈3和6143 26/3=2的结果2进栈15 遇*号退栈
19、2和31663*2=6进栈176扫描完毕，运算结束从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。一、队列一、队列27第四节队列第四节队列n队列是只允许在表的一端进行插入，而在另一队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。端删除元素的线性表。n在队列中，允许插入的一端叫队尾（在队列中，允许插入的一端叫队尾（rearrear），），允许删除的一端称为对头允许删除的一端称为对头( (front)front)。n特点：先进先出特点：先进先出 ( (FIFO)FIFO)第章栈和队列第章栈和队列a1 a2 a3 an出队出队入队入队队头队尾
20、二、顺序队列二、顺序队列28第四节队列第四节队列n顺序队列：采用一组地址连续的存储单元依次顺序队列：采用一组地址连续的存储单元依次存储从队列头到队列尾的元素存储从队列头到队列尾的元素n顺序队列有两个指针：队头指针顺序队列有两个指针：队头指针frontfront和队尾和队尾指针指针rearrear第章栈和队列第章栈和队列三、顺序队列的进队和出队原则三、顺序队列的进队和出队原则29第四节队列第四节队列n进队时，新元素按进队时，新元素按rearrear指针位置插入，然后队指针位置插入，然后队尾指针增一，即尾指针增一，即 rear = rear + 1rear = rear + 1n出队时，将队头指针
21、位置的元素取出，然后队出队时，将队头指针位置的元素取出，然后队头指针增一，即头指针增一，即 front = front + 1front = front + 1n队头指针始终指向队列头元素队头指针始终指向队列头元素n队尾指针始终指向队列尾元素的下一个位置队尾指针始终指向队列尾元素的下一个位置第章栈和队列第章栈和队列四、顺序队列的进队和出队举例四、顺序队列的进队和出队举例30第四节队列第四节队列第章栈和队列第章栈和队列frontrear空队列frontrearA,B,C,D进队A B C DfrontrearA退队B C DfrontrearB退队C DfrontrearE,F,G进进队C D
22、E F GC D E F GfrontrearH进进队,溢出五、顺序队列存在的问题五、顺序队列存在的问题31第四节队列第四节队列n当队尾指针指向队列存储结构中的最后单元时，当队尾指针指向队列存储结构中的最后单元时，如果再继续插入新的元素，则会产生溢出如果再继续插入新的元素，则会产生溢出n当队列发生溢出时，队列存储结构中可能还存当队列发生溢出时，队列存储结构中可能还存在一些空白位置（已被取走数据的元素）在一些空白位置（已被取走数据的元素）n解决办法之一：将队列存储结构首尾相接，形解决办法之一：将队列存储结构首尾相接，形成循环成循环( (环形环形) )队列队列第章栈和队列第章栈和队列一、循环队列一
23、、循环队列32第五节循环队列第五节循环队列n循环队列采用一组地址连续的存储单元循环队列采用一组地址连续的存储单元n将整个队列的存储单元首尾相连将整个队列的存储单元首尾相连第章栈和队列第章栈和队列C0123456front MAXQSIZE-1DEABCrear二、循环队列空与满二、循环队列空与满33第五节循环队列第五节循环队列nfront = rearfront = rear，循环队列空循环队列空n(rear+1) % MAXQSIZE = front(rear+1) % MAXQSIZE = front，循环队列满循环队列满第章栈和队列第章栈和队列C0123456front MAXQSIZE
24、-1rear队列空CDEFGBCH0123456front MAXQSIZE-1rear队列满三、循环队列定义三、循环队列定义34第五节循环队列第五节循环队列#define MAXQSIZE 100Typedef struct QElemType *base;int front;int rear; SqQueue;第章栈和队列第章栈和队列CDEFC0123456front baserear三、循环队列插入元素三、循环队列插入元素35第五节循环队列第五节循环队列Status EnQueue(SqQueue &Q, QElemType e) if (Q.rear + 1) % MAXQSIZE =
25、 Q.front) return ERROR; /队满队满Q.baseQ.rear = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;第章栈和队列第章栈和队列CDEFGBCH0123456front MAXQSIZE-1rear三、循环队列删除元素三、循环队列删除元素36第五节循环队列第五节循环队列Status DeQueue(SqQueue &Q, QElemType e) if (Q.rear = Q.front) return ERROR; /队空队空e = Q.baseQ.front;Q.front = (Q.front + 1) % MAX
26、QSIZE;return OK;第章栈和队列第章栈和队列C0123456frontrear一、链队列一、链队列37第六节链队列第六节链队列n链队列采用链表存储单元链队列采用链表存储单元n链队列中，有两个分别指示队头和队尾的指针。链队列中，有两个分别指示队头和队尾的指针。n链式队列在进队时无队满问题，但有队空问题。链式队列在进队时无队满问题，但有队空问题。第章栈和队列第章栈和队列data nextfrontrear二、链队列指针变化状况二、链队列指针变化状况38第六节链队列第六节链队列n链队列是链表操作的子集链队列是链表操作的子集第章栈和队列第章栈和队列frontrearxy元素元素y入队入队frontrearxy元素元素x出队出队frontrear空队列空队列
