第三章 栈与队列 ￡3.1 栈 ￡3.3 队列 ￡3.2 栈的应用举例 ￡3.1.1 栈的定义 ￡3.1.2 栈的顺序存储结构

Presentation on theme: "第三章 栈与队列 ￡3.1 栈 ￡3.3 队列 ￡3.2 栈的应用举例 ￡3.1.1 栈的定义 ￡3.1.2 栈的顺序存储结构"— Presentation transcript:

1 第三章 栈与队列 ￡3.1 栈 ￡3.3 队列 ￡3.2 栈的应用举例 ￡3.1.1 栈的定义 ￡3.1.2 栈的顺序存储结构
第三章 栈与队列 ￡3.1 栈 ￡3.1.1 栈的定义 ￡3.1.2 栈的顺序存储结构 ￡3.1.3 栈的链式存储结构 ￡3.3 队列 ￡3.3.1 队列的定义 ￡3.3.2 队列的顺序存储结构 ￡3.2 栈的应用举例 ￡3.3.3 队列的链式存储结构 ￡3.2.1 数制转换 ￡3.2.2 括号匹配检验 ￡3.2.3 行编辑程序 ￡3.2.4 迷宫求解 ￡ 表达式求值

2 ￡3.1 栈 ￡3.1.1 栈的定义 栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。又称为后
进先出（last in first out）的线性表（简称LIFO结构）。 栈顶（top）：栈表尾端。 栈底（bottom）：栈表头端。 例：假设栈 ，则 称为栈底元素， 为栈顶元素。栈中元 素按 的次序进栈，退栈的第一个元素应为栈顶元素。如图3.1所示。 出栈 进栈 栈顶 an . a2 栈底 a1 图3.1 栈的示意图

3 ￡3.1.2 栈的顺序存储结构 （1）定义 顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放
自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。 （2）C语言描述 typedef struct { SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈当前可使用的最大容量。 }SqStack; （3）图形表示 top E D C top B top base A base A base 图3.2 栈的顺序存储结构示意图

4 （4）ADT Stack的表示和实现 #define STACK_INIT_SIZE 100; //存储空间初始分配量 #define STACKINCREMENT 10; //存储空间分配增量 typedef struct { SElemType *base; //在构造之前和销毁之后， //base的值为NULL SElemType *top; //栈顶指针 int stacksize; //栈当前可使用的最大容量。 }SqStack; // 基本操作的函数原型说明 Status InitStack (SqStack &S); //构造一个空栈S Status DestroyStack (SqStack &S); //销毁栈S，栈S不再存在 Status ClearStack (SqStack &S); //把S置为空栈 Status StackEmpty (SqStack S); //若S为空栈，则返回TRUE，否则返回FALSE Status StackLength (SqStack S); //返回S的元素个数，即栈的长度

5 Status GetTop (SqStack S, SElemType &e);
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR Status Push (SqStack &S, SElemType e); //插入元素e为新的栈顶元素 Status Pop (SqStack &S, SElemType &e); //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status StackTraverse (SqStack S, Status (*visit) () ); //从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败 // 基本操作的算法描述（部分） Status InitStack (SqStack &S) { //构造一个空栈S S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } //InitStack

6 Status GetTop (SqStack S, SElemType &e) {
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if (S.top = = S.base) return ERROR; e = *(S.top－1); return OK; } // GetTop Status Push (SqStack &S, SElemType e) { //插入元素e为新的栈顶元素 if (S.top－S.base >= S.stacksize) { //栈满，追加存储空间 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } * S.top + + = e; return OK; } //Push

