第4章 栈与队列.ppt

第4章栈和队列
数据结构(C描述)
栈
队列
退出
目录
前言
栈和队列是两种重要的线性结构,它们也是线性表,特殊性体现在:它们是操作受限的线性表。
栈
栈的定义
栈(stack)是一种操作受限的线性表,即表中元素的插入和删除只能在表的一端进行,通常称允许插入和删除的一端为栈顶(Top),另一端为栈底(Bottom)。
假设栈 s=(a1,a2,…,an),栈中的数据元素以a1,a2,…an的顺序入栈,而出栈的次序则是an,an-1,,…,a1,如图所示。
栈顶的位置随元素的插入或删除而变化,需要一个称为栈顶指示器的来指示栈顶的当前位置。一般将栈的插入操作称为进栈(入栈),删除操作为退栈(出栈)。
根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
也就是说,栈是一种后进先出(Last In First Out)的线性表,简称为LIFO表(或称FILO)。
类似日常生活中的一叠盘子

:INISTACK(&S)
将栈S置为一个空栈(不含任何元素)。
:PUSH(&S,X)
将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”。
: POP(&S)
删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”。
: GETTOP(S)
取栈S中栈顶元素。
: EMPTY(S)
判断栈S是否为空,若为空,返回值为1,否则返回值为0。
栈的抽象数据类型描述
ADT Stack {
Data:
含有n个元素a1,a2,a4,…,an,按LIFO规则存放,每个元素的类型都为elemtype。
Operation:
Void inistack(&s) //将栈S置为一个空栈(不含任何元素)
Void Push(&s,x) //将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”
Void Pop(&s) //删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”
Elemtype gettop(s) //取栈S中栈顶元素
Int empty(s) //判断栈S是否为空,若为空,返回值为1,否则返回值为0
}ADT stack
栈的顺序存储结构——顺序栈
1、顺序栈的定义如下:
#define maxnum 100 //定义栈的最大容量
typedef struct
{ elemtype stack[maxnum];
int top; //指示栈顶位置
}seqstack;
seqstack *s;
用一维数组来依次存放自栈底到栈顶的数据元素,同时
利用指针top来指示栈顶在数组中的当前位置。
#define maxlen MAXSIZE
typedef struct
{ elemtype vec[maxlen];
int len; //顺序表的长度
}sequenlist;

(1)初始化栈
由于数组的下标从0开始,故初始化时将栈顶指针放在下标为0之前,即-1处。
void inistack(seqstack *s)
{
s->top=-1; //设置栈顶指针top,表示栈空
}