【数据结构2】第三章（1） 栈、入栈出栈、顺序栈和链栈、栈的递归、顺序栈的初始化_出栈表示方法

用于学习

第三章 栈和队列

目录

第三章 栈和队列

3.1  栈( Stack )

(1)栈的定义和特点

(2)逻辑结构

(3)存储结构

(4)运算规则

(5)主要操作

基本操作：

栈的表示和操作

栈的存储结构——顺序栈和链栈

操作1：顺序栈的初始化

操作2：判断顺序栈是否为空

操作3：求顺序栈的长度

操作4：清空顺序栈

操作5：销毁顺序栈

操作6：顺序栈进栈

操作7：顺序栈出栈

操作8：取顺序栈栈顶元素

3.2  栈和递归

分治法

---

3.1  栈( Stack )

(1)栈的定义和特点

定义只能在表的一端(栈顶Top)进行插入和删除运算的线性表

(2)逻辑结构

与线性表相同，仍为一对一关系。

(3)存储结构

用顺序栈或链栈存储均可，但以顺序栈更常见

(4)运算规则

只能在栈顶Top运算，且访问结点时依照后进先出（LIFO)或先进后出（FILO)的原则

(5)主要操作

入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同

基本操作：

有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等

栈的表示和操作

入栈函数  PUSH()

出栈函数 POP（）

栈的存储结构——顺序栈和链栈

顺序栈SqStack

操作1：顺序栈的初始化

算法描述

操作2：判断顺序栈是否为空

算法描述

操作3：求顺序栈的长度

算法描述

操作4：清空顺序栈

算法描述

操作5：销毁顺序栈

操作6：顺序栈进栈

先压后动指针

压入数据e

*(S.top++) = e ;  等价于   *S.top = e; S.top++;

操作7：顺序栈出栈

算法描述

操作8：取顺序栈栈顶元素

分析：读需要用图中右边那种写法（原因：不能动到栈顶指针的位置）

3.2  栈和递归

递归的定义若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的;若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。

有头有体  叫定义

分治法