7 Status Pop (SqStack &S, SElemType &e) {
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK； //否则返回ERROR if (S.top = = S.base) return ERROR; e = *――S.top; return OK; } //Pop

8 ￡3.1.3 栈的链式存储结构 data next S 栈顶 ^ 栈底 图3.3 链栈示意图

9 ￡3.2 栈的应用举例 ￡3.2.1 数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决
方法很多，其中一个简单算法基于下列原理： N = ( N div d ) × d + N mod d （其中：div为整除运算，mod为求余运算） 例如：(1348)10＝(2504)8，其运算过程如下： N N div N mod 8 由于上述计算过程是从低位到高位顺序产生八进制数的 各个数位，而打印输出，一般来说应从高位到低位进行，恰 好和计算过程相反。因此，若计算过程中得到八进制数的各 位顺序进栈，则按出栈序列打印输出的即为与输入对应的八 进制数。

10 算法3.1如下： 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

11 ￡3.2.2 括号匹配检验 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套
的顺序随意，即( [ ] ( ))或[( [ ] [ ]) ]等为正确的格式，[ ( ] )或[ ( ) ) 或( ( ) ] )均为不正确的格式。检验括号是否匹配的方法可用“期待 的急迫程度”这个概念来描述。例如： [ ( [ ] [ ] ) ] 当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号“[”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号”)”的 出现，类似的，因等来的是第三个括号“[”，其期待匹配的程度较 第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依次类推。可见，这个处理过程恰与栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。

12 ￡3.2.3 行编辑程序 功能：接受用户从终端输入的程序或数据，并存入用户的数据区。 退格符“#”：表示前一个字符无效。
例如： whli # # ilr # e(s # *s) (*s = # ++); 等效为： while (* s) putchar (*s ++); 为了提高程序的效率，我们设立一个输入缓冲区， 用以接受用户输入的一行字符，然后逐行存入用户数 据区。在此，将这个输入缓冲区设为一个栈结构，每 当从终端接受了一个字符之后先作如下判断： ①如果它既不是退格符也不是退行符，则将该字符 压入栈顶； ②如果是一个退格符，则从栈顶删去一个字符； ③如果它是一个退行符，则将字符栈清为空栈。

13 void LineEdit { //利用字符栈S，从终端接收一行并传送至调用过程的数据区。 InitStack (S); //构造空栈S ch = getchar (); //从终端接收第一个字符 while (ch != EOF) { //EOF为全文结束符 while (ch != EOF && ch ! = ‘\n’) { switch (ch) { case ‘#’:Pop (S, c); break; //仅当栈非空时退栈 (S); break; //重置S为空栈 default:Push (S, ch); break; //有效字符进栈， //未考虑栈满情况 } ch = getchar ( ); //从终端接收下一个字符 将从栈底到栈顶的栈内字符传送至调用过程的数据区； ClearStack (S); //重置S为空栈 if (ch != EOF) ch = getchar ( ); DestroyStack (S); } //LineEdit 算法3.2如下：

14 ￡3.2.4 迷宫求解 入口 0 1 2 3 4 5 6 7 8 9 空白方块：表示通道。 带阴影线的方块：表示墙。 出口 图3.4 迷宫
空白方块：表示通道。 带阴影线的方块：表示墙。 出口 图3.4 迷宫 当前位置：指在搜索过程中某一时刻所在图中某个方块位置。 下一位置：指“当前位置”四周4个方向（东、南、西、北） 上相邻的方块。 当前位置可通：指未曾走到过的通道块。即要求该方块位置不仅 是通道块，而且既不在当前路径上，也不是曾经 纳入过路径的通道块。

15 求迷宫中一条从入口到出口的路径的算法可简单描述如下：
设定当前位置的初值为入口位置； do { 若当前位置可通， 则{ 将当前位置插入栈顶； //纳入路径 若该位置是出口位置，则结束； //求得路径存放在栈中 否则切换当前位置的东阾方块为新的当前位置； } 否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； //从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； }while(栈不空)；

16 typedef struct { int ord; //通道块在路径上的“序号” PosType seat; //通道块在迷宫中的“坐标位置” int di; //从此通道块走向下一通道块的“方向” }SElemType； //栈的元素类型 Status MazePath (MazeType maze, PosType start, PosType end) { //若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中 //（从栈底到栈顶），并返回TRUE，否则返回FALSE InitStack (S); curpos = start; //设定“当前位置”为“入口地址” curstep = 1; //探索第一步 do { if (Pass (curpos)) { //当前位置可以通过，即是未曾走到过的通道块 FootPrint (curpos); //留下足迹 e = (curstep, curpos, 1); Push (S, e); //加入路径 if (curpos = = end) return (TRUE); //到达终点（出口） curpos = NextPos (curpos, 1); //下一位置是当前位置的东阾 curstep++; //探索下一步 } //if 算法3.3如下：

17 else { //当前位置不能通过 if (!StackEmpty (S)) { Pop (S, e); while (e.di = = 4 && !StackEmpty (S)) { MarkPrint (e.seat); //留下不能通过的标记，并退回一步 } //while if (e.di < 4) { e.di++; //换下一个方向探索 Push (S, e); curpos = NextPos (e.seat, e.di); //设定当前位置是该新方向上 //的相邻块 } // if } // else } while (!StackEmpty (S)); return (FALSE); } // MazePath

18 ￡3.2.5 表达式求值 算法3.4如下： OperandType EvaluateExpression ( ) {
￡ 表达式求值 算法3.4如下： OperandType EvaluateExpression ( ) { //算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和 //运算数栈，OP为运算符集合。 InitStack (OPTR); Push (OPTR, ‘#’); InitStack (OPND); c = getchar ( ); while (c != ‘#’ | | GetTop(OPTR) != ‘#’) { if (!In (c, OP)) { //不是运算符则进栈 Push (OPND, c); } else switch (Precede (GetTop (OPTR), c)) { // Precede是判定运算符栈的栈顶运算符 与读入 //的运算符 之间优先关系的函数。

19 case ‘<’: //栈顶元素优先权低
Push (OPTR, c); c = getchar ( ); break; case ‘=’: //脱括号并接收下一字符 Pop (OPTR, x); case ‘>’: //退栈并将运算结果入栈 Pop (OPTR, theta); Pop (OPND, b); Pop (OPND, a); Push (OPND, Operate (a, theta, b)); // Operate为进行二元运算aθb的函数。 } // switch } // while return GetTop (OPND); } // EvaluateExpression

20 例如：利用上述算法对表达式3*(7－2)求值的操作过程如下所示：
步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 3*(7-2) # Push (OPND, ‘3’) 2 # *(7-2) # Push (OPTR, ‘*’) 3 #* (7-2) # Push (OPTR, ‘(’) 4 #*( ) # Push (OPND, ‘7’) 5 #*( ) # Push (OPTR, ‘-’) 6 #*( ) # Push (OPND, ‘2’) 7 #*( ) # operate (‘7’, ‘-’, ‘2’) 8 #*( ) # Pop (OPTR) {消去一对括号} 9 #* # operate (‘3’, ‘*’, ‘5’) 10 # # return (GetTop(OPND))

21 ￡3.3 队列 ￡3.3.1 队列的定义 队列（queue）：是一种先进先出（first in first out，缩写为FIFO）的线性表。 它只允许在表的一端进行插入，而在另一端删除元素。 队头（front）：在队列中允许删除元素的一端。 队尾（rear）：在队列中允许插入元素的一端。 出队列 入队列 … 队头 队尾 图3.5 队列示意图

22 ￡3.3.2 队列的顺序存储结构 （1）定义 队列的顺序存储结构：是利用一组地址连续的存储单元
依次存放从队列头到队列尾的数据元素，同时附设指针front 和rear分别指示队列头元素及队列尾元素的位置。 （2）图形表示 Q.rear 5 4 3 2 1 J6 J5 尾指针总是指向队列尾元素的下一 位置 Q.front Q.rear Q.rear J3 J2 J1 Q.front J3 Q.rear Q.front Q.front (a) (b) (c) (d) 头指针总是指向队列头元素 图3.6 队列的顺序存储结构示意图 (a)空队列 (b) J1、J2和J3相继入队列 (c) J1和J2相继被删除 (d) J4、J5和J6相继插入队列之后J3和J4被删除

23 （3）循环队列满和空的判断： 图3.7 循环队列示意图 (a) 一般情况 (b)队列满时 图3.8 循环队列满、空示意图 (c)空队列
maxsize-1 Q.rear 1 Q.front （3）循环队列满和空的判断： 队列 Q.rear 图3.7 循环队列示意图 4 2 1 3 5 4 2 1 3 5 Q.front (a) 一般情况 Q.front Q.rear Q.front (b)队列满时 Q.rear 4 2 1 3 5 图3.8 循环队列满、空示意图 (c)空队列

24 （4）循环队列类型的模块说明 // 循环队列——队列的顺序存储结构 #define MAXQSIZE //最大队列长度 typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针,若队列不空,指向队列头元素 int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置 } SqQueue; // 循环队列的基本操作的算法描述 Staus InitQueue (SqQueue &Q) { //构造一个空队列Q Q.base = (QElemType*) malloc (MAXQSIZE * sizeof(QElemType)); if (!Q.base) exit (OVERFLOW); //存储分配失败 Q.front = Q.rear = 0; return OK; }

25 int QueueLength (SqQueue Q) {
return (Q.rear – Q.front + MAXQSIZE) % MAXQSIZE; } Staus EnQueue (SqQueue &Q, QElemType e) { //插入元素e为Q的新的队尾元素 if ((Q.rear + 1) % MAZQSIZE = = Q.front) return ERROR; //队列满 Q.base [Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return OK; } Staus DeQueue (SqQueue &Q, QElemType &e) { //若队列不空，则删除Q的队头元素，用e返回其值， //并返回OK；否则，返回ERROR。 if (Q.front = = Q.rear) return ERROR; //队列空 e = Q.base [Q.front] ; Q.front = (Q.front + 1) % MAXQSIZE; return OK; }

26 ￡3.3.3 队列的链式存储结构 （1）定义 链队列：用链表表示的队列。 data next （2）图形表示 头结点（为了运算方便）
Q.front 头结点（为了运算方便） 队头（删除运算从此处开始） Q.rear 队尾（插入运算从此处开始） 图3.9 链队列示意图

27 Q.front = Q.rear; 即，头指针和尾指针都指向头结点。
（3）队列空的判决条件 Q.front = Q.rear; 即，头指针和尾指针都指向头结点。 （4）几种基本运算 链队列的操作即为单链表的插入和删除操作的特殊情况， 只是尚需修改尾指针或头指针。图3.10展示了这两种操作进行 时指针变化的情况。 Q.front Q.front x Q.rear Q.rear (b) 元素x入队列 (a) 空队列 Q.front x y Q.rear (c) 元素y入队列

28 //-------------单链队列——队列的链式存储结构------------ typedef struct QNode {
x y Q.front Q.rear (d) 元素x出队列 图3.10 队列运算指针变化情况 （5）ADT Quene的表示和实现 // 单链队列——队列的链式存储结构 typedef struct QNode { QElemType data; struct QNode *top; } QNode, *QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 } LinkQueue;

29 //-------------------基本操作的函数原型说明----------------------
Status InitQueue (LinkQueue &Q); //构造一个空队列Q Status DestroyQueue (LinkQueue &Q); //销毁队列Q，Q不再存在 Status ClearQueue (LinkQueue &Q); //把Q清为空队列 Status QueueEmpty (LinkQueue Q); //若队列Q为空队列，则返回TRUE，否则返回FALSE Status QueueLength (LinkQueue Q); //返回Q的元素个数，即为队列的长度 Status GetHead (LinkQueue Q, QElemType &e); //若队列不空,则用e返回Q的队头元素,并返回OK; //否则返回ERROR Status EnQueue (LinkQueue &Q, QElemType e); //插入元素e为Q新的队尾元素 Status DeQueue (LinkQueue &Q, QElemType &e); //若队列不空，则删除Q的队头元素，用e返回其值， //并返回OK；否则返回ERROR Status QueueTraverse (LinkQueue Q, visit () ); //从队头到队尾依次对队列Q中每个元素调用函数visit()。 //一旦visit()失败，则操作失败

30 //-------------------基本操作的算法描述（部分）---------------------
Status InitQueue (LinkQueue &Q) { //构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front－>next = NULL; return OK; } //InitQueue Status DestroyQueue (LinkQueue &Q) { //销毁队列 while (Q.front) { Q.rear = Q.front－>next; free (Q.front); Q.front = Q.rear; } return OK; } // DestroyQueue

31 Status EnQueue (LinkQueue &Q, QElemType e) {
p = (QueuePtr) malloc (sizeof (QNode) ); if (!p) exit (OVERFLOW); //存储分配失败 p－>data = e; p－>next = NULL; Q.rear－>next = p; Q.rear = p; return OK; } // EnQueue Status DeQueue (LinkQueue &Q, QElemType &e) { //若队列不空,则删除Q的队头元素,用e返回其值, //并返回OK;否则返回ERROR if (Q.front = = Q.reat) 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; } // DeQueue