第3章
栈与队列
所学内容：栈的类型定义；栈的应用举例；栈类型的实现；队列的类型定义；队列类型的实现。
栈、队列和线性表的结构特征一样，而类型不一样，主要是基本操作不一样。
3.1栈的类型定义：
ADT Stack{
数据对象：
D = {a(i) | a(i) ∈ ElemSet, i = 1,2,…..n, n>=0}
数据关系：
R1 = {<a(i-1), a(i)> |
a(i-1), a(i) ∈ D,
i=2,…,n}
约定 a(n)端为栈顶，a(1)端为栈底。
基本操作：
InitStack(&S)
Destroy(&S)
StackEmpty(S) //判栈空
StackLength(S) //求栈长
GetTop(S, &e) //用e 返回S的栈顶元素
ClearStack(&S) //将S清空
Push(&S,e) //插入元素e为新的栈顶元素
Pos(&S, &e) //删除S的栈顶元素，并用e返回其值
}ADT Stack
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);
}
}
例二． 括号匹配的检验
检验括弧是否成对出现。
算法的设计思想：
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()
&& state)
return OK;
else
return ERROR;
}
例三． 行编辑程序问题
如何实现？
“没接受一个字符即存入”？
这样不恰当。
设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。
假设从终端接受了这样两行字符：
whli##ilr#e(s#*s)
outchar @ putchar(*s=#++);
则实际有效的是下列两行：
while(*s)
putchar(*s++);
实现：
while( ch !=
EOF) //EOF为全文结束符
{ while( ch != EOF &&
ch != ‘\0’)
{
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)
Break;
}
例四． 迷宫求解
求迷宫路径算法的基本思想：
1． 若当前位置“可通”，则纳入路径，继续前进
2． 若当前位置“不可通”，则后退，换向探索
3． 若四周均“不可通”，则从路径中删除
求迷宫中一条从入口到出口的路径的算法：
设定当前位置的初值为入口位置；
do{
若当前位置可通，
则{
将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻方块为新的当前位置；
}
否则{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为：沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则
{
删去栈顶位置； //从路径中删去该通道块
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}
}while(栈不空)
例五． 表达式求值
在计算机中，表达式可以有三种不同的标识方法：
设 Exp = S1 + OP + S2
则称 OP + S1 + S2 为表达式的前缀表达式
称 S1 + OP + S2为表达式的中缀表达式
称 S1 + S2 + OP为表达式的后缀表达式
基本思路：
表达式 ----> 后缀表达式 --> 由后缀表达式求值
1． 后缀表达式 -->由后缀表达式求值
当后缀表达式为操作数时，则压栈，
当后缀表达式为操作符时，则将2个操作数出栈，运算后将结果压栈。
2． 表达式 ----> 后缀表达式
从原表达式求得后缀式的规律为：
1)。设立运算符栈
2）。设表达式的结束符为“#”，予设运算符栈的栈底为“#”
3）。若当前字符是操作数，则直接发送给后缀式。
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
{
switch(ch)
{
case ‘(’ : Push(S, ch); break;
case ‘)’:{Pop(S,c);
while(c != ‘(‘)
{
Pass(suffix, c);
Pop(S,c)
}
Break;}
default:{
while(!Gettop(S,c) && (precede(c,ch)))
{
Pass(suffix,c);
Pos(S,c);
}
If( ch != ‘#’) Push(S, ch);
Break;
}
}
if( ch != ‘#’)
{
p++;
ch = *p;
}
}
}
例六． 实现递归
当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先
完成三件事：
1． 将所有的实在参数、返回地址等信息传递给被调用函数保存；
2． 为被调用函数的局部变量分配存储区；
3． 将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该完成：
1． 保存被调用函数的计算结果；
2． 释放被调用函数的数据区；
3． 依照被调用函数保存的返回地址将控制转移到调用函数。
多个函数嵌套调用的规则是：
后调用先返回此时的内存管理实行“栈式管理”
递归过程指向过程中占用的数据区，称之为递归工作栈；
每一层递归参数合成一个记录，称为递归工作记录
栈顶记录指示当前层的执行情况，称为当前活动记录
栈顶指针，称为当前环境指针。
Void hannoi(int
n, char x, char y, char z)
//将塔座x上按直径有小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座
{
If( n==1)
move(x,1,z); //将编号为1的圆盘从x移到z
Else
{
hanoi(n-1,x,z,y); //将x上编号为1至n-1的圆盘移到y, z做辅助塔
move(x,n,z); //将编号为n的圆盘从x移到z
Hanoi(n-1,y,x,z); //将y上编号为1至n-1的圆盘移到z，x做辅助塔
}
}
3.3栈类型的实现（顺序栈，链栈）
1．顺序栈：
类型于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针
#define
STACK_INIT_SIZE 100
#define
STACKINCREMENT 10
typedef
struct{
SElemType* base;
SElemType* top;
Int stacksize;
}SqStack;
2.链栈：
N --> n-1-->。。。。。。。--> 2 --> 1
总是在栈顶插入新的数据元素，注意与单链表指针方向的区别。
