(??? )，Hello我是祐言QAQ
我的博客主頁：C/C++語言,Linux基礎,ARM開發板，軟件配置等領域博主🌍
快上🚘，一起學習，讓我們成為一個強大的攻城獅！
送給自己和讀者的一句雞湯🤔：集中起來的意志可以擊穿頑石!
作者水平很有限，如果發現錯誤，可在評論區指正，感謝🙏

????????在我們的日常生活中，隊列是一個非常常見的現象。無論是在商店結賬，還是在公交站等車，我們都在使用隊列。在計算機科學中，隊列也是一個重要的數據結構，用于處理和組織數據。在這篇文章中，我們將詳細探討隊列的定義、操作、以及如何用C語言實現隊列。

一、隊列的定義

????????隊列（Queue）是一種特殊類型的線性數據結構，它遵循特定的操作規則，即遵循“先進先出”（FIFO，First-In-First-Out）原則。這意味著在隊列中，首先加入的元素將會首先被移除，最后加入的元素將會最后被移除。

? ? ? ? ?當我們想存入1時，先移動front（隊頭）然后再寫入數據1，拿數據也是一樣，但務必保證先移動rear（隊尾），再拿出數據，否則將會錯位導致出錯。

二、順序隊列

? ? ? 1.? 隊列結構體定義

????????首先需要定義一個順序隊列，我們可以使用結構體來定義一個隊列，它包含一個數組（用于存儲隊列的數據）和三個整數（用于表示隊列長度、隊首和隊尾的位置）。


typedef int Datatype;//隊列的結構體定義
typedef struct Quene
{Datatype *q;	//用來存放隊列的數據int size;		//隊列的長度int front;		//隊頭int rear;		//隊尾
}queue;

????2.? 初始化隊列

????????接下來，我們需要初始化隊列。在初始化時，我們將隊首和隊尾都設置為0，表示隊列為空。

//初始化一個隊列
queue *init_queue(int size)
{queue *que = malloc(sizeof(queue));if (que!=NULL){que->q = calloc(size, sizeof(Datatype));que->size = size;que->front = 0;que->rear = 0;}return que;
}

????3.? 隊空和隊滿

? ? ? ? 如果我們想要實現入隊和出隊操作，我們需要先考慮隊列可能會溢出或下溢的情況，因此我們需要判斷是否隊空或隊滿。

//隊空判斷
bool isempty_queue(queue *q)
{return (q->rear == q->front);
}//隊滿判斷
bool isfull_queue(queue *q)
{return ((q->rear+1)%q->size == q->front);
}

????4.? 入隊和出隊

//入隊
bool en_queue(queue *que, Datatype data)
{if (isfull_queue(que)){return false;}//先挪rearque->rear = (que->rear+1)%(que->size);//再入數據que->q[que->rear] = data;return true;
}//出隊
bool de_queue(queue *que, Datatype *data)
{if (isempty_queue(que)){return false;}//先挪frontque->front = (que->front+1)%(que->size);//再取數據*data = que->q[que->front];return true;
}

????????隊列是計算機科學中的一個基礎概念，它在許多場景中都有應用，如操作系統的任務調度，網絡的數據包處理等。理解隊列的工作原理并能夠實現隊列，對于學習和理解計算機科學的其他概念是非常有幫助的。希望這篇文章能幫助你理解和實現隊列。

? ? ? ? 下面是一個簡單的順序隊列舉例，實現：輸入正整數，添加員工信息，入隊，用這個正整數表示員工號；輸入負整數，出隊（隊首），顯示該員工的所有信息；否則就退出。

????????員工信息：工號、姓名、工資

