第三章 栈和队列

通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 栈和队列是两种常用的数据类型

3.1 栈的类型定义 3.2 栈的应用举例 3.3 栈类型的实现 3.4 队列的类型定义 3.5 队列类型的实现

3.1 栈的类型定义 ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack

InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &e) ClearStack(&S) Push(&S, e) Pop(&S, &e) StackTravers(S, visit())

InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。

StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。

StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。

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

ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。

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

Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 a1 a2 … … an-1 an

3.2 栈的应用举例 例一、 数制转换 例二、 括号匹配的检验 例三、 行编辑程序问题 例四、 迷宫求解 例五、 表达式求值 3.2 栈的应用举例 例一、 数制转换 例二、 括号匹配的检验 例三、 行编辑程序问题 例四、 迷宫求解 例五、 表达式求值 例六、 实现递归

例一、 数制转换 算法基于原理： N = (N div d)×d + N mod d

例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 计算顺序 输出顺序

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

例二、 括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 （（）］) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。

分析可能出现的不匹配的情况: 例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待”的； 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧。

算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。

Status matching(string& exp) { int state = 1; while (i<=Length(exp) && state) { switch of exp[i] { case 左括弧:{Push(S,exp[i]); i++; break;} case”)”: { if(NOT StackEmpty(S)&&GetTop(S)=“(“ {Pop(S,e); i++;} else {state = 0;} break; } … … } if (StackEmpty(S)&&state) return OK; …...

例三、行编辑程序问题 如何实现？ “每接受一个字符即存入存储器” ? 并不恰当！

在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。 合理的作法是： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。

假设从终端接受了这样两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行： while (*s) putchar(*s++);

while (ch != EOF) { //EOF为全文结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break;// 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的 数据区； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar();

例四、 迷宫求解 通常用的是“穷举求解”的方法

求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。

求迷宫中一条从入口到出口的路径的算法： 设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； ｝ 否则 { ｝while (栈不空）； … …

若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则｛删去栈顶位置；// 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ｝ 若栈空，则表明迷宫没有通路。

例五、 表达式求值 限于二元运算符的表达式定义: 表达式 ::= (操作数) + (运算符) + (操作数) 操作数 ::= 简单变量 | 表达式 简单变量 :: = 标识符 | 无符号整数

设 Exp = S1 + OP + S2 则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 表达式的三种标识方法： 设 Exp = S1 + OP + S2 则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法

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

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

如何从原表达式求得后缀式？ 分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b  c  d / e  f 后缀式: a b c  + d e / f   每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。

从原表达式求得后缀式的规律为： 1) 设立操作数栈； 2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”； 1) 设立操作数栈； 2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”； 3) 若当前字符是操作数， 则直接发送给后缀式。

从原表达式求得后缀式的规律为： 4) 若当前运算符的优先数高于栈顶运算符，则进栈； 5) 否则，退出栈顶运算符发送给后缀式； 4) 若当前运算符的优先数高于栈顶运算符，则进栈； 5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。

… … void transform(char suffix[ ], char exp[ ] ) { InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S)) { if (!IN(ch, OP)) Pass( Suffix, ch); else { } if ( ch!= # ) { p++; ch = *p; } else { Pop(S, ch); Pass(Suffix, ch); } } // while } // CrtExptree … …

switch (ch) { case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) { Pass( Suffix, c); Pop(S, c) } break; defult : while(Gettop(S, c) && ( precede(c,ch))) { Pass( Suffix, c); Pop(S, c); } if ( ch!= # ) Push( S, ch); } // switch

例六、实现递归 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前， 需先完成三项任务： 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。

依照被调函数保存的返回地址将控制转移到调用函数。 从被调用函数返回调用函数之前，应该完成下列三项任务： 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。

多个函数嵌套调用的规则是： 后调用先返回 ！ 此时的内存管理实行“栈式管理” 例如： void main( ){ void a( ){ void b( ){ … … … a( ); b( ); … … }//main }// a }// b 函数b的数据区 函数a的数据区 Main的数据区

递归函数执行的过程可视为同一函数进行嵌套调用，例如： 递归工作栈：递归过程执行过程中占用的 数据区。 递归工作记录：每一层的递归参数合成 一个记录。 当前活动记录：栈顶记录指示当前层的 执行情况。 当前环境指针：递归工作栈的栈顶指针。

void hanoi (int n, char x, char y, char z) { // 将塔座x上按直径由小到大且至上而下编号为1至n // 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n==1) 2 move(x, 1, z); // 将编号为１的圆盘从x移到z 3 else { 4 hanoi(n-1, x, z, y); // 将x上编号为１至n-1的 //圆盘移到y, z作辅助塔 5 move(x, n, z); // 将编号为n的圆盘从x移到z 6 hanoi(n-1, y, x, z); // 将y上编号为１至n-1的 //圆盘移到z, x作辅助塔 7 } 8 }

void hanoi (int n, char x, char y, char z) { 1 if (n==1) 2 move(x, 1, z); 3 else { 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 } 8 } 7 1 c a b 5 1 a b c 5 2 a c b 8 3 a b c 返址 n x y z

3.3 栈类型的实现 顺序栈 链栈

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。 //----- 栈的顺序存储表示 ----- #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;

} {// 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* Status InitStack (SqStack &S) {// 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }

if (S.top - S.base >= S.stacksize) {//栈满，追加存储空间 Status Push (SqStack &S, SElemType 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;

Status Pop (SqStack &S, SElemType &e) { // 用e返回其值，并返回OK； // 否则返回ERROR if (S.top == S.base) return ERROR; e = *--S.top; return OK; }

链栈 栈顶指针 an an-1 a1 ∧ 注意: 链栈中指针的方向

3.4 队列的类型定义 ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾 基本操作： } ADT Queue

队列的基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, &e) ClearQueue(&Q) EnQueue(&Q, e) DeQueue(&Q, &e) QueueTravers(Q, visit())

InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。

QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。

QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。

GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 … … an

ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。

EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 a1 a2 … … an e

DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 a1 a2 … … an

3.5 队列类型的实现 链队列——链式映象 循环队列——顺序映象

链队列——链式映象 typedef struct QNode {// 结点类型 QElemType data; struct QNode *next; } QNode, *QueuePtr;

typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; … Q.front Q.rear a1 an ∧ Q.front Q.rear 空队列 ∧

(QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); Status InitQueue (LinkQueue &Q) { // 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front->next = NULL; return OK; }

Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; }

if (Q.front == Q.rear) return ERROR; Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) 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; }

循环队列——顺序映象 #define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空， // 指向队列头元素 int rear; // 尾指针，若队列不空，指向 // 队列尾元素 的下一个位置 } SqQueue;

Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); Status InitQueue (SqQueue &Q) { // 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; }

Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; }

if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Status DeQueue (SqQueue &Q, ElemType &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; }

本章学习要点 1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。 　2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。 　3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。 4. 理解递归算法执行过程中栈的状态变化过程。