数据结构与算法 教学课件 作者 张晓蕾 第五章.ppt

《数据结构与算法 教学课件 作者 张晓蕾 第五章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第5章栈和队列栈5.1模板栈容器5.2队列的基本知识5.3模板队列容器5.45.1栈5.1.1栈的定义及运算栈（stack）是限定仅在表尾一端进行插入或删除操作的线性表。对于栈来说，允许进行插入或删除的一端称为栈顶（top），而另一端称为栈底（bottom）。不含任何元素的栈称为空栈。栈中的元素遵从“先进后出（LIFO）”的原则。该原则的含义如下：设有一个栈S＝{a0，a1，……，an-1}a0先进栈，an-1最后进栈。a0是栈底元素，an-1是栈顶元素，如图5-1所示。出栈时，an-1最先出，a0最后出。因此，栈也称为后进先出（LIFO）的线性表。a0a1a0

2、an-1…栈顶栈底进栈出栈图5-1栈栈也有两种存储结构，即向量存储结构和链表存储结构。向量栈是顺序存储结构亦称顺序栈。它是利用地址连续的存储单元依次存放从栈底到栈顶的数据元素，同时设定一个top指针指向栈顶元素的当前位置。5.1.2栈的向量存储结构通常用一维数组来实现向量栈，习惯上以下标小的一端做栈底。当top=－1时为空栈；当元素进栈时top++；当top等于最大下标值时为栈满。向量存储结构描述如下：#defineMAXSIZE20structSqStack{ELEMTYPEelem[MAXSIZE];//数组域inttop;//栈指针域};例5-1字符栈的向

3、量存储结构。见教材p.98。1．向量栈类定义及其实现利用前面叙述的栈的向量存储结构描述，可以建立一个简易的向量栈类。该向量栈类的类名是miniSqStack。5.1.3简易向量栈类该类仅包含一个向量栈S作为私有数据成员，成员函数由构造器、插入操作、删除操作、取栈顶元素和输出操作组成。这些算法的函数原型如下。算法5-1miniSqStack();算法5-2voidpush(ELEMTYPEx);算法5-3ELEMTYPEpop();算法5-4ELEMTYPEgettop()const;算法5-5voidprint();简易向量栈类miniSqStack编写在头文件

4、miniStack_Vector.h中，要使用它，只需有下面的包含：#include"miniStack_Vector.h"简易向量栈类的接口源代码如下。#include#defineMAXSIZE20//定义问题规模#defineELEMTYPEint//定义数据类型classminiSqStack{private://声明向量栈structSqStack{ELEMTYPEelem[MAXSIZE];//数组域inttop;//向量栈指针域}S;public://构造器：初始化空向量栈miniSqStack();//入栈voidpush

5、(ELEMTYPEx);//出栈ELEMTYPEpop();//返回栈顶元素ELEMTYPEgettop()const;//向量栈输出voidprint();};在简易向量栈类的实现中，对它的插入操作、删除操作做了较详细的说明，请参看教材p.100-101。2．向量栈测试下面利用一个常量数组提供的数据来测试简易向量栈。例5-2简易向量栈的测试。栈可以用单链表作为存储结构，其结点的存储结构structLsnode简化定义为nodeLS。具体的定义语句如下：5.1.4栈的链表存储结构typedefstructLsnode{ELEMTYPEdata;//数据域stru

6、ctLsnode*next;//指针域}nodeLS;nodeLS*top;例5.3字符栈的链表存储结构。见教材p.103。1．简易链表栈类定义及其实现简易的链表栈类的类名是miniLsStack。在类中使用nodeLStop;5.1.5简易链表栈类来定义链表头结点。下面给出链表栈类miniLsStack的定义及其实现。该类的数据成员仅包含上述的一个私有单链表栈，成员函数由构造器、插入操作、删除操作、取栈顶元素和输出操作组成。这些算法的函数原型如下：算法5-6miniLsStack();算法5-7voidpush(ELEMTYPEx);算法5-8ELEMTYPE

7、pop();算法5-9ELEMTYPEgettop()const;算法5-10voidprint();链表栈类miniLsStack编写在头文件miniStack_List.h中，要使用它只需有下面的包含即可。#include"miniStack_List.h"为便于读者阅读，在该类源代码中加入了适当的注释并且对它的插入操作、删除操作做了较详细的说明。具体源代码见教材p.104-106。例5-4简易链表栈的测试。具体的应用程序源代码见教材p.107。运行本测试程序，所做的操作和结果见教材p.108。2．链表栈测试5.2模板栈容器5.2.1模板栈容器的实现栈容器适

8、配器生成具有后进先出（L