第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;
顺序堆栈的操作实现 (1)初始化 StackInitiate(S) void StackInitiate(seqStack"S) S->top=0; (2)非空否 StackNotEmpty(S) int StackNotEmpty (seqStacks if(S top<=Return 0 else return 1
顺序堆栈的操作实现： （1）初始化StackInitiate(S) void StackInitiate(SeqStack *S) { S->top = 0; } （2）非空否StackNotEmpty(S) int StackNotEmpty(SeqStack S) { if(S.top <= 0)return 0; else return 1; }
(3)入栈 StackPush(S,x) int StackPush(SeqStack *S, Data Type x) if(s->top > MaxStackSize) printf("堆栈已满无法插入!Ⅷm"); return else t S->stack[S->top]=x S->top++ return 1;
（3）入栈StackPush(S, x) int StackPush(SeqStack *S, DataType x) { if(S->top >= MaxStackSize) { printf("堆栈已满无法插入!\n"); return 0; } else { S->stack[S->top] = x; S->top ++; return 1; } }
(4)出栈 StackPop(S,d) int StackPop(seqstack"S, DataType *d) t if(s->toptop--*d=s->stack S->top]; return I
（4）出栈StackPop(S, d) int StackPop(SeqStack *S, DataType *d) { if(S->top top --;*d = S->stack[S->top]; return 1; } }
(5)取栈顶数据元素 StackTop( Seqstack s, DataType*d) int StackTop(seqstacks, Data Type *d) if(stop<=0) printf("堆栈已空!Ⅶn"); return o e t*d=sstack[S top-1; return 1
（5）取栈顶数据元素StackTop(SeqStack S, DataType *d) int StackTop(SeqStack S, DataType *d) { if(S.top <= 0) { printf("堆栈已空!\n"); return 0; } else { *d = S.stack[S.top - 1]; return 1; } }
测试主程序 任务:建立一个顺序堆栈,首先依次输入数据元素1,2, ······ 10,然后依次出栈堆栈中的数据元素并显示。 假设该顺序堆栈的数据元素个数在最坏情况下不会超过 100个。 #include #include #define maxStackSize 100 typedef int Data Type; #include segstack h
测试主程序： 任务：建立一个顺序堆栈，首先依次输入数据元素1, 2, 3,......,10，然后依次出栈堆栈中的数据元素并显示。 假设该顺序堆栈的数据元素个数在最坏情况下不会超过 100个。 #include #include #defineMaxStackSize 100 typedef int DataType; #include "SeqStack.h