队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First in Frist Out）
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
结构体类型定义
#include <stdlib.h> #include <stdio.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue;
基本接口函数
//基本接口函数 void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);
初始化函数
void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; }
销毁队列函数
队列的销毁和链表的销毁基本相同，注意在free时记得提前存储下一个结点的地址即可。
void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
入队列函数
当队列中没有数据时，头结点即是尾结点，所以将新结点赋给头结点和尾结点。 当队列中有数据时，则进行链表的尾插操作。tail->next = newnode；tail = newnode。
void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } }
判断队列是否为空
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
出队列函数
出队列函数要注意判断队列是否为空，为空就没有数据可以进行出队列的操作了。
而当队列一直进行出队列的操作，直到队列中只剩下一个数据。头指针和尾指针指向相同的地址，它们所指向的空间被释放掉之后，指针所指向的地址只有head被置空，但tail并没有置空，所以此处的tail存在野指针的隐患。 故要注意多加一步，当head被置空时，tail也进行置空。
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } }
读取队头队尾的数据
QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
计算队列中有多少个数据
int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { n++; cur = cur->next; } return n; }
出队列中的所有数据
int main() { Queue pq; QueueInit(&pq); QueuePush(&pq, 1); QueuePush(&pq, 2); QueuePush(&pq, 3); QueuePush(&pq, 4); QueuePush(&pq, 5); while (!QueueEmpty(&pq)) { QDataType front = QueueFront(&pq); printf("%d\t", front); QueuePop(&pq); } printf("\n"); QueueDestroy(&pq); return 0; }
运行结果为： 
队列的部分应用
医院、营业厅、银行的抽号机（保证公平性，先来先被服务）
