数据结构栈和队列.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)
栈的类型定义
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
栈的应用举例
例一、数制转换
十进制数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

这是利用栈的后进先出特性的最简单的例子。在这个例子中,栈操作的序列是直线式的,即先一味地入栈,然后一味地出栈。也许,有的读者会提出疑问:用数组直接实现不也很简单吗?仔细分析上述算法不难看出,栈的引入简化了程序设计的问题,划分了不同的关注层次,使思考范围缩小了。而用数组不仅掩盖了问题的本质,还要分散精力去考虑数组下标增减等细节问题。
例二、括号匹配的检验
假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([ ][ ])]等为正确的格式,[( ])或([( ))或(( )])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列:
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的不匹配的情况:
到来的右括弧非是所“期待”的;
到来的是“不速之客”;
直到结束,也没有到来所“期待”的。
status matching(string& exp) {
// 检验表达式中所含括弧是否正确嵌套,若是,则返回
// OK,否则返回ERROR
int state = 1;
while (i<=length(exp) && state) {
swith of exp[i] {
case 左括弧: { Push(S,exp[i]); i++; break; }
case ")":
{ if (