数据结构队列的特点和实现本解读.ppt

队列 定义 特点 基本操作 存储结构 取队头 入队 出队 队列的存储结构 循环队列 链队列 链队列的表示和实现 链队列的基本形态 链队列的基本操作 链队列的基本操作 链队列的基本操作 链队列的基本操作 链队列的基本操作 循环队列的表示和实现 队列的基本形态 假溢出的解决办法 如何判断队空和队满 循环队列的基本操作 循环队列的基本操作 循环队列的基本操作 双端队列 输出受限的双端队列 输入受限的双端队列 队列的应用 舞伴配对 舞伴配对 舞伴配对 舞伴配对 * 第三章 队列 限定在线性表的一端（表尾）进行插入，而在线性表的另一端（表头）进行删除。在队列中允许插入的一端叫队尾（rear)，允许删除的一端叫队头（front)。 1.队列也是一种线性结构； 2.对队列的操作按照“先进先出”的原则进行。 与栈相比，队列的插入、删除分别在线性表的表尾和表头进行。 读取非空队列中的队头元素 a1 a2 an … … 向队列中插入一个新的元素，新插入的元素为队尾。 a1 a2 an e … … 非空队列中，删除队头元素，其直接后继为新队头。 a1 a2 an … … 用一组地址连续的存储单元依次存放自队头到队尾的数据元素。 利用链表存储队列中队头到队尾的数据元素。 需要设置队头和队尾位置标志 队头指针指向队头，队尾指针指向队尾。 定义 用链表表示的队列称为链队列。也就是用带头结点的单链表存储数据。设置头指针front指向头结点，设置尾指针rear指向尾结点。 C描述 typedef struct QNode{ ElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; 链队列结点类型 链队列类型 空队列 非空队列 通常链队列用单链表表示。为了操作方便，给链队列添加一个头结点，令头指针指向头结点。也就是说，带头结点的链队列中，非空队列中，队头指针指向头结点，队尾指针指向队尾结点。空队列中，队头指针和队尾指针均指向头结点。 Q.front Q.rear ∧ a1 ∧ an … Q.front Q.rear Q.front==Q.rear 链队列的基本操作即为单链表的插入和删除的特殊情况，只是需要进一步修改尾指针或头指针。 初始化队列 入队列 出队列 取队头 清空队列 销毁队列 Q.front = (QueuePtr)malloc(sizeof(QNode)); Q.rear = Q.front ; Q.front-next = NULL; 1.初始化为空队列 生成新结点为头结点，队头和队尾指针指向此结点。头结点的指针域为空。 while(Q.front){ Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; } 2.销毁队列 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; 3.入队 入队修改尾指针 链队列在入队前不需要判断队列是否满。入队元素动态分配内存，插入到队尾处，同时修改队尾指针。 if (Q.front == Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear == p) Q.rear = Q.front; free (p); 4.出队 出队修改头结点的链接 一般情况下，删除队列首元素时仅需修改头结点中的指针，但当队列中最后一个元素被删除后，需要对队尾指针重新赋值（指向头结点）。 定义 用一组地址连续的存储单元依次存放从队头到队尾的元素。还需要附设两个整型变量：front指示队头元素的位置，rear指示队尾元素的下一个位置。 C描述 const int MAXSIZE=128; typedef struct { Elemtype elem[MAXSIZE]; int front; int rear; }Squeue; 空队列 非空队列 6 5 4 3 2 1 0 Q.front=Q.rear=