系列文章目錄
文章目錄
- 系列文章目錄
- 前言
- 一、佇列的概念及結構
- 1.佇列的概念
- 2.佇列的結構
- 二、佇列的實作
- 1.定義用鏈表表示的佇列struct QueueNode
- 2.定義佇列的隊頭、隊尾指標struct Queue
- 3.佇列的初始化函式QueueInit
- 4.佇列的銷毀函式QueueDestroy
- 5.佇列的隊尾入資料函式QueuePush
- 6.佇列的隊頭出資料函式QueuePop
- 7.佇列的取出隊頭資料函式QueueFront
- 8.佇列的取出隊尾資料函式QueueBack
- 9.佇列是否為空函式QueueEmpty
- 10.佇列的長度函式QueueSize
- 總結
前言
一、佇列的概念及結構
1.佇列的概念
佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out) 入佇列：進行插入操作的一端稱為隊尾 出佇列：進行洗掉操作的一端稱為隊頭，
2.佇列的結構
二、佇列的實作
佇列也可以陣列和鏈表的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料，效率會比較低，
1.定義用鏈表表示的佇列struct QueueNode
代碼如下：
typedef int QDataType;
struct QueueNode //佇列結構,用鏈表來表示
{
struct QueueNode* next;
QDataType data;
};
2.定義佇列的隊頭、隊尾指標struct Queue
代碼如下：
struct Queue //佇列頭尾指標
{
struct QueueNode* head;
struct QueueNode* tail;
};
3.佇列的初始化函式QueueInit
代碼如下：
void QueueInit(struct Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
4.佇列的銷毀函式QueueDestroy
遍歷佇列，記住free前先存盤下一個節點的地址，
代碼如下：
void QueueDestroy(struct Queue* pq)
{
assert(pq);
struct QueueNode* cur = pq->head;
while (cur)
{
struct QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
5.佇列的隊尾入資料函式QueuePush
先開辟一個結點，在分兩種情況，一種情況佇列一個節點都沒有，那可以直接當節點，第二種情況佇列一開始有節點，尾插資料即可，
代碼如下：
void QueuePush(struct Queue* pq, QDataType x) //隊尾入資料
{
assert(pq);
struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
if (newnode == NULL)
{
printf("開辟失敗!\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL) //無節點
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
6.佇列的隊頭出資料函式QueuePop
代碼如下：
void QueuePop(struct Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next==NULL) //只有一個節點
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
struct QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
7.佇列的取出隊頭資料函式QueueFront
記住每次取資料前判斷佇列是否為空，不為空才進行下一步，
代碼如下：
QDataType QueueFront(struct Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
8.佇列的取出隊尾資料函式QueueBack
記住每次取資料前判斷佇列是否為空，不為空才進行下一步，
代碼如下：
QDataType QueueBack(struct Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
9.佇列是否為空函式QueueEmpty
代碼如下：
bool QueueEmpty(struct Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
10.佇列的長度函式QueueSize
代碼如下：
int QueueSize(struct Queue* pq)
{
int size = 0;
assert(pq);
struct QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
總結
以上就是今天要講的內容，本文僅僅簡單介紹了佇列的使用，對于佇列提供了一些簡便方法幫助我們解題，能使我們快速便捷地處理資料的函式和方法，另外這個結構雖然相比鏈表更簡單，使用代碼實作起來更容易寫，但我們也要認真學習，以后會發現佇列結構會帶來很多優勢，我們務必掌握，另外，如果有需要原始碼的私信我即可，還有，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/280733.html
標籤：其他
下一篇：備賽西門子——資訊化網路化