上期我們已經(jīng)學習了數(shù)據(jù)結(jié)構(gòu)中的棧，這期我們開始學習隊列。
目錄
1.隊列的概念及結(jié)構(gòu)
2.隊列的實現(xiàn)
隊列結(jié)構(gòu)體定義
常用接口函數(shù)
初始化隊列
隊尾入隊列
隊頭出隊列
獲取隊列頭部元素、
獲取隊列隊尾元素
獲取隊列中有效元素個數(shù)
檢測隊列是否為空
銷毀隊列
3.循環(huán)隊列
1.隊列的概念及結(jié)構(gòu)
隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出 FIFO(First In First Out) 入隊列：進行插入操作的一端稱為隊尾 出隊列：進行刪除操作的一端稱為隊頭
?從網(wǎng)上找來的隊列結(jié)構(gòu)示意圖：
2.隊列的實現(xiàn)
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。
隊列結(jié)構(gòu)體定義
我們使用的是不帶頭節(jié)點的單向鏈表來實現(xiàn)隊列，而隊列要在隊尾插入數(shù)據(jù)，因此每次都要遍歷鏈表找隊尾，這樣會使得程序的運行效率變低。這里采取了一種解決辦法：定義一個指向隊尾的指針tail，?每次插入新的數(shù)據(jù)就只要將tail中的next指針指向新節(jié)點即可，同時插入新的數(shù)據(jù)后再更新tail的位置。
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;這里單獨定義了一個結(jié)構(gòu)體來存儲頭指針head和尾指針tail。
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;常用接口函數(shù)
//初始化
void QueueInit(Queue* pq);
//插入數(shù)據(jù)
void QueuePush(Queue* pq, QDataType x);
//銷毀
void QueueDestroy(Queue* pq);
//彈出
void QueuePop(Queue* pq);
//取隊頭數(shù)據(jù)
QDataType QueueFront(Queue* pq);
//取隊尾數(shù)據(jù)
QDataType QueueBack(Queue* pq);
//判斷是否為空
bool QueueEmpty(Queue* pq);
//計算大小
int QueueSize(Queue* pq);初始化隊列
由于這里使用的是不帶頭節(jié)點的單向鏈表，所以初始化隊列只需要將頭指針和尾指針都指向空即可。如果是要定義一個帶頭節(jié)點的鏈表，則需要在這里創(chuàng)建一個頭節(jié)點
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}隊尾入隊列
由于我們已經(jīng)將鏈表的尾部給記錄了下來，所以不需要遍歷鏈表，只要尾部節(jié)點中的next指針指向新節(jié)點
?同時需要判斷鏈表是否為空，如果鏈表是第一次插入數(shù)據(jù)，需要將頭指針和尾指針都指向新節(jié)點。
//隊尾插入數(shù)據(jù)
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//創(chuàng)建新節(jié)點
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
//將新節(jié)點鏈接起來
if (pq->tail == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}隊頭出隊列
在彈出數(shù)據(jù)之前，要判斷鏈表是否為空，這里可以用assert斷言：
接下來是具體的彈出操作：
- 判斷隊列是否只有一個節(jié)點。如果是，表示隊列中只剩下一個節(jié)點，直接釋放這個節(jié)點，同時將頭指針和尾指針都置為空。
- 如果隊列中有多個節(jié)點，將頭指針
pq->head指向下一個節(jié)點，然后釋放原來的頭節(jié)點。這樣就完成了一個節(jié)點的彈出操作。
//彈出
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}獲取隊列頭部元素、
返回隊列頭節(jié)點的數(shù)據(jù)?pq->head->data 即可。
//取隊頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}獲取隊列隊尾元素
- 返回隊列尾節(jié)點的數(shù)據(jù)?
pq->tail->data?即可。
//取隊尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}獲取隊列中有效元素個數(shù)
計算大小有多種方法，常用的兩種是：
一種是在定義Queue結(jié)構(gòu)體時增加一個用于計數(shù)的變量，每次插入數(shù)據(jù)就自加一下，彈出數(shù)據(jù)就自減一下。
typedef struct Queue
{
int size;
QNode* head;
QNode* tail;
}Queue;另外一種是遍歷鏈表，這種方法效率比較低，當然，如果你不在乎這點效率問題，你可以使用這種方法，我們這里也是使用這種方式：
//計算大小
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
int size = 0;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}檢測隊列是否為空
如果頭節(jié)點head為空，則隊列為空。
//判斷是否為空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
} 銷毀隊列
銷毀隊列和銷毀普通鏈表一樣：
- 使用一個指針
cur指向隊列的頭節(jié)點pq->head。 - 在一個循環(huán)中，遍歷隊列的所有節(jié)點，直到
cur為空。 - 循環(huán)結(jié)束后，將隊列的頭指針和尾指針都置為空，表示隊列已經(jīng)被銷毀。
//銷毀
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
3.循環(huán)隊列
循環(huán)隊列的概念
實際中我們有時還會使用一種隊列叫循環(huán)隊列。如操作系統(tǒng)課程講解生產(chǎn)者消費者模型 時可以就會使用循環(huán)隊列。環(huán)形隊列可以使用數(shù)組實現(xiàn)，也可以使用循環(huán)鏈表實現(xiàn)。
循環(huán)隊列是一種在固定大小的數(shù)組或鏈表上實現(xiàn)的隊列，它可以通過循環(huán)利用數(shù)組或鏈表中的空間來實現(xiàn)入隊和出隊操作。當隊列滿時，新的元素會從開頭重新進入隊列，實現(xiàn)循環(huán)利用。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ?
通常循環(huán)隊列有兩個指針，一個是頭指針head,另一個是尾指針tail, 當head和tail指向同一個節(jié)點時，表示隊列為空。
當從隊尾插入一個數(shù)據(jù)時，tail就會向后移動。當彈出隊頭數(shù)據(jù)時，head向后移動。
空的循環(huán)隊列：
插入3個數(shù)據(jù)：
?彈出一個隊首的數(shù)據(jù)：
按照上面這種情況，當隊列已經(jīng)滿了的時候，head和tail也會指向同一個節(jié)點。這樣我們就無法區(qū)分隊列是空還是滿了。因此想出了這兩種方法：
方案一：設(shè)置一個變量size計算隊列元素個數(shù)，如果size與隊列容量相等時，說明隊列已滿。
方案二：多開一個空間，不存儲數(shù)據(jù)。? 當 tail->next==head 時，表示已經(jīng)滿了。
一般方案二的實用性較強。
?用方案二這種方法我們會發(fā)現(xiàn)，如果使用鏈表的形式實現(xiàn)隊列，由于tail每次都是指向尾節(jié)點的下一個節(jié)點，當我們要取尾節(jié)點的數(shù)據(jù)時，不是很方便。
因此，我們可以使用數(shù)組來實現(xiàn)隊列。
用數(shù)組實現(xiàn)循環(huán)隊列
原題鏈接：力扣
文章來源：http://www.zghlxwxcb.cn/news/detail-536909.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-536909.html
typedef struct
{
int* a;
int k;
int head;
int tail;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//帶有一個不存儲數(shù)據(jù)的頭
obj->a = (int*)malloc(sizeof(int)*(k+1));
obj->k = k;
obj->head = obj->tail = 0;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
int next = obj->tail + 1;
if(obj->tail == obj->k)
{
next = 0;
}
return next == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->tail] = value;
obj->tail++;
//tail到達數(shù)組臨界，調(diào)整tail位置到開頭，以達到循環(huán)隊列效果
if(obj->tail == obj->k + 1)
{
obj->tail = 0;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->head++;
if(obj->head == obj->k + 1)
{
obj->head = 0;
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
int prev = obj->tail - 1;
if(obj->tail == 0)
{
prev = obj->k;
}
return obj->a[prev];
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】棧和隊列(隊列篇）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
