《数据结构3.2栈与队列双栈和循环队列课件》由会员分享，可在线阅读，更多相关《数据结构3.2栈与队列双栈和循环队列课件（20页珍藏版）》请在金锄头文库上搜索。
1、栈与队列栈与队列数据结构3.2栈与队列(双栈和循环队列)第10次课 栈与队列主要内容链式结构复习(单链表,循环链表,链栈)双栈结构的实现(程序示例)循环队列复习运动会比赛安排(链队实现)数据结构3.2栈与队列(双栈和循环队列)1、双栈结构 为同时出现的两个栈共同开辟一存储空间共同开辟一存储空间，两个栈的栈底设于存储空间的两端b1b2bs ana2a1栈栈2底底 栈栈2顶顶top2栈栈1顶顶top1栈栈1底底优点优点: : 两栈互补余缺充分利用存储空间。两栈互补余缺充分利用存储空间。数据结构3.2栈与队列(双栈和循环队列)双栈的存储结构定义 typedef struct ElemType *el
2、em； /待分配存储空间 int top1；/队头指针 int top2; /队尾指针 DStack； ；数据结构3.2栈与队列(双栈和循环队列)双栈操作栈初始化 InitDStack(DStack &ds )入栈 PushDStack(DStack &ds,ElemType elem,int iFlag)出栈 OutDStack(DStack &ds,ElemType &elem,int iFlag)判栈空 IsEmpty(Dstack ds,int iflag)判栈满 IsFull(DStack ds)销毁栈 DestroyDStack(Dstack &ds)数据结构3.2栈与队列(双栈和
3、循环队列)2、循环队列复习队列的顺序存储结构 typedef struct ElemType *elem； /待分配存储空间 int front；/队头指针 int rear; /队尾指针 SeqQueue ；a1sq.frontsq.reara2a3a4a5sq.elem存储空间数据结构3.2栈与队列(双栈和循环队列)循环队列操作sq.front01234567sq.rearInitQueue(SeqQueue &sq) sq.elem=new ElemTypeMAXSIZE；/MAXSIZE sq.front = sq.rear = 0;InQueue(SeqQueue &sq,ElemT
4、ype e)InitQueue(SeqQueue &sq)OutQueue(SeqQueue &sq,ElemType &e)Destroy(SeqQueue &sq)数据结构3.2栈与队列(双栈和循环队列)循环队列操作01234567a1a2a3a4a5sq.rearsq.fronta6InQueue(SeqQueue &sq,ElemType e)InitQueue(SeqQueue &sq)OutQueue(SeqQueue &sq,ElemType &e)Destroy(SeqQueue &sq)数据结构3.2栈与队列(双栈和循环队列)循环队列操作sq.front01234567a1a
5、2a3a4a5sq.reara6a7InQueue(SeqQueue &sq,ElemType e)InitQueue(SeqQueue &sq)OutQueue(SeqQueue &sq,ElemType &e)Destroy(SeqQueue &sq)InQueue(SeqQueue &sq, ElemType e) if(sq.rear+1)%MAXSIZE ! = sq.front) sq.elem sq.rear=e； sq.rear = (sq.rear+1)%MAXSIZE;数据结构3.2栈与队列(双栈和循环队列)循环队列操作InQueue(SeqQueue &sq,ElemTy
6、pe e)InitQueue(SeqQueue &sq)OutQueue(SeqQueue &sq,ElemType &e)Destroy(SeqQueue &sq)OutQueue(SeqQueue &sq, ElemType &e) if(sq.front!=sq.rear) e = sq.elemsq.front; sq.front=(sq.front+1)%MAXSIZE； 01234567a1a2a3a4a5sq.reara6a7sq.front数据结构3.2栈与队列(双栈和循环队列)3、链队实现a1anQ.frontQ.frontQ.rear空队列空队列Q.rear数据结构3.2栈
7、与队列(双栈和循环队列)存储结构定义 typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;数据结构3.2栈与队列(双栈和循环队列)初始化操作 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear =new QNode; if (!Q.front) exit (1);
8、/存储分配失败 Q.front-next = NULL; return 1;Q.frontQ.rear空队列空队列数据结构3.2栈与队列(双栈和循环队列)入队操作 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = new QNode; if (!p) exit (1); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return 1;a1anQ.frontQ.rear数据结构3.2栈与队列(双栈和循环队列)出队操作 Status DeQ
9、ueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回1；否则返回0 if (Q.front = Q.rear) return 0; p = Q.front-next; e = p-data; Q-front-next = p-next; delete (p); return 1;if (Q.rear = p) Q.rear = Q.front;a1anQ.frontQ.rear数据结构3.2栈与队列(双栈和循环队列)应用：运动会比赛安排 某运动会设立 N 个比赛项目，每个运动员可以参加一至三个项目。试问如何安排比赛
10、日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。分析：若将此问题抽象成数学模型，则归属于“划分子集”问题。N 个比赛项目构成一个大小为 n 的集合，有同一运动员参加的项目则抽象为“冲突”关系。数据结构3.2栈与队列(双栈和循环队列)例如：某运动会设有 9 个项目: A = 0，1，2，3，4，5，6，7，8 ，七名运动员报名参加的项目分别为：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）、（6，4） 它们之间的冲突关系为: R = （1，4）,（4，8）,（1，8）,（1，7）,（8，3）,（1，0）,（0，5）,（1，5）,
11、（3，4）,（5，6）,（5，2）,（6，2）,（6，4） 数据结构3.2栈与队列(双栈和循环队列)“划分子集划分子集”问题问题 将集合A划分成k个互不相交的子集 A1，A2，Ak（kn）， 使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。 对前述例子而言，问题即为: 同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。数据结构3.2栈与队列(双栈和循环队列)求解方法：可利用“过筛过筛”的方法来解决划分子集问题。从第一个元素考虑起，凡不和第一个元素发生冲突的元素都凡不和第一个元素发生冲突的元素都可以和它分在同一子集中可以和它分在同一子集中，然后再“过筛”出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止。问题：冲突关系的正确表示？数据结构3.2栈与队列(双栈和循环队列)组号 = 0;全体元素入队列;while ( 队列不空 ) 队头元素i出队列入组; while(jQueueLen) 队头元素j出队列 if ( j和组中元素都不冲突 ) j入组 else j重新入队列; /while 组号+；划分子集算法的基本思想划分子集算法的基本思想: :数据结构3.2栈与队列(双栈和循环队列)
