《[小学教育]栈与队列》由会员分享，可在线阅读，更多相关《[小学教育]栈与队列（45页珍藏版）》请在金锄头文库上搜索。
1、邵阳学院信息与计算科学专业教研室第3章 栈与队列 教研室：信息与计算科学 教师姓名：谢文平 课程名称算法语言与数据结构授课专业及 班次信息与计算科学08级授课内容栈和队列的逻辑结构、存 储结构及其基本操作授课方式及 学时讲授6课时目的要求目的：介绍栈和队列的逻辑结构和存储结构，以及基本运算及实现方法 要求：针对具体应用问题的要求和性质，选择栈和队列，设计有效算法 重点与难 点重点：掌握顺序栈和链栈以及循环队列和链队列上各种基本运算的实现 难点：循环队列中对边界条件的处理方法讲授内容 及 时间分配1 栈 2课时 2 队列 2课时 3 算法设计举例 2课时 教 具多媒体教学参考资料1 严蔚敏,吴伟
2、民编著.数据结构（C语言版）.北京: 清华大学出版社,2002年. 2黄同成,黄俊民等编.数据结构.中国电力出版社,2008年. 3 董建寅, 黄俊民等编.数据结构实验指导与题解.中国电力出版社,2008年. 邵阳学院信息与计算科学专业教研室栈是一种重要的、特殊的线性数据结构。从数据的逻辑结构角度看，栈是线性表；从操作的角度看，栈的基本操作是线性表操作的子集，是操作受限制的线性表。邵阳学院信息与计算科学专业教研室3.1.1 栈的逻辑表示 栈的定义栈是限定仅在表尾进行插入或删除的线性表。允许进行插入或删除的一端称为栈顶，它将随栈中元素的增减而浮动，栈顶指针指明当前元素位置；另一端称为栈底，其指针
3、是固定的，不随栈中元素的增减而移动。栈栈的操作规则是栈的操作规则是 “ “后进先出后进先出” ”。栈又称后进先出线性表，简称。栈又称后进先出线性表，简称 LIFO LIFO 表。表。 当栈中没有元素时称为空栈。邵阳学院信息与计算科学专业教研室例如，铁路调度站 A 是一个栈。 铁路调度示意图 3.1.1 栈的逻辑表示 栈的定义邵阳学院信息与计算科学专业教研室3.1.1 栈的逻辑表示 栈的抽象数据类型邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 顺序栈的定义把自栈底到栈顶的元素按逻辑次序依次存放在一组地址连续的存储单元里的方式称为栈的顺序存储结构，采用这种存储结构的栈称为
4、顺序栈。 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 顺序栈的类型定义通常的做法是以通常的做法是以 top=0 top=0 表示表示 “ “空栈空栈” ”。鉴于。鉴于 C C 语言中数组下标约定从语言中数组下标约定从 0 0 开始，因此对用开始，因此对用 C C 语言描述的顺序栈需要以语言描述的顺序栈需要以 top=-1 top=-1 表示空栈。表示空栈。 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 顺序栈的类型定义例如，顺序栈 S 的栈顶指针和栈中元素之间的关系如下：顺序栈中栈顶指针和栈中元素之间的关系 邵阳学院信息与计算科学专业教研室
5、3.1.2 栈的顺序存储表示与基本操作 初始化栈操作 算法描述：算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 销毁栈操作 算法描述：算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 取栈顶元素操作 算法描述：算法时间 复杂度为 O(1) 如果 S.top=-1，则表明顺序栈已空，此时若再作出栈处理则将因栈中无元素可 “出” 而发生溢出，这种情况称为 “下溢”。栈的下溢常用来作为程序的控制条件。 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 入栈操作 算法描述：如
6、果 S.top=S.stacksize-1，则表明顺序栈已满，此时若再作进栈处理则将发生溢出，这种情况称为 “上溢”。 在正常情况下，算 法时间复杂度为 O(1) 在上溢情况下，算 法时间复杂度为 O(n) 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 出栈操作 算法描述：算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.1.2 栈的顺序存储表示与基本操作 两个栈共享空间使同时存在的两个栈共享一段连续空间，把两个栈的栈底分别设在共享空间两端，让两个栈的栈顶各自向中间伸展，只有当两个栈的栈顶相遇时才会发生栈满问题，这称为两个栈共享空间。 两个栈共享空间采
7、用这种分配方法，两个栈可以做到互补余缺，使得任何一个栈的可采用这种分配方法，两个栈可以做到互补余缺，使得任何一个栈的可利用的最大空间均有可能超过利用的最大空间均有可能超过 m/2m/2，不仅增加了内存空间利用率，也减少，不仅增加了内存空间利用率，也减少了每个栈溢出的可能性。了每个栈溢出的可能性。 邵阳学院信息与计算科学专业教研室 链栈的定义栈中各个元素独立存储，依靠指针链接建立相邻的逻辑关系的方式称为栈的链式存储结构，简称链栈 。3.1.3 栈的链式存储表示与基本操作邵阳学院信息与计算科学专业教研室3.1.3 栈的链式存储表示与基本操作 链栈的类型定义非空链栈空链栈和单链表一样，为了操作方便起
8、见，给链栈添加一个头结点，并令头 指针 S 指向头结点。 当 S-next=NULL 时，该链栈为空栈。链栈没有栈满问题邵阳学院信息与计算科学专业教研室3.1.3 栈的链式存储表示与基本操作 初始化栈操作 算法描述：算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.1.3 栈的链式存储表示与基本操作 销毁栈操作 算法描述：算法时间 复杂度为 O(n) 邵阳学院信息与计算科学专业教研室3.1.3 栈的链式存储表示与基本操作 求栈长操作 算法描述：算法时间 复杂度为 O(n) 邵阳学院信息与计算科学专业教研室 入栈操作 算法描述：3.1.3 栈的链式存储表示与基本操作算法时间 复杂
9、度为 O(1) 邵阳学院信息与计算科学专业教研室 出栈操作 算法描述：算法时间 复杂度为 O(1) 3.1.3 栈的链式存储表示与基本操作邵阳学院信息与计算科学专业教研室队列是一种重要的、特殊的线性数据结构。从数据的逻辑结构角度看，队列是线性表；从操作的角度看，队列基本操作是线性表操作的子集，是操作受限制的线性表。邵阳学院信息与计算科学专业教研室3.2.1 队列的逻辑表示 队列的定义队列是限定只能在表一端进行插入，而在表另一端进行删除操作的线性表。允许进行删除操作的一端称为队头，它随着队列中元素的减少而浮动，队头指针指明队头元素位置；另一端称为队尾，其指针随队列中元素的增加而浮动，队尾指针指明
10、队尾元素位置。 队列的操作规则是队列的操作规则是 “ “先进先出先进先出” ”。队列又称先进先出线性表，简称。队列又称先进先出线性表，简称 FIFO FIFO 表。表。 当队列中没有元素时称为空队列。队列邵阳学院信息与计算科学专业教研室3.2.1 队列的逻辑表示 队列的抽象数据类型邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 顺序队列的定义把自队头到队尾的元素按逻辑次序依次存放在一组地址连续的存储单元里的方式称为队列的顺序存储结构，采用这种存储结构的队列称为顺序队列。 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 顺序队列的类型定义通常的
11、做法是以 Q.front=Q.rear=0 表示 “空队列”。 邵阳学院信息与计算科学专业教研室顺序队列中队头指针、队尾指针和队列中元素之间的关系 3.2.2 队列的顺序存储表示与基本操作 顺序队列的类型定义例如，顺序队列 Q 的头指针、尾指针和队列中元素之间的关系如下：初始化构建空队列时 令 Q.front=Q.rear=0 每当插入新的队尾元素时，先将新元素插入到队尾指针所指位置，再 使队尾指针 Q.rear 加 1。每当删除旧的队头元素时，先使队头指针所指位置的元素取出，再使 队头指针 Q.front 加 1。 在非空队列中， 队头指针始终指向队头元素； 队尾指针始终指向队尾元素的 “下
12、一个” 位置 在顺序队列中不断的入队操作，会造成数组下标越界；不断的出队操作，会造成 “假溢出” 现象。邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 循环队列解决 “假溢出” 现象的方法是将数组的 “尾” 与 “头” 接起来，形成循环的方式，因此，解决数组越界及假溢出的顺序队列称为循环队列。 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 循环队列逻辑上实现循环的队列循环队列只是在逻辑上实现了循环，而不是在物理上实现循环利用数学上的利用数学上的 MOD MOD 运算在逻辑上实现循环队列入队和出队指针修改：运算在逻辑上实现循环队列入队和出队指
13、针修改：（队头指针（队头指针+1+1）MOD MAXSIZE = MOD MAXSIZE = 实际队头指针实际队头指针（队尾指针（队尾指针+1+1）MOD MAXSIZE = MOD MAXSIZE = 实际队尾指针实际队尾指针如果循环队列空间 MAXSIZE=8，那么 Q7 的下一个位置就是 Q0。 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 循环队列满和空的条件循环的队列循环的队列满循环的队列空循环队列满和空条件同为 Q.front=Q.rear邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 循环队列满和空的条件在循环队列中少用一个元
14、素的空间，并约定以 “队头指针在队尾指针的下一位置（指环状的下一位置）上” 作为队列呈 “满” 状态的标志。该方法以牺牲一个元素空间为代价，区别循环队列满和空的条件。 呈 “满” 状态的循环队列呈 “空” 状态的循环队列循环队列的队列满条件：循环队列的队列满条件：(Q.rear+1) MOD MAXSIZE=(Q.rear+1) MOD MAXSIZE=Q.frontQ.front 循环队列的队列空条件：循环队列的队列空条件：Q.frontQ.front=Q.rearQ.rear 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 初始化队列操作 算法描述：算法时间 复杂
15、度为 O(1) 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 销毁队列操作 算法描述：算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 求队列长操作 算法描述：例如，Q.rear=4、Q.front=1 且 Q.queuesize=8，求得 length=(4-1+8) MOD 8=3又如，Q.rear=0、Q.front=4 且 Q.queuesize=8，求得 length=(0-4+8) MOD 8=4算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 入
16、队操作 算法描述：如果 (Q.rear+1)%Q.queuesize=Q.front，则表明循环队列已满，此时若再作入队处理则将发生溢出，这种情况称为 “上溢”。 在正常情况下，算 法时间复杂度为 O(1) 在上溢情况下，算 法时间复杂度为 O(n) 邵阳学院信息与计算科学专业教研室3.2.2 队列的顺序存储表示与基本操作 出队操作 算法描述：如果 Q.fornt=Q.rear，则表明循环队列已空，此时若再作出队处理则将因队列中无元素可 “出” 而发生溢出，这种情况称为 “下溢”。队列的下溢常用来作为程序的控制条件。 算法时间 复杂度为 O(1) 邵阳学院信息与计算科学专业教研室3.2.3 队列的链式存储表示与基本操作 链
