第三章栈和队列要点讲解.doc
文本预览下载声明
栈和队列
从数据结构的角度看: 它们和线性表相同
从数据类型的角度看: 它们和线性表不同
线性表 栈 队列
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 栈的类型定义
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 端为栈底。
基本操作：
InitStack(S)
操作结果：构造一个空栈S。
DestroyStack(S)
初始条件：栈S已存在。
操作结果：栈S被销毁。
ClearStack(S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALE。
StackLength(S)
初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
GetTop(S, e)
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push(S, e)
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(S, e)
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
} ADT Stack
3.2 栈的应用举例
例一、 数制转换
十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N = (N div d)×d + N mod d
(其中：div 为整除运算，mod 为求余运算）
例如：（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
这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。
例二、 括号匹配的检验
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［ ］［ ］）］等为正确的格式，［（ ］）或（［（ ））或 (( )])均为不正确的格式。检验括号是否匹配的方法可用期待的急迫程度这个概念来描述。例如考虑下列括号序列：
[ (
显示全部