用c語言實現——順序隊列支持用戶輸入交互、入隊、出隊、查找、遍歷、計算隊列長度等功能。確定判斷判滿的方法為：犧牲一個存儲單元方式

一、知識介紹

1.基本原理

在順序隊列中，我們使用一個固定大小的數組來存儲隊列中的元素，并使用兩個指針（front 和 rear）來分別表示隊頭和隊尾的位置。

隊列為空的條件：front == rear
隊列滿的條件：rear + 1 ≡ front (mod MAX_SIZE)

為了區分“隊列滿”和“隊列空”的情況，我們犧牲一個存儲單元，即當隊尾指針的下一個位置（循環計算）等于隊頭指針時，認為隊列已滿，而不是等到隊列完全填滿。?

2.實現方法?

a.數據結構

b.判空和判滿

判空：front == rear
判滿：(rear + 1) % MAX_SIZE == fron

c.入隊操作

當隊列未滿時，將元素添加到隊尾，并更新隊尾指針：

d.出隊操作

當隊列非空時，移除隊頭元素，并更新隊頭指針：

二、關鍵點解析

1.判斷隊列是否已滿邏輯解析

?核心邏輯：

隊列滿的條件是：隊尾指針的下一個位置（循環計算）等于隊頭指針。換句話說，當 (rear + 1) % MAX_SIZE == front 時，隊列已滿。

為什么這樣判斷？

循環隊列的特性：隊列使用一個固定大小的數組來存儲元素，并通過 front 和 rear 指針來管理元素的插入和刪除。
犧牲一個存儲單元：為了區分“隊列滿”和“隊列空”的情況，我們犧牲一個存儲單元。
當 rear + 1 等于 front 時，認為隊列已滿，而不是等到隊列完全填滿。

假設 MAX_SIZE = 5，隊列的數組大小為 5。
情況 1：隊列滿：
front = 0
rear = 4
(4 + 1) % 5 = 0，等于 front，所以隊列滿。
情況 2：隊列未滿
front = 0
rear = 3
(3 + 1) % 5 = 4，不等于 front，所以隊列未滿。

2. 入隊邏輯

a. 判斷隊列是否已滿

調用 IsFull 函數判斷隊列是否已滿。

如果隊列已滿，打印提示信息并返回 false，表示入隊失敗。

b.入隊操作

?將元素 value 存入隊列的尾部位置（q->rear）。

c.更新隊尾指針

隊尾指針 rear 加 1，并對數組大小 MAX_SIZE 取模，是為了確保指針在數組范圍內循環。

d.?返回成功?

3.出隊邏輯

a.函數定義

返回值類型：bool，表示出隊操作是否成功。

參數：

SeqQueue *q：指向隊列的指針。

int *value：指向一個整型變量的指針，用于存儲出隊的元素值。

b.判斷隊列是否為空

調用 IsEmpty 函數判斷隊列是否為空。

如果隊列為空，打印提示信息并返回 false，表示出隊失敗。

c.獲取隊頭元素

將隊列中隊頭位置（q->front）的元素值賦給傳入的指針變量 *value。

q->data 是存儲隊列元素的數組。
q->front 是隊頭指針，指向當前隊列的第一個元素的位置。
q->data[q->front] 通過數組索引訪問隊頭元素。
*value 是一個指針解引用操作，將隊頭元素的值存儲到傳入的變量中。

d.更新隊頭指針

隊頭指針 front 加 1，并對數組大小 MAX_SIZE 取模，確保指針在數組范圍內循環。

4.查找元素

a.檢查隊列是否為空

調用 IsEmpty 函數判斷隊列是否為空。

如果隊列為空，打印提示信息并返回 -1，表示無法查找。

b.?初始化變量

index：初始化為隊頭指針 front，用于遍歷隊列。

count：初始化為0，用于記錄當前遍歷到的位置。

c.?遍歷隊列

循環條件：index != q->rear，表示隊列中還有元素未遍歷。

查找邏輯：

? ? ? ?如果當前索引位置的元素等于要查找的值，返回 count，從0開始表示找到了元素。

? ? ? ?如果未找到，更新 index 指針為下一個位置，并對數組大小 MAX_SIZE 取模，確保指針在數組范圍內循環。

? ?count 加1，記錄當前遍歷到的位置。

d.未找到元素

如果循環結束仍未找到元素，返回 -1。

5.遍歷邏輯

a.檢查隊列是否為空

調用 IsEmpty 函數判斷隊列是否為空。

如果隊列為空，打印提示信息并返回，表示無法遍歷。

b.打印隊列元素并遍歷

打印提示信息，表示接下來將輸出隊列中的元素。

初始化索引：index 初始化為隊頭指針 front，用于遍歷隊列。

循環條件：index != q->rear，表示隊列中還有元素未遍歷。

打印元素：通過 q->data[index] 訪問當前索引位置的元素并打印。

更新索引：index = (index + 1) % MAX_SIZE，更新索引為下一個位置，并對數組大小 MAX_SIZE 取模，確保指針在數組范圍內循環。

打印換行符，使輸出更整潔。

6.計算長度邏輯

a.為什么可以這樣計算？

