栈 1。栈及相关概念 堆找( Stack) 栈是允许在同一端进行插入和删除操作的 特殊线性表。 允许进行插入和删除操作的一端称为栈页 (top),另一端为栈底( bottom);栈底固定, 而栈顶浮动; 栈中元素个数为零时称为空栈。 栈结构也称为后进先出表(LIFO)。 上一页 「停止放映 栈、栈顶、栈底、空栈 下一页 后进先出表栈底固定,而栈顶浮动 0页
下一页 上一页 停止放映 第 6 页 一、栈 1。栈及相关概念 堆栈(Stack) –栈是允许在同一端进行插入和删除操作的 特殊线性表。 –允许进行插入和删除操作的一端称为栈顶 (top)，另一端为栈底(bottom)；栈底固定， 而栈顶浮动； –栈中元素个数为零时称为空栈。 –栈结构也称为后进先出表（LIFO）。 栈、栈顶、栈底、空栈 后进先出表 栈底固定，而栈顶浮动
栈有关概念 栈顶指针 在栈操作过程中,有一个专门的栈指针(习惯 上称它为ToP),指出栈顶元素所在的位置。 栈空的条件:top=-1 栈满的条件:top=MAXS|ZE-1 找上溢 栈空间是有限的,若栈已满,再进行入栈操作 时,就要产生上溢。 上一页 楼下溢 「停止放映 若栈空,再要执行出栈操作,则会发生下溢。 下一页 第7页
下一页 上一页 停止放映 第 7 页 栈有关概念 栈顶指针 在栈操作过程中，有一个专门的栈指针（习惯 上称它为TOP），指出栈顶元素所在的位置。 栈空的条件： top = -1 栈满的条件： top = MAXSIZE-1 栈上溢 栈空间是有限的，若栈已满，再进行入栈操作 时，就要产生上溢。 栈下溢 若栈空，再要执行出栈操作，则会发生下溢
2、栈的基本运算 ● Setnull( Stack)置栈为空; ● Empty( Stack)判定栈是否为空 Push( Stack,x)进栈操作,在栈顶插入元素; Pop( Stack)出栈操作,删除栈顶元素; 上一页 ● Gettop( Stack)取栈顶元素 「停止放映 下一页 第8页
下一页 上一页 停止放映 第 8 页 2、栈的基本运算 ⚫ Setnull（Stack） 置栈为空； ⚫ Empty（Stack） 判定栈是否为空； ⚫ Push（Stack，x）进栈操作，在栈顶插入元素； ⚫ Pop（Stack） 出栈操作，删除栈顶元素； ⚫ Gettop（Stack） 取栈顶元素
例1-10 有三个元素的进栈序列是1,2,3。写出可 能的出栈序列。 出栈序列 操作序列 S X S X S X 132 213 X S X 321 上一页 「停止放映 下一页 第9页
下一页 上一页 停止放映 第 9 页 例1-10 有三个元素的进栈序列是1，2，3。写出可 能的出栈序列。 出栈序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x
3、栈的顺序存储结构 (1)栈的顺序存储结构:实际上是一维 数组。 (2)顺序栈:栈的顺序存储结构称为顺 序栈。 ●栈的操作只能在一端进行;即栈顶位置随 进栈和出栈而变化。 ●(3)顺序栈的C语言描述(初始化、定义): 上一页 define maXsize n 「停止放映 int stack [ MAXSIZE] 下一页 int top 第10页
下一页 上一页 停止放映 第 10 页 3、栈的顺序存储结构 ⚫ （1）栈的顺序存储结构：实际上是一维 数组。 ⚫ （2）顺序栈：栈的顺序存储结构称为顺 序栈。 ⚫ 栈的操作只能在一端进行；即栈顶位置随 进栈和出栈而变化。 ⚫ （3）顺序栈的C语言描述(初始化、定义)： #define MAXSIZE n int stack[MAXSIZE]; int top = -1;