佇列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，佇列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。佇列的特性總結為：先進先出。 這中特性在日常中類似於排隊，先來的先進行服務！

我們使用連結串列實現佇列，一個頭節點和一個為節點表示佇列的頭部和尾部。出佇列和入佇列的時間複雜度為 O(1)。空間複雜度為 O(n)

為充分利用向量空間，克服"假溢位"現象的方法是：將向量空間想象為一個首尾相接的圓環，並稱這種向量為迴圈向量。儲存在其中的佇列稱為迴圈佇列。迴圈佇列是把順序佇列首尾相連，把儲存佇列元素的表從邏輯上看成一個環，成為迴圈佇列。

單向佇列的實現方式:

#include <stdio.h>#include <stdlib.h>typedef struct Node{    // 節點的值    int val;    // 節點的在一個節點    struct Node *next;} Node;typedef struct Queue{    /* data */    // 佇列的頭節點    Node *head;    // 佇列的尾節點    Node *tail;    // 佇列的元素數量    int len;} Queue;//  初始化佇列Queue *init(){    // 申請空間    Queue *q = malloc(sizeof(Queue));    // 初始化成員屬性    q->head = q->tail = NULL;    q->len = 0;    return q;}

// 元素入佇列void push(Queue *q, int val){    // 申請空間    Node *node = malloc(sizeof(Node));    node->val = val;    node->next = NULL;    // 判斷佇列是不是為空    if (q->len == 0)    {        // 直接賦值        q->head = q->tail = node;    }    else    {        // 將元素新增至佇列末尾        q->tail->next = node;        q->tail = node;    }    // 長度 + 1    q->len++;}

// 元素出佇列int pop(Queue *q){    if (q->len > 0)    {        // 獲取頭節點的值        Node *h = q->head;        int val = h->val;        // 沒有其他元素重置為NULL        if (h->next == NULL)        {            q->head = q->tail = NULL;        }        else        {            q->head = h->next;        }        // 釋放節點空間        free(h);        q->len--;        return val;    }    return 0xFFFFFF;}

// 返回佇列的長度int size(Queue *q){    if (q == NULL)    {        return -1;    }    return q->len;}void printQueue(Queue *q){    if (q != NULL)    {        Node *h = q->head;        while (h != NULL)        {            printf("%d->", h->val);            h = h->next;        }        printf("\n");    }}// 銷燬佇列void destory(Queue *q){    if (q != NULL)    {        // 逐個釋放節點的元素        Node *h = q->tail;        while (h != NULL)        {            free(h);            h = h->next;        }        // 釋放佇列        free(q);    }}

int main(){    Queue *queue = init();    push(queue, 10);    push(queue, 11);    push(queue, 12);    push(queue, 13);    push(queue, 14);    printQueue(queue);    printf("%d\n", size(queue));    printf("%d\n", pop(queue));    printf("%d\n", size(queue));    printQueue(queue);    destory(queue);    return 0;}/*10->11->12->13->14->510411->12->13->14->*/

從佇列的特性中我們可以看到，佇列主要用在先來先服務的場景中。生活中與之相關的就是 12306 的候補買票了以及一些排隊的場景下，這種順序服務的思想在一些訊息隊列當中也有體現。

相關的程式碼我已上傳到 gitlab: https://gitlab.com/BitLegend/c-data-structure.git

此後的資料結構程式碼我都會上傳在這個倉庫中，需要的同學可以自己下載