? ? ? ? 完整源碼：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define SIZE 1024
typedef struct people
{int number;		//工號char name[20];	//姓名int money;		//工資
}Datatype;//隊列的結構體定義
typedef struct Quene
{Datatype *q;	//用來存放隊列的數據int size;		//隊列的長度int front;		//隊頭int rear;		//隊尾
}queue;//初始化一個隊列
queue *init_queue(int size)
{queue *que = malloc(sizeof(queue));if (que!=NULL){que->q = calloc(size, sizeof(Datatype));que->size = size;que->front = 0;que->rear = 0;}return que;
}//隊空判斷
bool isempty_queue(queue *q)
{return (q->rear == q->front);
}//隊滿判斷
bool isfull_queue(queue *q)
{return ((q->rear+1)%q->size == q->front);
}//入隊
bool en_queue(queue *que, Datatype data)
{if (isfull_queue(que)){return false;}//先挪rearque->rear = (que->rear+1)%(que->size);//再入數據que->q[que->rear] = data;return true;
}//出隊
bool de_queue(queue *que, Datatype *data)
{if (isempty_queue(que)){return false;}//先挪frontque->front = (que->front+1)%(que->size);//再取數據*data = que->q[que->front];return true;
}// 添加信息
void init_info(Datatype *data,int n)
{data->number = n;printf("請輸入工人信息\n");while(getchar() != '\n');printf("姓名：");scanf("%s", data->name);printf("工資：");scanf("%d", &data->money);
}int main(int argc, char const *argv[]) {queue *q = init_queue(SIZE);int n;Datatype data;while (1) {printf("請輸入一個正整數或負數\n");scanf("%d", &n);if (n > 0){init_info(&data, n);en_queue(q, data);continue;}else if(n < 0){Datatype d;if (de_queue(q, &d)) {printf("工號：%d，姓名：%s，工資：%d\n", d.number, d.name, d.money);} else {printf("隊列已空，無法出隊。\n");}}else{return -1;}}free(q->q);free(q);return 0;
}

三、鏈式隊列

????????鏈式隊列（Linked Queue）是一種使用鏈表來實現的隊列數據結構。與順序隊列不同，鏈式隊列的元素并不直接存儲在數組中，而是通過鏈表節點來連接。

????????并且由于使用鏈表實現，鏈式隊列的大小可以根據需要動態分配和釋放內存，避免了固定數組大小可能帶來的限制。因此就沒有是否隊滿問題。

1.結構體定義

typedef int Datatype;typedef struct Node
{Datatype data;struct Node *next;
}node;typedef struct List_queue
{node *rear;		//隊尾指針node *front;	//隊頭指針int size;		//鏈式隊列的長度(實際的元素的個數)
}L_q;

2.創建新節點和判斷隊空

//創建新節點
node *create_node(Datatype data)
{node *new = malloc(sizeof(node));if (new != NULL){new->data = data;new->next = NULL;}return new;
}
//鏈式隊列是否為空
bool isempty_list_queue(L_q *q)
{return (q->size == 0);
}

3.初始化隊列

//初始化鏈式隊列
L_q *init_list_queue()
{L_q *q = malloc(sizeof(L_q));if (q!=NULL){q->rear = NULL;q->front = NULL;q->size = 0;}return q;
}

3.入隊

????????入隊操作在鏈表的末尾添加一個新節點，同時更新隊尾指針。

//入隊
bool en_list_queue(L_q *q, Datatype data)
{//先要將數據創建新節點node *new = create_node(data);if (new==NULL){return false;}//如果是第一次入隊，new節點既是隊尾，也是隊頭if (isempty_list_queue(q)){q->rear = new;q->front = new;}else    //不是第一次入隊{//先將尾部節點的next指向new節點q->rear->next = new;//尾部節點要變成新節點newq->rear = new;}//隊的元素個數要+1q->size++;return true;
}

4.出隊

?????????出隊操作移除鏈表的第一個節點，同時更新隊頭指針。

//出隊
bool de_list_queue(L_q *q, Datatype *data)
{if (isempty_list_queue(q)){return false;}else if(q->size == 1)//只有一個數據的時候{q->rear = NULL;}//在鏈表不為空的情況下,先拿隊頭的數據*data = q->front->data;//將隊頭指向下一個節點q->front = q->front->next;//鏈式隊列的元素個數-1q->size--;return true;
}

?5.遍歷

//遍歷
void display(L_q *q)
{if (q->front == NULL){return ;}node *p = q->front;while(p->next != NULL){printf("%d ", p->data);p = p->next;}printf("%d\n", p->data);
}

????????簡單示例：當我們輸入正數時，入隊并遍歷整個隊列；當我們輸入負數時，出隊一個元素，并再次遍歷隊列；輸入0時退出。

int main(int argc, char const *argv[])
{L_q *q = init_list_queue();int num;Datatype data;while(1){scanf("%d", &num);if(num > 0){en_list_queue(q, num);	display(q);	}else if(num < 0){de_list_queue(q, &data);display(q);	}else{break;}}return 0;
}