隊列的基本操作實現
1.隊列的概念
🌟 隊列（Queue）—— 先進先出的數據結構
隊列是一種線性數據結構，遵循 “先進先出”（FIFO, First In First Out） 的原則。如現實中的排隊：先來的人先被服務，後來的人排在隊尾等待。
🔧 基本操作：
- 入隊（Enqueue）：在隊尾添加一個新元素。
- 出隊（Dequeue）：從隊頭移除一個元素。
- 查看隊頭（Front）：獲取隊頭元素，但不移除。
- 判空（IsEmpty）：判斷隊列是否為空。
- 獲取大小（Size）：返回隊列中元素個數。
📦 存儲方式：
隊列可以用兩種主要方式實現：
- 順序存儲：使用數組實現，可優化為循環隊列以避免空間浪費。
- 鏈式存儲：使用鏈表實現，動態分配內存，靈活性高。
2.鏈式存儲--代碼實現
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int DataType_t;
// 鏈表節點結構體（改為 QueueNode）
typedef struct QueueNode {
DataType_t data;
struct QueueNode* next;
} QueueNode;
// 隊列的結構體（改為 LinkedQueue，表示鏈式隊列）
typedef struct {
QueueNode* rear; // 指向隊尾節點
int size;
} LinkedQueue;
// 為 LinkedQueue* 定義別名 Queue，表示一個隊列的指針
typedef LinkedQueue* Queue;
/**
* 初始化隊列
* @param q 指向隊列指針的指針（二級指針），用於返回隊列的地址
* @return 成功返回 1，失敗返回 0
*/
int InitQueue(Queue* q)
{
if (q == NULL) return 0;
// 申請內存存儲管理隊列的結構體
*q = (Queue)malloc(sizeof(LinkedQueue));
if (*q == NULL) return 0;
(*q)->size = 0;
(*q)->rear = NULL;
return 1;
}
/**
* 入隊操作：一個新元素入隊列
* @param q 隊列指針
* @param data 要入隊列的數據
* @return 成功返回 1，失敗返回 0
*/
int EnQueue(Queue q, DataType_t data)
{
if (q == NULL) return 0;
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL) return 0;
newNode->data = data;
// 如果隊列空
if (q->rear == NULL) {
newNode->next = newNode;
q->rear = newNode;
} else {//新節點放到尾節點之後，再更新rear指向
newNode->next = q->rear->next;
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
return 1;
}
// 判斷隊列是否空
bool IsEmpty(Queue q) {
return q == NULL || q->rear == NULL;
}
// 計算隊列元素個數
int GetSize(Queue q) {
if (q == NULL) return -1;
return q->size;
}
/**
* 出隊操作：
* @param q 隊列指針
* @param data 存儲出隊元素的值
* @return 成功返回 1，失敗返回 0
*/
int DeQueue(Queue q, DataType_t* data) {
if (q == NULL || q->rear == NULL) {
return 0; // 空隊列或無效隊列
}
QueueNode* frontNode = q->rear->next; // 隊頭是 rear->next
*data = frontNode->data;
if (q->rear == frontNode) {
// 只有一個節點
free(frontNode);
q->rear = NULL;
} else {
// 多個節點
q->rear->next = frontNode->next; // 跳過隊頭
free(frontNode);
}
q->size--;
return 1;
}
void DestroyQueue(Queue* q) {
if (q == NULL || *q == NULL) return;
if ((*q)->rear != NULL) {
QueueNode* current = (*q)->rear->next; // 隊頭
QueueNode* head = current;
QueueNode* temp;
do {
temp = current;
current = current->next;
free(temp);
} while (current != head);
}
free(*q);
*q = NULL;
}
void PrintQueue(Queue q) {
if (IsEmpty(q)) {
printf("Queue is empty.\n");
return;
}
QueueNode* current = q->rear->next; // 從隊頭開始
printf("Queue (front -> rear): ");
do {
printf("%d ", current->data);
current = current->next;
} while (current != q->rear->next);
printf("\n");
}
int main() {
Queue myQueue;
if (!InitQueue(&myQueue)) {
printf("Failed to initialize queue.\n");
return -1;
}
printf("EnQueue: 10, 20, 30\n");
EnQueue(myQueue, 10);
EnQueue(myQueue, 20);
EnQueue(myQueue, 30);
PrintQueue(myQueue);
printf("Size: %d\n", GetSize(myQueue));
DataType_t val;
printf("DeQueue: ");
while (DeQueue(myQueue, &val)) {
printf("%d ", val);
if (IsEmpty(myQueue)) break;
}
printf("\n");
printf("After dequeue all: empty? %s\n", IsEmpty(myQueue) ? "yes" : "no");
DestroyQueue(&myQueue);
return 0;
}
運行結果
順序存儲--（循環隊列）代碼實現
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 定義隊列中元素的數據類型為 int
typedef int DataType_t;
// 循環隊列結構體定義
typedef struct CircularQueue
{
DataType_t *Addr; // 指向動態分配的數組，用於存儲數據
int Rear; // 隊尾索引（指向下一個插入位置）
int Front; // 隊頭索引（指向當前第一個元素）
unsigned int Size; // 隊列總容量（數組大小）
}CircQueue_t;
/**
* 初始化循環隊列
* @param size 隊列的最大容量
* @return 成功返回隊列指針，失敗則退出程序
*/
CircQueue_t* CircQueue_init(unsigned int size)
{
CircQueue_t *Manager = (CircQueue_t*)calloc(1,sizeof(CircQueue_t));
if(Manager == NULL){
perror("calloc for Manager is failed!\n");
exit(-1);
}
// 為數據數組分配內存
Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
if(Manager->Addr == NULL){
perror("calloc for Eelement is failed\n");
free(Manager);
exit(-1);
}
Manager->Size = size; // 設置容量
Manager->Rear = 0; // 初始隊尾為0
Manager->Front = 0; // 初始隊頭為0
return Manager; // 返回初始化後的隊列
}
/**
* 判斷隊列是否已滿
* @param Manager 隊列指針
* @return 滿則返回 true，否則返回 false
*/
bool CircQueueIsfull(CircQueue_t *Manager)
{
// 當 (Rear+1) % Size == Front 時，隊滿（犧牲一個空間，用空間換時間）
return ((Manager->Rear+1)%Manager->Size == Manager->Front)?true:false;
}
/**
* 判斷隊列是否為空
* @param Manager 隊列指針
* @return 空則返回 true，否則返回 false
*/
bool CircQueueIsEmpty(CircQueue_t *Manager)
{
// Front == Rear 表示隊列為空
return ( Manager->Front == Manager->Rear)?true:false;
}
/**
* 入隊操作
* @param Manager 隊列指針
* @param data 要入隊的數據
* @return 成功返回 true，失敗（隊滿）返回 false
*/
bool CircQueue_Push(CircQueue_t *Manager,DataType_t data)
{
if(CircQueueIsfull(Manager)){
printf("Full!\n");
return false;
}
Manager->Addr[Manager->Rear] = data; // 數據放入隊尾;
Manager->Rear = (Manager->Rear+1)%Manager->Size; // rear 向後移動，循環
return true;
}
/**
* 出隊操作
* @param Manager 隊列指針
* @param data 用於保存出隊的數據（通過指針返回）
* @return 成功返回 true，失敗（隊空）返回 false
*/
bool CircQueue_Pop(CircQueue_t* Manager, DataType_t* data)
{
// 檢查隊列是否為空
if (CircQueueIsEmpty(Manager)) {
printf("Empty!\n");
return false; // 出隊失敗
}
// 取出隊頭元素
*data = Manager->Addr[Manager->Front];
// 移動隊頭指針：向後移動一位，模 Size 實現循環
Manager->Front = (Manager->Front + 1) % Manager->Size;
return true; // 出隊成功
}
int main(int argc, char const *argv[])
{
// 初始化一個大小為 3 的循環隊列
CircQueue_t* q = CircQueue_init(3);
DataType_t val;
// --- 測試入隊 ---
printf("=== 入隊測試 ===\n");
if (CircQueue_Push(q, 10)) {
printf("成功入隊: 10\n");
}
if (CircQueue_Push(q, 20)) {
printf("成功入隊: 20\n");
}
if (CircQueue_Push(q, 30)) {
printf("成功入隊: 30\n");
}
if (CircQueue_Push(q, 40)) {
printf("成功入隊: 40\n");
} else {
printf("入隊 40 失敗：循環隊列隊列已滿！\n");
}
// --- 測試出隊 ---
printf("\n=== 出隊測試 ===\n");
if (CircQueue_Pop(q, &val)) {
printf("成功出隊: %d\n", val);
}
if (CircQueue_Pop(q, &val)) {
printf("成功出隊: %d\n", val);
}
// --- 測試循環入隊 ---
printf("\n=== 測試循環特性 ===\n");
if (CircQueue_Push(q, 40)) {
printf("成功入隊: 40\n");
}
if (CircQueue_Push(q, 50)) {
printf("成功入隊: 50\n");
} else {
printf("入隊 50 失敗：循環隊列隊列已滿！\n");
}
// --- 出隊剩餘元素 ---
printf("\n=== 清空隊列 ===\n");
while (CircQueue_Pop(q, &val)) {
printf("成功出隊: %d\n", val);
}
printf("隊列已空，測試結束。\n");
// --- 釋放資源 ---
free(q->Addr); // 釋放數據數組
free(q); // 釋放隊列結構體
return 0;
}
