本文共 2486 字，大约阅读时间需要 8 分钟。

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据的特殊线性表，队列具有先进先出的FIFO(First In First Out)，同栈正好相反

• 入队：在队尾进行插入操作即为入队
• 出队：在队头进行删除操作即为出队

队列也可以用数组和链表实现，但是使用链表的结构更优，因为如果使用数组的结构，出队时会在数组的头上出数据，出完数据后还必须处理剩下的数据，效率会比较低下，而链表在出完数据后，直接更换头结点并释放原来结点即可，相比于数组要更为适合实现队列一些。

队列的链式结构

typedef int QDataType;                      typedef struct QListNode     {                        struct QListNode* next;                      QDataType data;    }QNode; // 队列的结构                      typedef struct Queue    {                                        QNode* front;                 QNode* tail;            }Queue;

定义队列需要两个结构体，一个结构体中保存队列的结点信息，另一个队列中保存队列的队头指针和队尾指针。

队列的接口实现

1.void QueueInit(Queue* q);

描述：初始化队列，使队列的指针均指向空即可

实现：

void QueueInit(Queue* q)    {               q->front = q->tail = NULL;    }

2.void QueuePush(Queue* q, QDataType data);

描述：在队尾入队列

实现：

void QueuePush(Queue* q, QDataType data){       assert(q);    QListNode* newNode = (QListNode*)malloc(sizeof(QListNode));    newNode->data = data;    newNode->next = NULL;    if(newNode != NULL)    {           if(q->tail == NULL)        {               q->front = q->tail = newNode;        }        else        {               q->tail->next = newNode;            q->tail = newNode;        }    }}

3.void QueuePop(Queue* q);

描述：队头出队列

实现：

void QueuePop(Queue* q){       assert(q);    assert(!QueueEmpty(q));    //只有一个结点时    if(q->front == q->tail)    {           free(q->front);        q->front = q->tail = NULL;    }    else    {           QListNode* cur = q->front->next;                                    free(q->front);        q->front = cur;    }}

4.QDataType QueueFront(Queue* q);

描述：获取队列头部元素

实现：

QDataType QueueFront(Queue* q){       assert(q);    assert(!QueueEmpty(q));    return q->front->data;}

5.QDataType QueueBack(Queue* q);

描述：获取队尾元素

实现：

QDataType QueueBack(Queue* q){       assert(q);    assert(!QueueEmpty(q));    return q->tail->data;}

6.int QueueSize(Queue* q);

描述：获取队列中有效元素的个数

实现：

int QueueSize(Queue* q){       assert(q);    QNode* cur = q->front;    int size = 0;    while(cur)    {           size++;        cur = cur->next;    }    return size;}

7.int QueueEmpty(Queue* q);

描述：检测链表是否为空，如果为空返回非零结果，如果非空返回0

实现：

int QueueEmpty(Queue* q){       assert(q);    return q->front == NULL ? 1 : 0;}

8.void QueueDestroy(Queue* q);

描述：销毁队列，将队列中的结点一个接一个的free掉即可

实现：

void QueueDestroy(Queue* q){       assert(q);    QNode* cur = q->front;    while(cur)    {           QNode* next = cur->next;        free(cur);        cur=next;    }    q->front = q->tail = NULL;}