第3章栈和队列 3.1栈 32栈的应用举例 33栈与递归的实现 34队列 第3章 2021/2/25
第3章 2021/2/25 1 第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列
31栈( Stack 1定y:限定只在表的一端(表尾进行 插入和删除操作的线性表 特点:后进先出(L∥FO)(弹出 进栈 (压入) 允许插入和删除 的一端称为栈顶 op -1 ←表尾 (top),另一端称 为栈底( bottom) a1 bottom→ Co ←表头 2021/2/25 第3章
2021/2/25 第3章 2 3.1 栈 ( Stack ) 1.定义：限定只在表的一端(表尾)进行 插入和删除操作的线性表 特点:后进先出(LIFO) 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 表尾 表头
2.栈的表示和实现 1)顺序栈—栈的顺序存储结构 2)链栈——栈的链式存储结构 3)静态分配整型指针 3 第3章 2021/2/25
第3章 2021/2/25 3 2. 栈的表示和实现 1）顺序栈——栈的顺序存储结构 2）链栈——栈的链式存储结构 3）静态分配整型指针
1)顺序栈—栈的顺序存储结构 限定在表尾进行插入和删除操作的顺序表 类型定义:p46 typedef struct i SElem Type * base SElem lype top int stacksize SqStack Sqstack S; (顺序栈有三个域:栈顶和栈底指针,栈的最大容量) 第3章 2021/2/25
第3章 2021/2/25 4 1）顺序栈——栈的顺序存储结构 限定在表尾进行插入和删除操作的顺序表 类型定义： p46 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; SqStack s; （顺序栈有三个域：栈顶和栈底指针，栈的最大容量）
说明: base称为栈底指针,始终指向栈底; 当base=NULL时,表明栈结构不存在 op为栈顶指针 a.top的初始值指向栈底,即top=base b.空栈:当top-base时为栈空的标记 C.当栈非空时,top的位置:指向当前栈 顶元素的下一个位置 stacksize—当前栈可使用的最大容量 5 第3章 2021/2/25
第3章 2021/2/25 5 说明： ▪ base称为栈底指针，始终指向栈底； 当base = NULL时，表明栈结构不存在。 ▪ top为栈顶指针 a. top的初始值指向栈底，即top=base b. 空栈：当top=base时为栈空的标记 c. 当栈非空时，top的位置：指向当前栈 顶元素的下一个位置 ▪ stacksize ——当前栈可使用的最大容量