资源描述：
《数据结构第3章栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列【课前思考】1.什么是线性结构？2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？第三章栈和队列栈和队列与线性表相比，是限定性的线性表结构。栈的特点：栈必须按“后进先出”的规则进行操作队列特点：必须按“先进先出”的规则进行操作。插入删除线性表：Insert(L,i,x)Delete(L,i)(1≤i≤n+1)(1≤i≤n)栈：Insert(L,n+1,x)Delete(L,n)队列：Insert(L,n+1,x)Del
2、ete(L,1)1.从“数据结构”的角度看，它们都是线性结构即数据元素之间的关系相同。2.它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的“限定”。如：线性表允许在表内任一位置进行插入和删除； 栈只允许在表尾一端进行插入和删除； 队列只允许在表尾一端插入，在表头一端删除。栈和队列与线性表对比：第三章栈和队列3.1栈3.1.1栈的类型定义栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称作“栈顶(top)”不允许插入和删除的另一端称作"栈底(bottom)"通常称往栈顶插入元素的操
3、作为“入栈”，称删除栈顶元素的操作为“出栈”。栈被称为是一种“后进先出”的结构，又称LIFO（LastInFirstOut的缩写）表。如下图所示的铁路调度站栈的类型定义如下：ADTStack{数据对象：D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。 操作结果：栈S被销毁。ClearStack(&S)初始条
6、件：栈S已存在。 操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。 操作结果：返回栈S中元素个数，即栈的长度GetTop(S,&e)初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。StackTrav
7、erse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack3.1栈3.1.2栈的存储表示和操作的实现栈也有两种存储表示：顺序存储和链式存储顺序存储结构简称为顺序栈链式存储结构简称为链栈"栈顶指针"意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的length值的意义相同。一、顺序栈类型的定义//结构定义：typedefstruct{elemType*base;//存储空间基址
8、inttop;//栈顶指针intstacksize;//允许的最大存储空间以元素为单位}Stack;3.1栈3.1.2栈的存储表示和操作的实现//基本操作接口(函数声明)：voidInitStack(Stack&S，intmaxsize);//构造一个最大存储容量为maxsize的空栈S。voidDestroyStack(Stack&S);//销毁栈S，S不再存在。voidClearStack(Stack&S);//将S置为空栈。boolStackEmpty(StackS);//若栈S为空栈，则返回TRUE，否则返回FALSEintStackLengt
9、h(StackS);//返回S的元素个数，即栈的长度。boolGetTop(StackS,ElemType&e);//若栈不空，则用e返回S的栈顶元素，并返回TRUE；//否则返回FALSE。boolPush(Stack&S,ElemTypee);//若栈的存储空间不满，则插入元素e为新的栈顶//元素，并返回TRUE； 否则返回FALSE。boolPop(Stack&S,ElemType&e);//若栈不空，则删除S的栈顶元素，用e返回其值，//并返回TRUE；否则返回FALSE。voidStackTraverse(StackS,void(*visi
10、t(ElemType))//依次对S的每个元素调用函数visit()，//一旦visit()失
