可以用數組、鏈表實現隊列，大致與棧相似，簡要介紹下隊列實現吧。值得注意的是循環隊列判空判滿操作，在用鏈表實現時需要額外思考下出入隊列條件。
設計頭文件
#ifndef ARRAY_QUEUE_H #define ARRAY_QUEUE_H#include <stdbool.h> #include <stdlib.h> #include <stdio.h> #define QUEUE_CAPACITY 10 typedef int ElementType;typedef struct {// 由于是固長數組隊列，所以直接把數組作為結構體對象的一個成員ElementType elements[QUEUE_CAPACITY];int front; // 隊頭元素的索引int rear; // 隊尾元素下一個位置的索引int size; // 隊列數組中實際存儲元素的個數 } ArrayQueue;// 初始化一個空隊列 ArrayQueue *queue_create(); // 銷毀一個隊列 void queue_destroy(ArrayQueue *q); // 判滿 bool is_full(ArrayQueue *q); // 判空 bool is_empty(ArrayQueue *q); // 入隊 bool enqueue(ArrayQueue *q, ElementType element); // 出隊 ElementType dequeue(ArrayQueue *q); // 訪問隊首元素 ElementType peek(ArrayQueue *q);#endif // !ARRAY_QUEUE_H
實現創建和銷毀隊列
// 初始化一個空隊列 ArrayQueue *queue_create() {return calloc(1, sizeof(ArrayQueue)); } // 銷毀一個隊列 void queue_destroy(ArrayQueue *q) {free(q); }
實現判空和判滿
// 判滿 bool is_full(ArrayQueue *q) {return q->size == QUEUE_CAPACITY; } // 判空 bool is_empty(ArrayQueue *q) {return q->size == 0; }
實現入隊操作
// 入隊 bool enqueue(ArrayQueue *q, ElementType element) {// 1.判滿if (is_full(q)) {printf("error: queue is full.\n");return false;}// 2.隊列沒滿時才入隊q->elements[q->rear] = element;// 3.更新rear索引q->rear = (q->rear + 1) % QUEUE_CAPACITY;// 4.更新sizeq->size++;return true; // 入隊成功 }
實現出隊操作
/* * 出隊就是將front索引的元素返回，然后將front索引后移 * 注意：不需要對front位置的元素做任何修改 * 因為front和rear之間的元素才是隊列元素，其它位置即便有值也不算隊列元素 * 其他位置的垃圾值，會隨著隊列出入隊操作逐漸被覆蓋 */ ElementType dequeue(ArrayQueue *q) {// 1.判空if (is_empty(q)) {printf("error: queue is empty.\n");exit(1);}// 2.隊列非空，記錄隊首元素以用于返回ElementType ret = q->elements[q->front];// 3.更新front索引q->front = (q->front + 1) % QUEUE_CAPACITY;// 4.不要忘記更新sizeq->size--;return ret; }
實現訪問隊首元素
// 訪問隊首元素 ElementType peek(ArrayQueue *q) {// 1.判斷隊列是否是空的if (is_empty(q)) {printf("error: queue is empty.\n");exit(1);}// 2.隊列非空返回隊首元素return q->elements[q->front]; }
擴展: 鏈式隊列
#ifndef LIST_QUEUE_H #define LIST_QUEUE_H#include <stdbool.h> #include <stdio.h> #include <stdlib.h>// 定義隊列中的元素類型 typedef int ElementType;// 隊列節點的結構 typedef struct node_s {ElementType data;struct node_s *next; } QueueNode;// 隊列的結構 typedef struct {QueueNode *front; // 隊頭結點指針QueueNode *rear; // 隊尾結點指針 } LinkedListQueue;// 函數聲明 // 創建鏈式隊列 LinkedListQueue *create_queue(); // 銷毀鏈式隊列 void destroy_queue(LinkedListQueue *q); // 入隊列 bool enqueue(LinkedListQueue *q, ElementType element); // 出隊列并返回隊頭元素 ElementType dequeue(LinkedListQueue *q); // 訪問隊頭元素 ElementType peek_queue(LinkedListQueue *q); // 判空 bool is_empty(LinkedListQueue *q);#endif // !LIST_QUEUE_H鏈式隊列實現-參考代碼
#include "list_queue.h"// 函數聲明 LinkedListQueue *create_queue() {return calloc(1, sizeof(LinkedListQueue)); }void destroy_queue(LinkedListQueue *q) {// 從隊頭開始遍歷鏈表，銷毀每一個結點QueueNode *current = q->front;while (current != NULL) {QueueNode *temp = current->next;free(current);current = temp;}// 銷毀隊列結構體free(q); }bool is_empty(LinkedListQueue *q) {// 隊頭指針是空指針，即表示空隊列return q->front == NULL; }// 入隊操作: 只能在隊尾插入一個結點 // 由于已存在尾指針，所以這里的操作就是鏈表尾插 bool enqueue(LinkedListQueue *q, ElementType element) {QueueNode *new_node = malloc(sizeof(QueueNode));if (new_node == NULL) {printf("Error: malloc failed in enqueue.\n");return false;}// 初始化新結點new_node->data = element;new_node->next = NULL;// 開始進行尾插法插入一個結點// 分兩種情況：如果尾插插入的是第一個結點需要同步更新頭指針，否則僅需要更新尾指針if (q->front == NULL) {// 插入的是第一個結點q->front = new_node;q->rear = new_node;}else {// 插入的不是第一個結點q->rear->next = new_node;q->rear = new_node;}return true; }// 出隊，在隊頭刪除一個結點。也就是在刪除鏈表的第一個結點 ElementType dequeue(LinkedListQueue *q) {if (is_empty(q)) {printf("Error: queue is empty.\n");exit(1);}QueueNode *tmp = q->front;// 將出隊的結點數據保存ElementType remove_data = tmp->data;// 更新隊頭指針q->front = tmp->next;if (q->front == NULL) {// 如果隊頭更新后,隊列為空,說明出隊的就是最后一個元素// 于是同步更新隊尾指針q->rear = NULL;}free(tmp);return remove_data; }// 訪問隊頭元素但不出隊 ElementType peek_queue(LinkedListQueue *q) {if (is_empty(q)) {printf("Error: queue is empty.\n");exit(1);}return q->front->data; }
擴展: 動態數組隊列
既然可以實現固定長度的隊列，那么基于動態數組，就可以實現一個動態數組隊列
#ifndef DYNAMIC_QUEUE_H #define DYNAMIC_QUEUE_H#include <stdbool.h> #include <stdlib.h> #include <stdio.h>typedef int ElementType; // 該隊列當前存儲int元素 #define DEFAULT_CAPACITY 10 // 數組隊列的初始長度是10 #define THRESHOLD 1000 // 超過閾值每次擴容1.5倍擴，否則2倍的擴// 定義隊列結構體 typedef struct {ElementType *data; // 動態數組存儲隊列元素int front; // 標記隊頭元素的索引int rear; // 標記隊尾元素下一個位置的索引int size; // 當前隊列中元素數量int capacity; // 隊列容量 } DynamicQueue;// 隊列基本操作函數聲明 // 創建動態數組隊列 DynamicQueue *create_queue(); // 銷毀動態數組隊列 void destroy_queue(DynamicQueue *q); // 判空 bool is_empty(DynamicQueue *q); // 判滿 bool is_full(DynamicQueue *q); // 入隊列 bool enqueue(DynamicQueue *q, ElementType data); // 出隊列并且返回隊頭元素 ElementType dequeue(DynamicQueue *q);#endif // DYNAMIC_QUEUE_H參考代碼
#include "dynamic_queue.h"// 創建并初始化隊列 DynamicQueue *create_queue() {DynamicQueue *q = calloc(1, sizeof(DynamicQueue));if (q == NULL) {printf("error: calloc failed in create_queue.\n");return NULL;}// front、rear、size自動初始化0值，無需再手動初始化了q->data = calloc(DEFAULT_CAPACITY, sizeof(ElementType)); // 使用calloc避免隨機值if (q->data == NULL) {printf("error: calloc failed in create_queue.\n");free(q);return NULL;}q->capacity = DEFAULT_CAPACITY;return q; }// 銷毀隊列 void destroy_queue(DynamicQueue *q) {free(q->data);free(q); }// 檢查隊列是否為空 bool is_empty(DynamicQueue *q) {return q->size == 0; }// 檢查隊列是否已滿 bool is_full(DynamicQueue *q) {return q->size == q->capacity; }/*這里采用一種簡單粗暴的擴容手段:直接分配新容量的內存塊然后遍歷舊內存塊中的隊列元素,將這些元素全部從頭開始復制到新內存塊中這樣的操作在完成后,需要更新front索引和rear索引 */ static bool resize_queue(DynamicQueue *q) {int old_capacity = q->capacity;int new_capacity = (old_capacity < THRESHOLD) ?(old_capacity << 1) :(old_capacity + (old_capacity >> 1));// 重新分配一個新的,更長的動態數組ElementType *new_data = malloc(new_capacity * sizeof(ElementType));if (new_data == NULL) {printf("error: realloc failed in resize_queue.\n");return false;}int curr = q->front; // curr索引用于遍歷整個隊列中的元素int index = 0;while (index < q->size) {new_data[index] = q->data[curr];curr = (curr + 1) % q->capacity;index++;} // while循環結束時,new_data就從頭開始包含了隊列的所有元素 free(q->data);q->data = new_data;q->front = 0;q->rear = q->size;q->capacity = new_capacity;return true; }// 入隊操作 bool enqueue(DynamicQueue *q, ElementType data) {if (is_full(q)) {if (!resize_queue(q)) {printf("error: 擴容失敗.\n");return false; // 隊列擴容失敗,入隊也同步失敗}}q->data[q->rear] = data;q->rear = (q->rear + 1) % q->capacity; // 循環隊列q->size++;return true; }// 出隊操作 ElementType dequeue(DynamicQueue *q) {if (is_empty(q)) {printf("error: 隊列為空，無法出隊。\n");exit(1);}ElementType item = q->data[q->front];q->front = (q->front + 1) % q->capacity; // 循環隊列q->size--;return item; }
隊列的應用場景
- 操作系統的任務調度，進程/線程按照到達順序來排隊等待CPU執行權。
- 各種數據處理系統中的緩沖區/緩存機制。比如stdin/stdout緩沖區，先輸入緩沖區的數據，總是先從緩沖區輸出。
- 打印機的任務管理，當多個打印任務同時到達時，它們在隊列中排隊，按照提交的順序進行打印。
- 后端應用系統中的消息隊列。
- 廣度優先搜索(比如二叉搜索樹的層次遍歷)
)
