文档介绍：第三章栈和队列
栈
抽象数据类型栈的定义
栈的表示和实现
栈的应用举例
数制转换
括号匹配的检验
行编辑程序
* 迷宫求解
表达式求值
6/29/2017
栈
栈的定义及基本运算
栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。
假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,3,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。
6/29/2017
顺序栈
由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点;栈顶位置是随着进栈和退栈操作而变化的,故需用一个整型变量top
6/29/2017
例、一叠书或一叠盘子。
栈的抽象数据类型的定义如下:P44
a1
a2
a n-1
a n
……
栈顶
栈底
6/29/2017
-1
top
7 6 5 4 3 2 1
base
6/29/2017
A
B
-1
top
7 6 5 4 3 2 1
base
6/29/2017
top指示当前栈顶的位置,通常称top为栈顶指针。因此,顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下:
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}Seqstack;
6/29/2017
设S是SeqStack类型的指针变量。若栈底位置在向量的低端,即s–>data[0]是栈底元素,那么栈顶指针s–>top是正向增加的,即进栈时需将s–>top加1,退栈时需将s–>top 减1。因此,s–>top<0表示空栈, s–>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出,简称“上溢”;当栈空时再做退栈运算也将产生溢出,简称“下溢”。
6/29/2017
上溢是一种出错状态,应该设法避免之;下溢则可能是正常现象,因为栈在程序中使用时,其初态或终态都是空栈,所以下溢常常用来作为程序控制转移的条件。
6/29/2017
1、置空栈
void Initstack(Seqstack *s)
{
s–>top=-1;
}
2、判断栈空
int Stackempty(Seqstack *s)
{
return(s–>top==-1);
}
6/29/2017