目錄

前言

1. 隊列

1.1?隊列的概念

1.2 隊列的結構

2.?隊列的實現

2.1?隊列的定義

2.2 隊列的初始化

2.3?入隊

2.4 出隊

2.5?獲取隊頭元素

2.6?獲取隊尾元素

2.7?判斷空隊列

2.8?隊列的銷毀

3. 隊列完整源碼

Queue.h

Queue.c

---

• 🎈個人主頁：庫庫的里昂
• ?🎐C/C++領域新星創(chuàng)作者
• ?🎉歡迎 👍點贊?評論?收藏
• ?收錄專欄：數據結構與算法
• 🤝希望作者的文章能對你有所幫助，有不足的地方請在評論區(qū)留言指正，大家一起學習交流！🤗

前言

在前幾期的學習中，我們認識了順序表、鏈表和棧這三種線性表，而在本期學習中，我們將會認識別的線性表。跟隨我們的腳本，看看隊列有怎樣的特點。

1. 隊列

1.1?隊列的概念

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出?FIFO(First In First Out)。

• 入隊列：進行插入操作的一端稱為隊尾
• 出隊列：進行刪除操作的一端稱為隊頭

1.2 隊列的結構

2.?隊列的實現

2.1?隊列的定義

在入隊時相當于尾插，我們可以定義一個尾指針來記錄尾的位置。這就使我們傳指針時，要傳遞兩個指針，我們可以把指針放到結構體中，這樣在插入第一個時也可以解決要傳遞二級指針的問題。

定義尾指針可以避免每次尾插時要遍歷一遍鏈表。

typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueType* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

2.2 隊列的初始化

這里的 size 用來記錄隊列中數據的個數。

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.3?入隊

入隊相當于尾插，在入隊時我們要考慮鏈表是否為空。

void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

2.4 出隊

出隊相當于頭刪,與之前不同的是，當我們刪除最后一個節(jié)點，還要記得處理尾指針。

void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}

2.5?獲取隊頭元素

隊頭元素就是頭指針指向的節(jié)點的數據域。

QDateType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

2.6?獲取隊尾元素

我們通過尾指針可以直接找到隊尾，不用遍歷鏈表。

QDateType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}

2.7?判斷空隊列

利用bool的函數判斷隊列是否為空，當尾指針為空時，返回true；當尾指針不為空時，返回false。

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

2.8?隊列的銷毀

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

3. 隊列完整源碼

Queue.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueType* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);void QueueDstroy(Queue* pq);void QueuePush(Queue* pq, QDateType x);void QueuePop(Queue* pq);QDateType QueueFront(Queue* pq);QDateType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDstroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}QDateType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDateType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

本次的內容到這里就結束啦。希望大家閱讀完可以有所收獲，同時也感謝各位讀者三連支持。文章有問題可以在評論區(qū)留言，博主一定認真認真修改，以后寫出更好的文章。你們的支持就是博主最大的動力。