第3章 限定性线性表——栈和队列.ppt

第3章限定性线性表——栈和队列
栈
队列
返回主目录
栈
栈的定义
栈的表示和实现
栈的应用举例
栈与递归的实现
返回主目录
栈的定义:
栈作为一种限定性线性表,是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top),表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。
返回主目录
根据栈定义,每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶,而每次出栈的总是当前栈中“最新”的元素,即最后进栈的元素。因此,栈又称为后进先出的线性表。简称为LIFO表。如下图所示:
进栈、出栈图例
进栈
出栈
进栈
出栈
栈顶
栈底
an
a2
a1
返回主目录
栈的抽象数据类型定义
关系:栈中数据元素之间是线性关系
数据元素:可以是任意类型的数据,但必须属于同一个数据对象。
基本操作:
InitStack(S) 2. ClearStack(S)
3. IsEmpty(S) 4. IsFull(S) 5. Push(S,x)
6. Pop(S,x) 7. GetTop(S,x)
返回主目录
栈的表示和实现
栈在计算机中主要有两种基本的存储结构:顺序存储结构和链式存储结构。
顺序存储的栈为顺序栈;
链式存储的栈为链栈。
返回主目录

顺序栈是用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时由于栈的操作的特殊性,还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以top = -1表示空栈。
返回主目录
用C语言定义栈的顺序存储结构
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
 typedef struct
{StackElementType elem[Stack_Size];
/*用来存放栈中元素的一维数组*/
int top; /*用来存放栈顶元素的下标*/
}SeqStack;
返回主目录
顺序栈中的进栈和出栈图例
A
E
D
C
B
A
B
A
top
top
top
top
返回主目录
顺序栈基本操作的实现
1)初始化
void InitStack(SeqStack *S)
{/*构造一个空栈S*/
S->top= -1;
}
返回主目录