第三章 栈和队列
栈和队列是两种重要的线性结构。
从数据结构上看，栈和队列也是线性表，不过 是两种特殊的线性表。
栈只允许在表的一端进行插入或删除操作。
队列只允许在表的一端进行插入操作、而在另 一端进行删除操作。
因而，栈和队列也可以被称作为操作受限的线 性表。
栈和队列的插入、删除操作与线性表 的插入、删除操作的比较：
…
S.base S.top
S.stacksize
(栈底) (栈顶)
Status Push (SqStack &S, ElemType e) {
if (S.top - S.base >= S.stacksize) {//栈满，追加存储空间
S.base = (ElemType *) realloc ( S.base,
例二、 括号匹配的检验
假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 （（）］) 均为不正确的格式。 则 检验括号是否匹配的方法可用“期待的急迫程度 ”这个概念来描述。
例如：考虑下列括号序列： [( [ ][ ] )] 1 2 34 5 6 7 8
a1 a2
…
an e …
}
S.base
S.topS.top
Status Pop (SqStack &S, ElemType &e) {
// 若栈不空，则删除S的栈顶元素，
// 用e返回其值，并返回OK；
// 否则返回ERROR
if (S.top == S.base) return ERROR;
e = *--S.top;
算法见教材 P.53
算法的计算过程: 以表达式: 5+(6-4/22))*33# 为例
/
2
-
342
(*
4 / 2 =2
1642
+
6 - 2 =4
157
#
4 * 3 =12
OPRD
OPTR
5 + 12=17
运算符栈栈顶运算符的优先权?当前运算符的优先权
(运算符间的优先关系请看教材P.53)
1)若为“<”，则将当前运算符压入运算符栈，并依次读 下一个元素。
根据栈的定义可知，栈顶元素总是最后入栈的， 因而是最先出栈；栈底元素总是最先入栈的，因而也 是最后出栈。这种表是按照后进先出（LIFO）的原则 组织数据的，因此，栈也被称为“后进先出”的线性 表。
栈的示意图：
出栈
栈顶
an
top
a2
栈底
a1
bottom
…
入栈 若输入序列是1,2,3，
则可能的输出序列有
(S.staeof (ElemType));
if (!S.base) exit (OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
} *S.top++ = e; return OK;
Status matching(string exp) { m= Length(exp) ; i=0; state = 1; while (i<m&& state) {
switch exp[i] { case 左括弧:{Push(S,exp[i]); i++; break;} case ’)’: { if(!StackEmpty(S)&&GetTop(S)== ’(’) {Pop(S,e); i++;} else state = 0; break; } …… }
计 1348 168
4
算
168 21
0
输 出
顺
21 2
5
顺
序
20
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
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; }
哪些？ 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1
栈的应用
在各种程序设计语言中都有子程序（或称函数、过 程）调用功能。而子程序也可以调用其它的子程序，甚 至可以直接或间接地调用自身，即递归。
下面以求阶乘的递归方法为例，来分析计算机系
统是如何处理这种递归调用关系的。
求n！的递推公式：
输出 s=120.00
第一层调用
n=5 s=5*fact(4)
fact(5) =120
第二层调用
n=4 s=4*fact(3)
fact(4) =24
每一次递归调用并未立即得到
结果，而是进一步向深度递归
调用，直到n=1或n=0时，函数 fact才有结果为1，然后再一一 返回计算，最终得到结果。
第三层调用
3.1.3 栈的应用举例
例一、 数制转换 例二、 括号匹配的检验 例三、 表达式求值
例一、 数制转换
十进制数N和其他d进制数的转换算法基于以 下原理：
N = (N div d)×d + N mod d
例如： （1348)10 = (2504)8 ，其运算过程如下：
N N div 8 N mod 8
if (StackEmpty(S)&&state) return TRUE; else return FALSE; }
例三、 表达式求值(算符优先算法)
表达式求值是程序设计语言编译中的一 个最基本问题。它的实现方法是栈的一个典 型的应用实例。
算术四则运算的规则为： （1）先乘除、后加减； （2）同级运算时先左后右； （3）先括号内，后括号外。
} 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)
相应的算法：
n!
n
1 (n 0,1) * (n 1)! (n 1)
float fact(int n)
{ if (n==0||n==1) s=1;
else s=n*fact(n-1);
return s; }
若求5!，递归调用执行过程：
主函数 mani() printf(“fact(5)”)
n=3 s=3*fact(2)
fact(3) =6
第四层调用
n=2 s=2*fact(1)
fact(2) =2
第五层调用
n=1 s=1
fact(1) =1
计算机系统处理上述过程时，其关键是要正确处理 执行过程中的递归调用层次和返回路径，也就是要记住 每一次递归调用时的返回地址。在系统中用一个线性表 动态记忆调用过程中的路径，其处理原则为：
线性表 Insert(L, i, x) 1≤i≤n+1 Delete(L, i, x)
1≤i≤n
栈 Insert(S, n+1, x)
Delete(S, n, x)
队列 Insert(Q, n+1, x)
Delete(Q, 1, x)
3.1 栈
栈（stack）是一种只允许在一端进行插入和删 除的线性表，它是一种操作受限的线性表。在表中只 允许进行插入和删除的一端称为栈顶（top），另一 端称为栈底(bottom)。栈的插入操作通常称为入栈或 进 栈 (push) ， 而 栈 的 删 除 操 作 则 称 为 出 栈 或 退 栈 (pop)。当栈中无数据元素时，称为空栈。
假定表达式语法正确，且以“#”结束。
表达式求值的算符优先算法描述如下：
1.初始化操作数栈和运算符栈，置表达式起始符“#”为 运算符栈的栈底元素； 2.从左到右依次读出表达式中的各个元素(操作数或运 算符)，每读出一个元素后，根据运算规则作如下的处 理： (1)如果是操作数，则将其压入操作数栈，并依次读下 一个元素。 (2)如果是运算符，则和运算符栈的栈顶运算符比较优 先权后作相应操作，直至整个表达式求值完毕（即运算 符栈的栈顶运算符和当前读入的元素均为“#”）。最后 的表达式的计算结果在操作数栈的栈顶位置。
54 5 4321
——该线性表就是栈
[栈]提要 3.1.1 栈的类型定义 3.1.2 栈类型的实现 3.1.3 栈的应用举例
3.1.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 端为栈底。 基本操作：