第3章-栈和队列.ppt

第3章栈和队列
本章主要内容
栈的概念、存储结构及其基本操作
栈的应用
栈与递归
队列的概念、存储结构及其基本操作
队列的应用
栈
栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。
进行插入和删除的称为栈顶,并用一个“栈顶指针”指示;而另一端是固定端,称为栈底。
a1, a2, a3, ..., an 插入和删除端
图 3-1
栈的操作入栈演示
a
b
c
SP
单击标题开始演示!
下一页
栈的操作出栈演示
a
b
c
SP
单击标题开始演示!
下一页
栈的特点
后进先出(Last In First Out),简称为LIFO线性表。
举例1:家里吃饭的碗,通常在洗干净后一个一个地落在一起存放,在使用时,若一个一个地拿,一定最先拿走最上面的那只碗,而最后拿出最下面的那只碗。
举例2:在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。
栈的基本操作
1、栈初始化:Init_Stack(S)
初始条件:栈S不存在
操作结果:构造了一个空栈。
2、销毁栈:Destroy_Stack(S)
初始条件:栈S已存在
操作结果:销毁一个已存在的栈。
3、判栈空:Empty_Stack(S)
操作结果:若S为空栈返回为1,否则返回为0。
栈的基本操作
4、入栈: Push_Stack(S,x)
初始条件:栈S已存在
操作结果:在栈s的顶部插入一个新元素x, x成为新的栈顶元素。栈发生变化
5、出栈:Pop_Stack(S)
初始条件:栈S存在且非空
操作结果:栈S的顶部元素从栈中删除,栈中少了一个元素。栈发生变化
6、取栈顶元素:GetTop_Stack(S)
初始条件:栈S存在且非空
操作结果:栈顶元素作为结果返回,栈不变化
栈的顺序存储
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素,并用起始端作为栈底。
类型定义如下所示:
#define MAXSIZE 100
typedef struct {
DataType data[MAXSIZE];
int top;
}SeqStack, *PSeqStack;
定义一个指向顺序栈的指针:
PSeqStack S;
S=( PSeqStack)malloc(sizeof(SeqStack));