佇列概念：
只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出 FIFO(First In First Out)
入佇列：進行插入操作的一端稱為隊尾
出佇列：進行洗掉操作的一端稱為隊頭
佇列的實作
佇列也可以陣列和鏈表的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在數 組頭上出資料，效率會比較低，
下面用鏈式結構實作佇列：
// 鏈式結構：表示佇列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;//記錄下一個節點地址
QDataType data;//記錄資料
}QNode;
// 佇列的結構
typedef struct Queue
{
QNode* head;//記錄頭節點
QNode* tail;//記錄尾節點
}Queue;
開始先定義一個佇列，要先進行初始化；
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//開始沒有資料的時候，把記錄隊首，隊尾的節點都指向空初始化完成就可以添加資料了，注意一定只能從隊尾插入
兩種情況：第一種，當添加前沒有一個資料時，隊首、隊尾指標都要變化；
第二種，普通情況下只改變隊尾指標即可；
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;
}
}有入資料，就有出資料；第一種情況：出資料只要改變隊首指標，
注意：第二種情況：當只有一個資料時，隊首、隊尾都要指向空指標；
要檢驗當佇列中沒有資料時，直接退出（或斷言可以提示錯誤！）；
void QueuePop(Queue* pq)
{
//保證，傳入的資料不能為空，且佇列不能為空；
assert(pq);
assert(pq->head);
//下面是兩種情況；
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QueueNode* ret = pq->head->next;
free(pq->head);
pq->head = ret;
}
}有時需要回傳隊首、隊尾的資料，可以單獨實作下介面：
//回傳隊首資料；
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
//回傳隊尾資料；
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}在一些專案中，要知道當前佇列中的資料個數，以免多洗掉等操作造成崩潰
回傳資料個數的介面如下：
int QueueSize(Queue* pq)
{
assert(pq);
//定義一個整形，初始化為0，遍歷一遍鏈表
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
++n;
cur = cur->next;
}
return n;
}在判斷佇列資料為空的方法上，可以直接使用assert(pq->head);但是最好還是單獨封裝一個介面方便直接呼叫；介面直接回傳真偽；
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
//如果相等回傳真，也就是資料為空
//如果不相等回傳假，也就是資料不為空；謹慎使用；
}因為是動態開辟的記憶體，最后要手動釋放；
鏈表要遍歷一遍，全部依次釋放
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur= pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}上面實作的介面能滿足大多數情況需要，具體情況具體分析；
來看一下如何來呼叫這些介面：
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 7);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
int n=QueueSize(&q);
printf("%d\n", QueueSize(&q));
printf("%d\n", QueueFront(&q));
QueueDestroy(&q);
return 0;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348378.html
標籤：其他