Queue - C语言（LeetCode107）

前言

队列的实现也是LeetCode107的关键。队列的实现分为两种，一种是实现先进先出的数据结构，另外一种是使用双栈实现队列。本文介绍第一种的实现，在实现107题时对第二种的实现进行解析。

分析

队列是一种先进先出的数据结构，因此使用链式队列的方式实现起来比较简单。队列的基本操作如下，

typedef struct QueueNode {
    int data;
    
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    
    QueueNode* rear;
} LinkQueue;

void CreateQueue(LinkQueue* queue);
bool EnQueue(LinkQueue* queue, int data);
bool DeQueue(LinkQueue* queue, int* dataPtr);
void Destroy(LinkQueue* queue);
void Traverse(LinkQueue* queue);

实现

本文中队列实现的是无头结点的，因此在入队和出队时对头结点的处理。

void CreateQueue(LinkQueue* queue) {
    queue->front = queue->rear = NULL;
}

bool EnQueue(LinkQueue* queue, int data) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    
    if (!node)
        return false;
    
    node->data = data;
    node->next = NULL;
    
    if (queue->front == NULL) {
        queue->front = queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }
    
    return true;
}

bool DeQueue(LinkQueue* queue, int* dataPtr) {
    if (queue->front == NULL)
        return NULL;
    
    QueueNode* p = queue->front->next, *q = queue->front;
    
    queue->front = p;
    q->next = NULL;
    
    (*dataPtr) = q->data;
    
    free(q);
    
    return true;
}

void Destroy(LinkQueue* queue) {
    while (queue->front) {
        queue->rear = queue->front->next;
        
        free(queue->front);
        queue->front = queue->rear;
    }
}

void Traverse(LinkQueue* queue) {
    QueueNode* p = queue->front;
    
    while(p) {
        printf("%d ", p->data);
        
        p = p->next;
    }
}

结束语

本文中实现了一种先进先出的无头结点的链式队列。栈和队列这两种数据结构，是在树的宽度遍历中使用最频繁的两种，其中队列还可以用双栈的方式实现，具体的解析在下文实现树的宽度逆序层次遍历时会提到。