資料結構之佇列詳解
文章目錄
- 資料結構之佇列詳解
- 前言
- 一、佇列的概念及結構
- 二、佇列的實作
- 1.基本結構
- 2.基本操作
- （1）初始化和銷毀
- （2）出隊入隊
- （3）判空
- （4）獲取元素
- 三、回圈佇列
- 總結
前言
在介紹玩堆疊之后我們來介紹下佇列基本結構
一、佇列的概念及結構
- 佇列：只允許在『 一端 』進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有『 先進先出 』 FIFO(First In First Out) 入佇列：進行插入操作的一端稱為隊尾 出佇列：進行洗掉操作的一端稱為隊頭
- 上圖演示：
二、佇列的實作
- 佇列也可以『 陣列 』和『 鏈表 』的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料，效率會比較低，
『』
1.基本結構
代碼如下（示例）：
// 鏈式結構：表示佇列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 佇列的結構
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
- 這里注意QListNode表示的是每一個『 存放資料 』的節點，Queue是『 整個佇列 』，含有指向隊頭和隊尾的兩個QListNode* 指標，因此我們在函式傳參的時候只需要傳遞Queue相關的地址來操作佇列即可
2.基本操作
（1）初始化和銷毀
- 初始化只需要把頭尾置空即可，但是銷毀不僅僅要銷毀佇列頭尾指標，還要釋放每一個存放資料的節點
// 初始化佇列
void QueueInit(Queue* q)
{
assert(q);
q->front = q->tail = NULL;
}
// 銷毀佇列
void QueueDestroy(Queue* q)
{
assert(q);
QueueNode* cur = q->front;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
q->front = q->tail = NULL;
}
（2）出隊入隊
- 隊尾入佇列,考慮兩種情況，一是佇列為空直接佇列頭尾指標指向新節點，二是不為空，需要鏈接新節點到尾部
// 隊尾入佇列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = data;
newnode->next = NULL;
if (q->front == NULL)
{
q->front = q->tail = newnode;
}
else
{
q->tail->next = newnode;
q->tail = newnode;
}
}
- 出佇列時候需要特殊注意一種情況，正常做法是把頭節點出隊free掉，并且頭指標指向下一個，但是要考慮只有一個資料出隊時候！！！當你頭指標釋放完指空的時候此刻，尾指標還在指向釋放掉的空間，成了野指標！！！因此要置空，
// 隊頭出佇列
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
QueueNode* next = q->front->next;
free(q->front);
q->front = next;
if (q->front == NULL)
{
q->tail = NULL;
}
}
（3）判空
// 檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL;
}
（4）獲取元素
// 獲取佇列頭部元素
QDataType QueueFront(Queue* q)
{
assert(q);//斷言防止傳進來空指標
assert(!QueueEmpty(q));//斷言防止佇列空
return q->front->data;
}
// 獲取佇列隊尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->tail->data;
}
// 獲取佇列中有效元素個數
int QueueSize(Queue* q)
{
assert(q);
int n = 0;
QueueNode* cur = q->front;
while (cur)
{
cur = cur->next;
n++;
}
return n;
}
三、回圈佇列
- 實際中我們有時還會使用一種佇列叫回圈佇列，環形佇列可以使用陣列實作也可以用回圈鏈表來實作
- 當頭指標和尾指標相遇時佇列已滿，具體可以參考這篇文章
總結
以上就是佇列基礎內容和操作，實際上堆疊和佇列的實際應用還是很多，比如叫號機等等，那么佇列和堆疊的常見題型下次見，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344240.html
標籤：其他
下一篇：鏈表OJ題（一）