??隊列的概念及結構
- 隊列的概念：
隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out) 新添加的元素添加到隊尾,只能從隊頭取出元素。
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
- 隊列特征如下:
入隊(Enqueue):通過尾指針添加元素到隊列尾部,即向隊列中插入元素。
出隊(Dequeue):通過頭指針刪除隊列頭部元素,即從隊列中移除元素。
空隊列:當頭指針和尾指針相同時,表示隊列為空。
滿隊列:當尾指針指向隊列容量最大位置時,表示隊列已滿。
- 常用的隊列結構包括數(shù)組和鏈表實現(xiàn):
數(shù)組實現(xiàn)隊列:使用一維數(shù)組存儲元素,頭指針和尾指針分別指向數(shù)組的下標位置。
鏈表實現(xiàn)隊列:每個元素使用一個節(jié)點存儲,頭節(jié)點和尾節(jié)點通過指針鏈接實現(xiàn)隊列。
?? 隊列的順序實現(xiàn)
頭文件：Queue_order.h
# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int QDataType;
typedef struct Queue
{
QDataType data[MAX_SIZE];
int front;
int rear;
int size;//記錄隊列中元素數(shù)量
}Queue;
//初始化隊列
void InitQueue(Queue* pq);
//入隊操作
void EnQueue(Queue* pq,int value);
//出隊
QDataType DeQueue(Queue* pq);
//獲取隊首元素
QDataType FrontQueue(Queue* pq);
//獲取隊尾元素
QDataType RearQueue(Queue* pq);
//獲取隊列中有效元素個數(shù)
QDataType SizeQueue(Queue* pq);
//隊列是否為空
QDataType IsEmpty(Queue* pq);
//隊列是否為滿
QDataType IsFull(Queue* pq);
//銷毀隊列
void DestroyQueue(Queue* pq);
??初始化
//初始化隊列
void InitQueue(Queue* pq)
{
pq->front = -1;
pq->rear = -1;
pq->size = 0;
}
front和rear都指向-1,表示隊列中沒有數(shù)據(jù)。size為0,表示隊列中沒有元素。
??入隊
//入隊
void EnQueue(Queue* pq, int value)
{
if (pq->front == MAX_SIZE - 1)
{
printf("隊列滿了，入隊操作失敗");//檢查隊列是否已滿,如果front指針指向的下一個位置就是MAX_SIZE-1,表示隊列已滿,打印錯誤信息并返回。
return;
}
if (pq->front == -1)
{//如果front為-1,表示隊列為空,將front指針置0。
pq->front = 0;
}
pq->rear++;//如果front為-1
pq->data[pq->rear] = value;//表示隊列為空
pq->size++;//加完了別忘了size++
}
??出隊
//出隊
QDataType DeQueue(Queue* pq)
{
if (-1 == IsEmpty)
{
printf("隊列為空！");
return -1;//返回一個特定的值表示隊列為空
}
int value = pq->data[pq->front];
pq->front++;
pq->size--;
return value;
}
檢查滿是為了防止入隊越界,front為-1時,表示隊列為空,需要將front置0,rear后移一位指向新的元素位置，將元素值寫入data數(shù)組，size計數(shù)增加。
??獲取隊列首元素
//獲取隊首元素
QDataType FrontQueue(Queue* pq)
{
if (-1 == IsEmpty)
{
printf("隊列為空！");
return -1;//返回一個特定的值表示隊列為空
}
return pq->data[pq->front];
}
??獲取隊列尾部元素
//獲取隊列尾部元素
QDataType RearQueue(Queue* pq)
{
if (0 == IsEmpty)
{
printf("隊列為空！");
return -1;//返回一個特定的值表示隊列為空
}
return pq->data[pq->rear];
}
??獲取隊列中有效元素個數(shù)
//獲取隊列中有效元素個數(shù)
QDataType SizeQueue(Queue* pq)
{
return pq->size;
}
?? 隊列是否為空
//隊列是否為空
QDataType IsEmpty(Queue* pq)
{
if (pq->front == -1 || (pq->front > pq->rear))
{
//隊列為空
return -1;
}
else
{
//隊列不為空
return 1;
}
}
注意：在隊列中，如果 front 指針大于 rear 指針，表示隊列為空。這是因為 front 指針指向隊列的第一個元素，而 rear 指針指向隊列的最后一個元素。如果 front 指針大于 rear 指針，意味著隊列中沒有元素，或者已經(jīng)出隊了所有的元素。
考慮一個隊列中有一個元素的情況。初始時 front 和 rear 都指向該元素，而當該元素出隊時，front 指針會被移動到下一個位置，這時 front 指針就比 rear 指針大，表示隊列已經(jīng)為空。
??查看隊列是否為滿
//查看隊列是否為滿
QDataType IsFull(Queue* pq)
{
return (pq->rear == MAX_SIZE - 1);
}
??銷毀隊列
//銷毀隊列
void DestroyQueue(Queue* pq)
{
InitQueue(pq);//重新初始化隊列，清空元素并釋放內存
}
??測試
源文件Test.c
# define _CRT_SECURE_NO_WARNINGS 1
#include"Queue_order.h"
int main()
{
Queue Pq;
InitQueue(&Pq);
EnQueue(&Pq, 10);
EnQueue(&Pq, 20);
EnQueue(&Pq, 30);
printf("Front element: %d\n", FrontQueue(&Pq));
printf("Rear element: %d\n", RearQueue(&Pq));
printf("Front element: %d\n", SizeQueue(&Pq));
printf("Front element: %d\n", FrontQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq)); // 嘗試從空隊列中出隊
printf("Queue size: %d\n", SizeQueue(&Pq));
printf("Is queue empty? %s\n", IsEmpty(&Pq) ? "Yes" : "No");
}
?? 順序隊列的假溢出
順序隊列的假溢出指的是，隊列在結構上沒有真正滿溢，但是在邏輯上已經(jīng)無法再插入新元素了。
在隊尾指針已經(jīng)指向數(shù)組的最后一個位置，但數(shù)組中仍然有空閑空間時，確實是隊列溢出的情況，而不是假溢出。這種情況通常是由于沒有充分利用隊列所分配的存儲空間所導致的，因此會造成隊列操作的限制。
“假溢出” 通常用于表示隊列中還有空閑空間，但因某種原因無法繼續(xù)插入元素的情況，這可能是由于某些限制條件或錯誤的隊列操作所導致的。例如，可能存在對隊列的錯誤管理，使得無法正確地判斷隊列是否已滿，導致了插入元素失敗的情況。
舉個例子：
在一個順序隊列中，隊列大小為5，已包含四個元素 value1-2-3-4，rear在隊尾4的位置。
當出隊兩個元素value1-2時，隊列前面多出來了兩位置
當你想再插入來兩個數(shù)據(jù)時，隊列確只能插入一個數(shù)據(jù)，但是隊列其實不能插入數(shù)據(jù)了。
這是隊列在結構上沒有真正滿溢,但是在邏輯上已經(jīng)無法再插入新元素了。
怎么優(yōu)化這個假溢出呢？兩種常見的方法：
- 循環(huán)隊列: 循環(huán)隊列是一種特殊的順序隊列，通過將隊列的數(shù)組視為一個循環(huán)的環(huán)形結構，使得在隊列尾部插入元素時可以利用數(shù)組頭部的空閑空間，從而解決了假溢出的問題。循環(huán)隊列中，當隊尾指針指向數(shù)組的末尾時，再插入元素時將其指向數(shù)組的起始位置，這樣就形成了一個循環(huán)。通過這種方式，可以充分利用數(shù)組空間，避免了假溢出。
- 動態(tài)擴容: 動態(tài)擴容是在順序隊列滿時，自動增加數(shù)組的大小以容納更多元素。當隊列滿時，分配一個更大的數(shù)組，并將原有的元素復制到新數(shù)組中，然后釋放原來的數(shù)組。這樣可以確保隊列始終有足夠的空間來插入新的元素，從而避免假溢出。動態(tài)擴容的關鍵是選擇適當?shù)臄U容策略，以及控制擴容時機，以避免頻繁的擴容操作帶來的性能開銷。
??循環(huán)隊列概念
循環(huán)隊列是一種基于數(shù)組實現(xiàn)的隊列數(shù)據(jù)結構，其特點是通過循環(huán)利用數(shù)組空間來實現(xiàn)隊列的操作。循環(huán)隊列的數(shù)組通常被看作一個環(huán)形的結構，隊列的頭部和尾部指針在數(shù)組中循環(huán)移動，使得當尾部指針到達數(shù)組末尾時，可以將其“循環(huán)”到數(shù)組的起始位置，從而避免了溢出或假溢出的情況。
循環(huán)隊列看似循環(huán)，其實是固定數(shù)組不斷往復的過程，我們可以模擬普通數(shù)組來實現(xiàn)：
如圖：data 表示一個數(shù)據(jù)域，int 為類型，當然你也可以修改為任意自定義的類型，也可以是復雜的結構體類型。
MAX_SIZE ：表示循環(huán)最大容量，可進行放數(shù)據(jù)的操作空間
rear代表尾指針，入隊時移動。
front代表頭指針，出隊時移動。
size記錄當前有效數(shù)據(jù)的多少
代碼：
#define MAX_SIZE 5
typedef struct {
int data[MAX_SIZE];
int front; // 隊列頭指針
int rear; // 隊列尾指針
int size; // 隊列當前元素個數(shù)
} Cir_Queue;
??循環(huán)隊列的初始化
對于循環(huán)隊列來說,front從0開始是合理的,因為數(shù)據(jù)數(shù)組是環(huán)狀結構,front從0開始可以實現(xiàn)隊列元素的循環(huán)利用。
rear從0開始表示隊列此時為空,front和rear指針都指向數(shù)組第一個位置。
將隊列當前元素個數(shù)size清零,表示隊列為空。
// 初始化隊列
void initQueue(Cir_Queue* queue)
{
queue->front = 0;將隊列頭指針front設置為0。
queue->rear = 0;將隊列尾指針rear也設置為0。
queue->size = 0;
}
??循環(huán)隊列的入隊操作
入隊操作與順序隊列相同，只需將rear向后移動。但要注意，如果rear達到隊列的上限，需從頭開始移動。建議使用余數(shù)法，確保操作在隊列空間內進行，避免一次錯誤導致整體崩潰。
要進行入隊操作，得先判斷隊列是不是滿了rear==front來判斷隊空，也可以用size。
// 入隊操作
void enqueue(Cir_Queue* queue, int value)
{
if (queue->size == MAX_SIZE)
{
printf("Queue is full. Enqueue operation failed.\n");
return;
}
queue->data[queue->rear] = value;
queue->rear = (queue->rear + 1) % MAX_SIZE; // 使用(rear+1)%MAX_SIZE更新rear指針，循環(huán)移動
queue->size++;
}
檢查隊列是否已滿，可通過判斷size是否等于MAX_SIZE來確定。如果已滿，則打印提示信息并返回；將數(shù)值value賦給data數(shù)組的rear索引位置，并使用(rear+1)%MAX_SIZE更新rear指針。這里使用模運算來實現(xiàn)rear指針的循環(huán)移動。當rear指向最后一個位置時，利用模運算使其指向第一個位置，實現(xiàn)循環(huán)利用數(shù)組。然后將size增加1，表示元素個數(shù)加1。
?? 循環(huán)隊列的出隊操作
// 出隊操作
int dequeue(Cir_Queue* queue)
{
if (queue->size == 0)
{
printf("Queue is empty. Dequeue operation failed.\n");
return -1;
}
int value = queue->data[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE; // 循環(huán)移動
queue->size--;
return value;
}
使用(front+1)%MAX_SIZE更新front指針，這里也使用模運算實現(xiàn)front指針的循環(huán)移動。當front指向最后一個位置時,利用模運算讓它指向第一個位置。
?? 查看隊首元素
// 查看隊首元素
int front(Cir_Queue* queue)
{
if (queue->size == 0)
{
printf("Queue is empty. Front operation failed.\n");
return -1;
}
return queue->data[queue->front];
}
??查看隊尾元素
// 查看隊尾元素
int rear(Cir_Queue* queue)
{
if (queue->size == 0)
{
printf("Queue is empty. Rear operation failed.\n");
return -1;
}
return queue->data[(queue->rear - 1 + MAX_SIZE) % MAX_SIZE];
}
??查看隊列是否為空
// 查看隊列是否為空
int isEmpty(Cir_Queue* queue)
{
return (queue->size == 0);
}
??查看隊列是否已滿
// 查看隊列是否已滿
int isFull(Cir_Queue* queue)
{
return (queue->size == MAX_SIZE);
}
?? 測試下循環(huán)隊列
int main() {
Cir_Queue queue;
initQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
printf("Front element: %d\n", front(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
enqueue(&queue, 80);
enqueue(&queue, 90);
printf("Front element: %d\n", front(&queue));
printf("rear element: %d\n", rear(&queue));
return 0;
}
??總結
感謝你的收看，如果文章有錯誤，可以指出，我不勝感激，讓我們一起學習交流，如果文章可以給你一個小小幫助，可以給博主點一個小小的贊??文章來源：http://www.zghlxwxcb.cn/news/detail-850328.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-850328.html
到了這里，關于【算法與數(shù)據(jù)結構】隊列的實現(xiàn)詳解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