1.?直接計算?`rear - front`

在非循環隊列中，隊列的長度可以直接通過 rear - front 計算。例如：

如果 front = 0，rear = 3，隊列長度為 3 - 0 = 3。
如果 front = 1，rear = 4，隊列長度為 4 - 1 = 3。

2.?循環隊列的特殊情況

在循環隊列中，rear 可能小于 front，因為隊列是循環的。例如：

如果 front = 3，rear = 0，直接計算 rear - front 會得到負數 -3，這顯然不符合實際隊列長度。

3.?解決負數問題

為了避免負數，公式中加上了 MAX_SIZE

這樣可以確保結果始終是正數。例如：

如果 front = 3，rear = 0，MAX_SIZE = 5：
- 0 - 3 + 5 = 2，表示隊列中有 2 個元素。

4.?取模操作

這一步確保即使 rear 和 front 的差值超過 MAX_SIZE，結果仍然正確

假設 MAX_SIZE = 5：

情況 1：`rear`?大于?`front`

front = 0
rear = 3
計算：(3 - 0 + 5) % 5 = 8 % 5 = 3，隊列長度為 3。

情況 2：`rear`?小于?`front`

front = 3
rear = 0
計算：(0 - 3 + 5) % 5 = 2 % 5 = 2，隊列長度為 2。

情況 3：隊列為空

front = 0
rear = 0
計算：(0 - 0 + 5) % 5 = 5 % 5 = 0，隊列長度為 0。

三、完整代碼

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>#define MAX_SIZE 10                              // 隊列的最大容量                      // 定義隊列結構
typedef struct
{int data[MAX_SIZE];                          // 存儲隊列元素的數組             int front;                                   // 隊頭指針int rear;                                    // 隊尾指針
}SeqQueue;// 初始化隊列
void InitQueue(SeqQueue* q)
{q->front = 0;q->rear = 0;
}// 判斷隊列是否已滿
bool isFull(SeqQueue* q)
{return ((q->rear + 1) % MAX_SIZE) == q->front;
}// 判斷隊列是否為空
bool isEmpty(SeqQueue* q)
{return	q->front == q->rear;
}// 入隊操作
bool Enqueue(SeqQueue* q, int value)
{if (isFull(q)){printf("隊列已滿，無法入隊！\n");return false;}q->data[q->rear] = value;q->rear = (q->rear + 1) % MAX_SIZE;return true;
}// 出隊操作
bool Dequeue(SeqQueue* q, int* value)
{if (isEmpty(q)){printf("隊列為空，無法出隊！\n");return false;}*value = q->data[q->front];q->front = (q->front + 1) % MAX_SIZE;return true;
}// 查找元素
int FindElement(SeqQueue* q, int value)
{if (isEmpty(q)){printf("隊列為空，無法查找！\n");return -1;}int index = q->front;int count = 1;while (index != q->rear){if (q->data[index] == value){return count;                         // 返回元素在隊列中的位置（從0開始）}index = (index + 1) % MAX_SIZE;count++;}return -1;
}// 遍歷隊列
void TraverseQueue(SeqQueue* q)
{if (isEmpty(q)){printf("隊列為空，無法遍歷！\n");return;}printf("隊列元素:");int index = q->front;while (index != q->rear){printf("%d ", q->data[index]);index = (index + 1) % MAX_SIZE;}printf("\n");
}// 計算隊列長度
int QueueLength(SeqQueue* q)
{return ((q->rear) - (q->front) + MAX_SIZE) % MAX_SIZE;
}void Menu()
{printf("\n===== 順序隊列操作菜單 =====\n");printf("1. 入隊\n");printf("2. 出隊\n");printf("3. 查找元素\n");printf("4. 遍歷隊列\n");printf("5. 計算隊列長度\n");printf("0. 退出程序\n");printf("請輸入您的選擇：");
}int main()
{SeqQueue queue;InitQueue(&queue);int choice = 0;int value = 0;int pos = 0;while (1){Menu();scanf_s("%d", &choice);switch (choice){case 1:printf("請輸入要入隊的元素:>");scanf_s("%d", &value);if (Enqueue(&queue, value)){printf("入隊成功！當前隊列長度:>%d\n", QueueLength(&queue));}break;case 2:if (Dequeue(&queue, &value)){printf("出隊元素:%d，當前隊列長度:%d\n", value, QueueLength(&queue));}break;case 3:printf("請輸入要查找的元素:");scanf_s("%d", &value);pos = FindElement(&queue, value);if (pos != -1){printf("元素 %d 在隊列中的位置為:%d\n", value, pos);}else{printf("隊列中不存在元素 %d\n", value);}break;case 4:TraverseQueue(&queue);break;case 5:printf("當前隊列長度:%d\n", QueueLength(&queue));break;case 0:printf("程序結束！\n");exit(0);break;default:printf("無效的選擇，請重新輸入！\n");}}return 0;
}

?以上是基于VS2022編譯器，用c語言實現——順序隊列。判斷隊列已滿或者空的情況是通過犧牲一個存儲單元的方法來實現的。支持用戶輸入交互、入隊、出隊、查找、遍歷等功能。