第3章堆栈和队列 堆栈 要雄栈应用 主 知〈队列 识 点队列应用 优先级队列
第3章 堆栈和队列 主 要 知 识 点 堆栈 堆栈应用 队列 队列应用 优先级队列
31堆栈 1、堆栈的基本概念 1)定义:限定只能在固定一端进行插入和删除操作的线性表。 特点:后进先出。 (2)允许进行插入和删除操作的一端称为栈顶,另一端称为栈底 作用:可以完成从输入数据序列到某些输出数据序列的转换
3.1 堆 栈 1、堆栈的基本概念 (1)定义:限定只能在固定一端进行插入和删除操作的线性表。 特点：后进先出。 (2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。 作用：可以完成从输入数据序列到某些输出数据序列的转换
2、堆栈抽象数据类型 数据集合: {an,a1…,an}a的数据类型为 Data Type。 操作集合: (1) StackInitiate(S):初始化堆栈S (2) StackNotEmpty(S):堆栈s非空否 (3) StackPush(S,x):入栈 (4) StackPop(S,d):出栈 (5) StackTop(S,d):取栈顶数据元素
2、堆栈抽象数据类型 数据集合: {a0 ,a1 ,…,an-1 }ai的数据类型为DataType。 操作集合： (1) StackInitiate(S) ：初始化堆栈S (2) StackNotEmpty(S)：堆栈S非空否 (3) StackPush(S, x) ：入栈 (4) StackPop(S, d)：出栈 (5) StackTop(S, d)：取栈顶数据元素
3、顺序堆栈 顺序堆栈:顺序存储结构的堆栈。 顺序栈的存储结构 利用一组地址连续的存储单元依次存放自栈底到栈顶的数 据元素
3、顺序堆栈 顺序堆栈：顺序存储结构的堆栈。 顺序栈的存储结构： 利用一组地址连续的存储单元依次存放自栈底到栈顶的数 据元素
栈底 栈顶 stack ao a, a2la3 a4 012345 MaxStackSize-1 top typedef struct DataType stack MaxStackSize]: int top y Seqstack;
a0 a1 a2 a3 a4 stack 栈底 栈顶 0 1 2 3 4 5 MaxStackSize-1 = top typedef struct { DataType stack[MaxStackSize]; int top; } SeqStack;