隊列（Queue）是一種特殊的線性數據結構，它遵循FIFO（First In First Out，先入先出）的原則。隊列只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。隊列中沒有元素時，稱為空隊列。
隊列的數據元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以又稱為先進先出（FIFO—first in first out）線性表，簡稱隊列。
在程序中，隊列常常被用來處理需要按一定順序處理的任務，例如打印任務隊列、線程任務調度等。此外，隊列也在許多算法中發揮著重要作用，如廣度優先搜索（BFS）等。
隊列的實現方式有多種，包括基于數組的靜態隊列、基于鏈表的動態隊列等。在實際應用中，可以根據具體需求選擇合適的隊列實現方式。
隊列的主要特點包括：
先進先出：隊列中的元素按照進入隊列的先后順序依次出隊。
操作受限：隊列只允許在隊尾插入元素（入隊），在隊頭刪除元素（出隊），其他位置的元素無法直接訪問或修改。
有序性：由于遵循FIFO原則，隊列中的元素始終保持一定的順序。
隊列的鏈式存儲結構為：
typedef int QDataType;
// 鏈式結構：表示隊列
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 隊列的結構
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;隊列的順序存儲結構為：
#define MAXQSIZE 100 //隊列可能達到的最大長度
typedef struct
{QElemType* base; //存儲空間的基地址int front; //頭指針int rear; //尾指針
}SqQueue;
假設當前隊列分配的空間最大為6，則當隊列處于上圖的最后一個狀態時，就不可以在繼續插入新的隊尾元素，否則會出現溢出的情況，即因數組越界而導致程序的非法操作錯誤。但是隊列的實際空間并未占滿，這種現象就被稱為假溢出。
那么怎么解決這個問題呢？
我們就可以運用一個較為巧妙的方法：循環隊列
但這里我們面臨一個問題，就是front==rear的時候時隊空還是隊滿
可以發現并不好來判斷
下面我們就有兩種方法來解決下列問題
| 多開辟用一個空間（即少用一個元素空間），假設隊列的空間為k+1，但當有m個元素的時候就認為時隊滿 | |
|---|---|
| 即(Q.rear + 1)%(k+1) == Q.front即為隊滿，Q.rear == Q.front時為隊空 | |
| 用一個標志位來Size判斷隊列是空還是隊滿 | |
| 即當Size == k時為隊滿，Size == 0時為隊空 | – |
下面我們就用一種方法來實現循環隊列
結構體定義：
typedef int QDataType;
typedef struct {QDataType* a;int front;//指向頭int rear;//指向尾的下一位int k;//隊列的長度
} MyCircularQueue;
創建隊列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//開辟一個大小為（k+1）的數組空間，多開一個空間以便判斷隊列為空還是滿的//防止假溢出現象obj->a = (QDataType*)malloc((k + 1) * sizeof(QDataType));obj->k = k;obj->front = obj->rear = 0;return obj;
}
判斷隊空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}
判斷隊滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
入隊
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj->a[obj->rear] = value;obj->rear++;obj->rear %= obj->k + 1;return true;
}
出隊
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj->front++;obj->front %= obj->k + 1;return true;
}
取出隊頭元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}取出隊尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}
銷毀隊列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}
