文档介绍：第三章栈与队列
￡ 栈
￡ 栈的定义
￡ 栈的顺序存储结构
￡ 栈的链式存储结构
￡ 栈的应用举例
￡ 表达式求值
￡ 迷宫求解
￡ 数制转换
￡ 括号匹配检验
￡ 行编辑程序
￡ 队列的顺序存储结构
￡ 队列
￡ 队列的定义
￡ 队列的链式存储结构
￡ 栈的定义
￡ 栈
栈(stack):是限定仅在表尾进行插入和删除操作的线性表。又称为后
进先出(last in first out)的线性表(简称LIFO结构)。
栈顶(top):栈表尾端。
栈底(bottom):栈表头端。
例:假设栈,则称为栈底元素, 为栈顶元素。栈中元
素按的次序进栈,退栈的第一个元素应为栈顶元素。。
出栈进栈
栈顶 an
.
.
.
a2
栈底 a1
栈的示意图
￡ 栈的顺序存储结构
(1)定义
顺序栈(即栈的顺序存储结构):是利用一组地址连续的存储单元依次存放
自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。
(2)C语言描述
typedef struct {
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈当前可使用的最大容量。
}SqStack;
(3)图形表示
top
base
top
base
top
base
A
A
B
C
D
E
栈的顺序存储结构示意图
(4)ADT Stack的表示和实现
#define STACK_INIT_SIZE 100; //存储空间初始分配量
#define STACKINCREMENT 10; //存储空间分配增量
typedef struct {
SElemType *base; //在构造之前和销毁之后,
//base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //栈当前可使用的最大容量。
}SqStack;
//-----------------基本操作的函数原型说明------------------
Status InitStack (SqStack &S);
//构造一个空栈S
Status DestroyStack (SqStack &S);
//销毁栈S,栈S不再存在
Status ClearStack (SqStack &S);
//把S置为空栈
Status StackEmpty (SqStack S);
//若S为空栈,则返回TRUE,否则返回FALSE
Status StackLength (SqStack S);
//返回S的元素个数,即栈的长度
Status GetTop (SqStack S, SElemType &e);
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
Status Push (SqStack &S, SElemType e);
//插入元素e为新的栈顶元素
Status Pop (SqStack &S, SElemType &e);
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
Status StackTraverse (SqStack S, Status (*visit) () );
//从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败,则操作失败
//-----------------基本操作的算法描述(部分)------------------
Status InitStack (SqStack &S) {
//构造一个空栈S
= (SElemType *)malloc(STACK_INIT_SIZE
* sizeof(ElemType));
if (!)
exit (OVERFLOW); //存储分配失败
= ;
= STACK_INIT_SIZE;
return OK;
} //InitStack
Status GetTop (SqStack S, SElemType &e) {
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
if ( = = )
return ERROR;
e = *(-1);
return