《小白学数据结构》课件——第三章 栈和队列.pptx

MANDAMUS小白学数据结构知识讲堂主讲教师：

1.栈的顺序存储结构

n!

定义：只允许在同一个端点处进行插入或删除操作的线性表称为栈（stack）栈栈栈顶（top）栈底（bottom）进栈（push）出栈（pop）空栈（empty）TOP

栈栈特点：栈是一种后进先出结构后进先出（lastinfirstout)表（简称LIFO结构）进筒出筒

初始化生成空栈：stack取栈顶元素：top进栈：push出栈：pop判断栈是否为空：empty栈栈基本操作

应用实例栈栈

顺序栈栈typedefstruct{ElemTypestack[MaxStackSize];inttop;}Stack;顺序栈的类型定义MaxStackSize

顺序栈顺序栈MaxStackSize-1

总结栈和顺序栈的相关知识理解栈的操作原则栈在生活中的应用实例掌握顺序栈的存储结构和类型定义

总结学而不思则罔，思而不学则殆。

2.顺序栈的基本操作

判栈空操作判栈满操作初始化栈出栈取栈顶元素进栈

初始化栈

初始化栈voidInitStack(SeqStack*S){S-top=-1;}

判栈空操作

判栈空操作intStackEmpty(SeqStack*S){if(S-top==-1)retrun1;elsereturn0;}

判栈满操作

判栈满操作intStackFull(SeqStack*S){if(S-top==MaxStackSize-1)retrun1;elsereturn0;}

顺序栈的进栈运算

顺序栈的进栈运算

具体的程序设计voidPush(SeqStack*S,chare){if(S-top==MaxStackSize-1)printf(“Stackoverflow”);else{S-top++;S-data[S-top]=e;}}

顺序栈的出栈运算

顺序栈的出栈运算

具体的程序设计charPop(SeqStack*S){chare;if(S-top==-1)printf(“Stackunderflow”);else{e=S-data[S-top];S-top--;returne;}}

顺序栈的取栈顶元素运算

顺序栈的取栈顶元素运算charStackTop(SeqStack*S){chare;if(S-top==-1)printf(“Stackisempty”);else{e=S-data[S-top]; returne;}}

顺序栈的基本操作基本操作的核心算法和程序设计

学而不思则罔，思而不学则殆。

3.队列的顺序存储结构

电脑疑似死机又突然恢复正常

客服人员占线客户被要求等待最先等待的客户接通电话

如何实现的呢？

队列

队列队列是一种特殊的线性表，其特殊性在于只允许在一端进行插入，而在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫对头，队的插入和删除分别称为进队和出队。队头队尾进队出队firstlastabcx…1.队的术语

队列是一种特殊的线性表，其特殊性在于只允许在一端进行插入，而在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫对头，队的插入和删除分别称为进队和出队。队头队尾进队出队firstlastabcx…y队列1.队的术语

队列是一种特殊的线性表，其特殊性在于只允许在一端进行插入，而在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫对头，队的插入和删除分别称为进队和出队。队头队尾进队出队firstlastabcx…队列1.队的术语

队列是一种特殊的线性表，其特殊性在于只允许在一端进行插入，而在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫对头，队的插入和删除分别称为进队和出队。队头队尾进队出队firstlastabcx…a队列1.队的术语

1.队列的术语abcd队头队尾出队进队

队结构遵循先进先出原则，又称先进先出（FirstInFirstOut)表，或FIFO表。队头的人最先办理业务2.队列的特点队列

出队进队队列abcd已知数据元素进队次序为a、b、c、d，请写出所有元素出队后的序列。