１
引言
栈是数据结构一类重要的抽象数据类型
，
本
文对
“
栈
”
的概念以及
“
栈
”
在
“
迷宫
”
程序中的应用
和实现作了一些论述
，
从中我们可以看出如何利
用
“
栈
”
建立良好的算法以及利用
ＶＢ
语言实现程
序的设计
。
栈是一种特殊的线性表
，
这种线性表只能在
表的一端
（
表头
）
进行插入和删除操作
。
通常称插
入
、
删除的这一端为栈顶
（
Ｔｏｐ
） ，
另一端称为栈底
（
Ｂｏｔｔｏｍ
） 。
假设一个栈
Ｓ
中的元素为
ａ
ｎ
，ａ
ｎ－１
，．．，ａ
１
，
则
称
ａ１
为栈底元素
，
ａ
ｎ
为栈顶元素
。
栈中的元素按
ａ
１
，ａ
２
，．．，ａ
ｎ－１
，ａ
ｎ
的次序进栈
，
而任何时候出栈的元素
都是栈顶元素
，
即最后插入
（
进栈
）
的元素
，
而最先
插入的被放在栈的底部
，
要到最后才能删除
，
所以
按
ａ
ｎ
，ａ
ｎ－１
，．．，ａ
１
的次序出栈
。
换句话说
，
栈的修改是
按后进先出的原则进行的
。
因此
，
栈被称为后进先
出
（Ｌａｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）
表
，
简称为
ＬＩＦＯ
表
。
所以
，
只
要问题满足
ＬＩＦＯ
原则
，
就可以使用栈
。
图
１
示意了栈的操作
。
２
栈的表示方法
２．１
顺序栈
顺序栈
，
即栈的顺序存储结构
，
是利用一组地
址连续的存储单元依次存放自栈底到栈顶的数据
元素
，
同时附设指针
ｔｏｐ
指示栈顶元素在顺序栈中
的位置
。
通常的做法是以
ｔｏｐ＝０
表示空栈
，
当以
ＶＢ
作描述语言时
，
指定数组下标从
０
开始
，
而
０
号单
元不用即可
，
并以下述自定义类型作为顺序栈的
定义
。
Ｔｙｐｅ ｚｈａｎ
Ｔｏｐ ａｓ ｉｎｔｅｇｅｒ
Ｂａｓｅ ａｓ ｉｎｔｅｇｅｒ
Ｓｔａｃｋ （ｎ） ａｓ ｊｄｔｙｐｅ
Ｅｎｄ ｔｙｐｅ
其中
Ｓｔａｃｋ（ ）
数组的元素为另一自定义类型
ｊｄｔｙｐｅ ； Ｂａｓｅ
可称为栈底指针
（
实际上在
ＶＢ
中是
不存在指针的概念的
） ，
在顺序栈中
，
它始终指向
栈底的位置
（
在
ＶＢ
中以
Ｂａｓｅ
的值为栈底元素的
下标来实现
） 。
Ｔｏｐ
为栈顶指针
，
其初值指向栈底
（
实现方法同
Ｂａｓｅ）
，
即
ｔｏｐ＝ｂａｓｅ
可以作为栈空的标
记
，
每当插入新的栈顶元素时
，
指针
ｔｏｐ
增
１
，
删除
栈顶元素时
，
指针
ｔｏｐ
减
１
，
因此
，
非空栈中的栈顶
指针始终在栈顶元素的下一个位置上
。
图
２
展示了顺序栈中数据元素和栈顶指针之
间的对应关系
。
栈空 元素
Ａ
入栈 栈满 元素
Ｅ
，
Ｄ，Ｃ
出栈
图
２
栈顶指针和栈中元素之间的关系
２．２
链式栈
由于栈是操作受限的线性表
，
因此链栈的操
作是易于实现的
，
图
３
即为链栈示意图
。
［
收稿日期
］２００６－ １２－ １２
［
作者简介
］
井田
（
１９８０
—） ，
女
，
安徽淮南人
，
淮南师范学院物理系助教
。
栈在“迷宫问题”算法中的应用和实现
井田
（
淮南师范学院 物理系
，
安徽 淮南
２３２００１
）
［
摘 要
］
文章论述了数据结构中栈的理论知识和应用栈解决迷宫问题的算法设计
，
并用
ＶＢ
实现
了迷宫程序的设计
。
［
关键词
］
栈
；
路径
；
算法
［
中图分类号
］ＴＰ３１１ ［
文献标识码
］ Ａ ［
文章编号
］ １００９－ ９５３０
（
２００７
）
０３－ ０１３０－ ０３
淮南师范学院学报
ＪＯＵＲＮＡＬ ＯＦ ＨＵＡＩＮＡＮ ＴＥＡＣＨＥＲＳ ＣＯＬＬＥＧＥ
２００７
年第
３
期
第
９
卷
（
总第
４３
期
）
Ｎｏ． ３， ２００７
Ｇｅｎｅｒａｌ Ｎｏ． ４３， Ｖｏｌ．９
图
１
