C语言用指针支持队列

队列是一种线性数据结构，行为类似排队。它通常支持两种主要操作：入队和出队。入队操作把元素添加到队列中，出队操作从队列中删除元素。一般来说，第一个添加到队列中的元素也是第一个离开队列的元素，这种行为被称为先进先出（FIFO）。

实现队列经常用到链表。入队操作就是将节点添加到链表头，出队操作就是从链表尾删除节点。为了说明队列，我们会用到6.4.1节中开发的链表。

先用类型定义语句来定义队列，它基于链表，如下所示。现在可以用Queue来清晰地表达我们想要的东西了：

typedef LinkedList Queue;

要实现初始化操作，要做的只是利用initializeList函数。我们不会直接调用这个函数，而是使用下面的initializeQueue函数：

void initializeQueue(Queue *queue) {
    initializeList(queue);
}

类似地，下面的代码会用addHead函数向队列中添加一个节点：

void enqueue(Queue *queue, void *node) {
    addHead(queue, node);
}

之前实现的链表没有删除尾节点的函数，下面的dequeue函数删除最后一个节点，这里需要处理以下三种情况：

• 空队列
  返回NULL
• 单节点队列
  由else if语句处理
• 多节点队列
  由else分支处理

在最后一种情况中，我们用tmp指针来一个节点一个节点地前进，直到它指向尾节点的前一个节点，然后按顺序执行下面三种操作：

1. 将尾节点赋值为tmp；
2. 将tmp指针前进一个节点；
3. 将尾节点的next字段置为NULL，表示后面没有节点了。

必须按照这个顺序来确保链表的完整性，下图说明了原理，带圆圈的数字对应上面的三步操作。

void *dequeue(Queue *queue) {
    Node *tmp = queue->head;
    void *data;
    if (queue->head == NULL) {
        data = NULL;
    } else if (queue->head == queue->tail) {
        queue->head = queue->tail = NULL;
        data = tmp->data;
        free(tmp);
    } else {
        while (tmp->next != queue->tail) {
        tmp = tmp->next;
        }
        queue->tail = tmp;
        tmp = tmp->next;
        queue->tail->next = NULL;
        data = tmp->data;
        free(tmp);
    }
    return data;
}

返回赋给节点的数据后节点被释放。下面的代码片段用前面创建的雇员信息说明这些函数的用法：

Queue queue;
initializeQueue(&queue);

enqueue(&queue, samuel);
enqueue(&queue, sally);
enqueue(&queue, susan);

void *data = dequeue(&queue);
printf("Dequeued %s\n", ((Employee*) data)->name);
data = dequeue(&queue);
printf("Dequeued %s\n", ((Employee*) data)->name);
data = dequeue(&queue);
printf("Dequeued %s\n", ((Employee*) data)->name);

输出如下：

Dequeued Samuel
Dequeued Sally
Dequeued Susan