1,数据结构,第3章 栈和队列 第3讲,2,本章分为（3）讲,第1讲 3.1 栈 3.2 栈的顺序存储结构及实现 3.3 栈的链表存储结构及实现 3.4 栈的应用 3.4.1表达式计算,第3讲 3.7 队列的链表存储结构及实现 3.8 队列的应用,第2讲 3.4.2 子程序的嵌套调用 3.4.3 递归调用 3.5 队 列 3.6 队列的顺序存储结构及实现,供教师参考,3,3.7 队列的链表存储结构及实现,队列也可采用链表存储结构。用链表表示的队列简称为链队列，如图所示。,一个链队列需两个指针才能唯一确定，分别称为头指针front和尾指针rear。 为操作方便使用附加头结点，并令头指针指向front附加头结点，正好指向队列第一个数据结点的前一位置。 尾指针rear指向队尾数据结点。,4,3.7.1 队列的链表存储结构,图(a)空链队列，满足条件： front=rear 图(b)进队元素x, 仅有一个数据元素。 图(c)再进队元素y。 图(d)出队一个元素的情况。,除去空队情况外，头指针front总是指向队头元素结点前一位置，队尾指针rear总是指向队尾元素结点自身。,5,struct quenode ElemType data; /数据元素类型 quenode *next; /结点指针域 ; quenode *front, *rear; front和rear分别为队列的头指针和尾指针。,链表队列的结点结构为:,6,队列采用链表存储结构时，需要两个指针才能唯一确定，它们分别为头指针和尾指针。 同时，把头、尾指针作为类的私有成员来处理。 链队列的各种操作设计为类的函数成员。,3.7.2 链表队列类定义,7,class LsQueue private: quenode *front, *rear; /头、尾指针 public: LsQueue(); LsQueue(); int IsEmpty() void Display(); void AddQ(ElemType x); ElemType DelQ(); ElemType GetFront() ;,1链表队列类定义,8,LsQueue:LsQueue() /构造函数，初始化空队 quenode *p; p=new quenode; p-next=NULL; front=rear=p; int LsQueue:IsEmpty() /判队列是否为空 if(front=rear) return 1; else return 0; ,链表队列类的几个函数,9,ElemType LsQueue:GetFront() /取队首元素不出队 ElemType x; quenode *p; if (front=rear) coutnext; x=p-data; return x; 这里没有给出析构函数和输出函数的实现，请读者自己思考写出。,链表队列类的几个函数,10,进队操作在队尾处进行。新数据结点s插在队尾结点后，将尾指针rear移至新队尾结点s上。 void LsQueue:AddQ(ElemType x) /x结点入队 quenode *s; s=new quenode; s-data=x; s-next=NULL; rear-next=s; rear=s; /很重要 由于是链表结构，在插入时不用判断队列是否为满。,2进队操作 -算法3.9,11,ElemType LsQueue:DelQ() /出队一个元素 ElemType x; quenode *p; if ( front=rear) coutnext; /p指向第一个数据结点 front-next=p-next; if(p-next=NULL) rear=front; /防止尾指针丢失 x=p-data; delete p; return x; ,3出队操作 -算法3.10,12,通过链表队列对象Q调用进队、出队和输出函数。,int main() ElemType e; int j; LsQueue Q; coute; Q.AddQ(e); Q.Display(); e=Q.DelQ(); Q.Display(); return 0; ,13,3.8 队列的应用,队列有着广泛的应用。本节通过“报数问题”的求解介绍队列在程序设计中的应用。 所谓报数问题，设有n个人站成一排，从左到右的编号分别为1n，从左到右报数“1，2，3，1，2，3”数到“1”和“2”的人出列，数到“3”的人立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求输出数据出列的顺序。 例如，当n = 10时，初始序列为 1 2 3 4 5 6 7 8 9 10 则出列顺序为：2 4 5 7 8 10 3 6 9,14,算法思想,先将n个人的编号进队，然后反复执行如下操作： （1）出队一个元素，输出其编号； （2）再出队一个元素，输出其编号； （3）若队列不空，则出队一个元素，然后将该元素再进队，直到队列为空。 本算法采用链表队列类LsQueue Q， 假设ElemType代表整型，算法如下：,15,报数问题的算法,void number(int n) int i; ElemType e; LiQueue Q; for(i=1;i=n;i+) Q.AddQ(i); /构建初始序列 cout“n 报数出列顺序：“； while(!Q.IsEmpty() e=Q.delQ( ); cout“ “e; /出列一个元素且输出 e=Q.delQ( ); cout“ “e; /再出列一个元素且输出 if(!Q.IsEmpty( ) e=Q.delQ( ); /出列一个元素 Q.AddQ(e); /将该元素进队，排在队尾 /while ,16,小 结,栈是操作受限的线性表，插入和删除操作只能在表一端进行。栈是一个后进先出（Last In First Out，LIFO）的线性表。 栈的顺序存储结构称为顺序栈，本质上是顺序表的简化。通常把数组中下标为0的一端作为栈底，同时设指针top指示栈顶元素的位置。顺序栈基本操作的算法的时间复杂度均为O(1)。 栈的链式存储结构称为链栈，链栈的插入和删除操作仅在栈顶进行，其时间复杂度均为O(1)。,17,小 结,队列也是操作受限的线性表。限定在队尾处插入，而在队头处删除。队列是先进先出（First In First Oout，FIFO）的线性表。 约定队列的头指针front指向队列头元素前一位置，而为指针rear指向队尾元素自身。 循环队列是重要数据结构，即指队列的顺序存储结构。凡涉及队头或队尾指针的修改都要对MAXSIZE求模： front=(front+1) % MAXSIZE; rear=(rear+1) % MAXSIZE; 循环队列，队空的判定条件：rear=front 循环队列，队满的的判定条件是： (rear+1)%MAXSIZE=front,18,小 结,队列的链式存储结构称为链队列。通常设附加头结点，并设队头指针指向头结点，即指向第一个数据结点的前一位置。队列的尾指针指向终端结点。 链队列的基本操作，也是单链表操作的简化，插入只考虑在链队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均为O(1)。 链队列，队空的判定条件：rear=front 链队列一般不作队满的的判。 本章的重点是栈和队列的基本概念，以及在不同存储结构前提下的进栈、出栈、进队、出队算法。,19,写给任课教师,为了逐步培养在实际中应用栈和队列的能力。 结合布置的上机作业，因C+实验存在一定难度，教师在实验室也要有实验课件，适当讲解，对学生加以指导和引导。 结合将要布置的课后书写作业，教师在讲课过程中要增加与作业相关的引导示范内容。 后面（下一片）的“对比复习”内容，仅供教师参考，仅有标题。可不采纳，也可根据自己理解完成。,20,栈和队列与线性表对比复习,一、存储结构的复习 二、类设计的复习 三、重要算法的前提条件,21,一、存储结构的复习,顺序结构类的私有数据成员: ElemType elemMAXSIZE; /三者相同 int length; /线性表长，用于顺序表 int top ; /栈顶指针，用于顺序栈 int front,rear; /队头、队尾指针，用于循环队列,链表结构类的私有数据成员： Head; /头指针，用于单链表 top; /栈顶指针，用于链表栈 front,rear; /队头、队尾指针，用于链队列,22,二、类设计的复习,顺序表类； 顺序栈类； 循环队列类； 单链表类； 链表栈类； 链表队列类；,23,三、重要算法的前提条件,线性表的插入/删除 顺序结构前提： 指定位置int i， 指定数据元素值x，先查找 链式结构前提： 指定位置 int i 的， 指定数据元素值x的,未完待续 请教师自己完成。,