数据结构与算法 3.4 队列ADT

像栈一样，队列（queue）也是表。然而，使用队列时插入在一端进行而删除则在另一端进行。

3.4.1 队列模型

队列的基本操作是Enqueue（入队），它是在表的末端（或叫队尾（rear））插入一个元素，还有一个Dequeue（出队），它是删除（或返回）在表的开头（叫做队头（front））的元素。
图3-56显示一个队列的抽象模型：

              +------------+Dequeue(Q）  |            |   Enqueue(Q, X)
<----------   |   Queue Q  |  <-------------|            |+------------+图3-56 队列模型  

3.4.2 队列的链表实现

我们讨论队列的链表实现，对于每一个队列数据结构，我们需要保留一个Front指针与一个Rear指针用于标记队头及队尾。 图3-57显示一个队列的双向链表实现示例：

+----------+     +---------+     +---------+     +---------+
|\0|Head|68|---> |58| A |88|---> |68| B |99|---> |88| C |\0|
+----------+     +---------+     +---------+     +---------+↑                               ↑                           +---------+                     +---------+     |  Front  |                     |   Rear  | +---------+                     +---------+图3-57 队列双向链表实现

头文件 - queue.h

#include <stdio.h>
#include <stdlib.h>
#include "../../fatal.h"typedef int ElementType;struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Queue;
typedef PtrToNode Position;
typedef PtrToNode Front;
typedef PtrToNode Rear;// 创建队列
Queue CreateQueue(Queue);
// 入队
void Enqueue(Queue, ElementType);
// 出队
ElementType Dequeue(Queue);
// 输出队列
void PrintQueue(Queue);

源文件 - queue.c

#include "queue.h"// 创建新的节点
static Position NewNode(void);
// 是否空队列
static int IsEmptyQueue(Queue);
// 队列清空
static void MakeEmptyQueue(Queue);struct Node {ElementType Element;PtrToNode Next;PtrToNode Prev;
};// 队头Front
static Front QueueFront = NULL;
// 队尾Rear
static Rear  QueueRear  = NULL;/*** 创建新的节点* @return */
static Position NewNode() {return (Position)malloc(sizeof(struct Node));
}/*** 是否空队列* @param Q* @return */
static int IsEmptyQueue(Queue Q) {return Q->Next == NULL;
}/*** 队列清空* @param Q*/
static void MakeEmptyQueue(Queue Q) {Position P, Tmp;P = Q->Next;while (P != NULL) {Tmp = P->Next;free(P);P = Tmp;}Q->Next	= NULL;QueueFront = Q;QueueRear  = Q;
}/*** 创建队列* @param Q* @return */
Queue CreateQueue(Queue Q) {if (Q != NULL) {MakeEmptyQueue(Q);}Q = NewNode();if (Q == NULL) {FatalError("Out of memory!");}Q->Next = NULL;Q->Prev = NULL;QueueFront = Q;QueueRear  = Q;return Q;
}/*** 入队* @param Q* @param */
void Enqueue(Queue Q, ElementType X) {Position TmpCell = NewNode();if (TmpCell == NULL) {FatalError("Out of memory!");}if (IsEmptyQueue(Q)) {QueueRear = TmpCell;} else {Q->Next->Prev = TmpCell;}TmpCell->Element= X;TmpCell->Next   = Q->Next;TmpCell->Prev   = Q;Q->Next   = TmpCell;QueueFront= TmpCell;
}/*** 出队* @param Q* @return */
ElementType Dequeue(Queue Q) {if (IsEmptyQueue(Q)) {FatalError("Queue is empty!");}Position Prev = QueueRear->Prev;ElementType X = QueueRear->Element;Prev->Next= NULL;free(QueueRear);QueueRear = Prev;return X;
}/*** 输出队列* @param Q*/
void PrintQueue(Queue Q) {if (IsEmptyQueue(Q)) {FatalError("Queue is empty!");}Position P = Q->Next;while (P != NULL) {printf("|%x|%d|%x|", P->Prev, P->Element, P->Next);P = P->Next;if (P != NULL) {printf("-->");}}printf("\n");
}

调用示例

#include "ext/s16/queue.h"int main(int argc, char** argv) {Queue Q = CreateQueue(NULL);Enqueue(Q, 5);Enqueue(Q, 6);Enqueue(Q, 7);Enqueue(Q, 8);PrintQueue(Q);Dequeue(Q);PrintQueue(Q);Dequeue(Q);PrintQueue(Q);Dequeue(Q);PrintQueue(Q);return (EXIT_SUCCESS);
}

输出截图