- (??? )，Hello我是祐言QAQ
- 我的博客主頁：C/C++語言,Linux基礎(chǔ),ARM開發(fā)板，軟件配置等領(lǐng)域博主??
- 快上??，一起學(xué)習(xí)，讓我們成為一個強(qiáng)大的攻城獅！
- 送給自己和讀者的一句雞湯??：集中起來的意志可以擊穿頑石!
- 作者水平很有限，如果發(fā)現(xiàn)錯誤，可在評論區(qū)指正，感謝??
????????在我們的日常生活中，隊(duì)列是一個非常常見的現(xiàn)象。無論是在商店結(jié)賬，還是在公交站等車，我們都在使用隊(duì)列。在計(jì)算機(jī)科學(xué)中，隊(duì)列也是一個重要的數(shù)據(jù)結(jié)構(gòu)，用于處理和組織數(shù)據(jù)。在這篇文章中，我們將詳細(xì)探討隊(duì)列的定義、操作、以及如何用C語言實(shí)現(xiàn)隊(duì)列。
一、隊(duì)列的定義
????????隊(duì)列（Queue）是一種特殊類型的線性數(shù)據(jù)結(jié)構(gòu)，它遵循特定的操作規(guī)則，即遵循“先進(jìn)先出”（FIFO，F(xiàn)irst-In-First-Out）原則。這意味著在隊(duì)列中，首先加入的元素將會首先被移除，最后加入的元素將會最后被移除。
? ? ? ? ?當(dāng)我們想存入1時，先移動front（隊(duì)頭）然后再寫入數(shù)據(jù)1，拿數(shù)據(jù)也是一樣，但務(wù)必保證先移動rear（隊(duì)尾），再拿出數(shù)據(jù)，否則將會錯位導(dǎo)致出錯。
二、順序隊(duì)列
? ? ? 1.? 隊(duì)列結(jié)構(gòu)體定義
????????首先需要定義一個順序隊(duì)列，我們可以使用結(jié)構(gòu)體來定義一個隊(duì)列，它包含一個數(shù)組（用于存儲隊(duì)列的數(shù)據(jù)）和三個整數(shù)（用于表示隊(duì)列長度、隊(duì)首和隊(duì)尾的位置）。
typedef int Datatype;
//隊(duì)列的結(jié)構(gòu)體定義
typedef struct Quene
{
Datatype *q; //用來存放隊(duì)列的數(shù)據(jù)
int size; //隊(duì)列的長度
int front; //隊(duì)頭
int rear; //隊(duì)尾
}queue;????2.? 初始化隊(duì)列
????????接下來，我們需要初始化隊(duì)列。在初始化時，我們將隊(duì)首和隊(duì)尾都設(shè)置為0，表示隊(duì)列為空。
//初始化一個隊(duì)列
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.? 隊(duì)空和隊(duì)滿
? ? ? ? 如果我們想要實(shí)現(xiàn)入隊(duì)和出隊(duì)操作，我們需要先考慮隊(duì)列可能會溢出或下溢的情況，因此我們需要判斷是否隊(duì)空或隊(duì)滿。
//隊(duì)空判斷
bool isempty_queue(queue *q)
{
return (q->rear == q->front);
}
//隊(duì)滿判斷
bool isfull_queue(queue *q)
{
return ((q->rear+1)%q->size == q->front);
}????4.? 入隊(duì)和出隊(duì)
//入隊(duì)
bool en_queue(queue *que, Datatype data)
{
if (isfull_queue(que))
{
return false;
}
//先挪rear
que->rear = (que->rear+1)%(que->size);
//再入數(shù)據(jù)
que->q[que->rear] = data;
return true;
}
//出隊(duì)
bool de_queue(queue *que, Datatype *data)
{
if (isempty_queue(que))
{
return false;
}
//先挪front
que->front = (que->front+1)%(que->size);
//再取數(shù)據(jù)
*data = que->q[que->front];
return true;
}
????????隊(duì)列是計(jì)算機(jī)科學(xué)中的一個基礎(chǔ)概念，它在許多場景中都有應(yīng)用，如操作系統(tǒng)的任務(wù)調(diào)度，網(wǎng)絡(luò)的數(shù)據(jù)包處理等。理解隊(duì)列的工作原理并能夠?qū)崿F(xiàn)隊(duì)列，對于學(xué)習(xí)和理解計(jì)算機(jī)科學(xué)的其他概念是非常有幫助的。希望這篇文章能幫助你理解和實(shí)現(xiàn)隊(duì)列。
? ? ? ? 下面是一個簡單的順序隊(duì)列舉例，實(shí)現(xiàn)：輸入正整數(shù)，添加員工信息，入隊(duì)，用這個正整數(shù)表示員工號；輸入負(fù)整數(shù)，出隊(duì)（隊(duì)首），顯示該員工的所有信息；否則就退出。
????????員工信息：工號、姓名、工資
? ? ? ? 完整源碼：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 1024
typedef struct people
{
int number; //工號
char name[20]; //姓名
int money; //工資
}Datatype;
//隊(duì)列的結(jié)構(gòu)體定義
typedef struct Quene
{
Datatype *q; //用來存放隊(duì)列的數(shù)據(jù)
int size; //隊(duì)列的長度
int front; //隊(duì)頭
int rear; //隊(duì)尾
}queue;
//初始化一個隊(duì)列
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;
}
//隊(duì)空判斷
bool isempty_queue(queue *q)
{
return (q->rear == q->front);
}
//隊(duì)滿判斷
bool isfull_queue(queue *q)
{
return ((q->rear+1)%q->size == q->front);
}
//入隊(duì)
bool en_queue(queue *que, Datatype data)
{
if (isfull_queue(que))
{
return false;
}
//先挪rear
que->rear = (que->rear+1)%(que->size);
//再入數(shù)據(jù)
que->q[que->rear] = data;
return true;
}
//出隊(duì)
bool de_queue(queue *que, Datatype *data)
{
if (isempty_queue(que))
{
return false;
}
//先挪front
que->front = (que->front+1)%(que->size);
//再取數(shù)據(jù)
*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("請輸入一個正整數(shù)或負(fù)數(shù)\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("隊(duì)列已空，無法出隊(duì)。\n");
}
}
else{
return -1;
}
}
free(q->q);
free(q);
return 0;
}三、鏈?zhǔn)疥?duì)列
????????鏈?zhǔn)疥?duì)列（Linked Queue）是一種使用鏈表來實(shí)現(xiàn)的隊(duì)列數(shù)據(jù)結(jié)構(gòu)。與順序隊(duì)列不同，鏈?zhǔn)疥?duì)列的元素并不直接存儲在數(shù)組中，而是通過鏈表節(jié)點(diǎn)來連接。
????????并且 由于使用鏈表實(shí)現(xiàn)，鏈?zhǔn)疥?duì)列的大小可以根據(jù)需要動態(tài)分配和釋放內(nèi)存，避免了固定數(shù)組大小可能帶來的限制。因此就沒有是否隊(duì)滿問題。
1.結(jié)構(gòu)體定義
typedef int Datatype;
typedef struct Node
{
Datatype data;
struct Node *next;
}node;
typedef struct List_queue
{
node *rear; //隊(duì)尾指針
node *front; //隊(duì)頭指針
int size; //鏈?zhǔn)疥?duì)列的長度(實(shí)際的元素的個數(shù))
}L_q;
2.創(chuàng)建新節(jié)點(diǎn)和判斷隊(duì)空
//創(chuàng)建新節(jié)點(diǎn)
node *create_node(Datatype data)
{
node *new = malloc(sizeof(node));
if (new != NULL)
{
new->data = data;
new->next = NULL;
}
return new;
}
//鏈?zhǔn)疥?duì)列是否為空
bool isempty_list_queue(L_q *q)
{
return (q->size == 0);
}3.初始化隊(duì)列
//初始化鏈?zhǔn)疥?duì)列
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.入隊(duì)
????????入隊(duì)操作在鏈表的末尾添加一個新節(jié)點(diǎn)，同時更新隊(duì)尾指針。
//入隊(duì)
bool en_list_queue(L_q *q, Datatype data)
{
//先要將數(shù)據(jù)創(chuàng)建新節(jié)點(diǎn)
node *new = create_node(data);
if (new==NULL)
{
return false;
}
//如果是第一次入隊(duì)，new節(jié)點(diǎn)既是隊(duì)尾，也是隊(duì)頭
if (isempty_list_queue(q))
{
q->rear = new;
q->front = new;
}
else //不是第一次入隊(duì)
{
//先將尾部節(jié)點(diǎn)的next指向new節(jié)點(diǎn)
q->rear->next = new;
//尾部節(jié)點(diǎn)要變成新節(jié)點(diǎn)new
q->rear = new;
}
//隊(duì)的元素個數(shù)要+1
q->size++;
return true;
}4.出隊(duì)
?????????出隊(duì)操作移除鏈表的第一個節(jié)點(diǎn)，同時更新隊(duì)頭指針。
//出隊(duì)
bool de_list_queue(L_q *q, Datatype *data)
{
if (isempty_list_queue(q))
{
return false;
}
else if(q->size == 1)//只有一個數(shù)據(jù)的時候
{
q->rear = NULL;
}
//在鏈表不為空的情況下,先拿隊(duì)頭的數(shù)據(jù)
*data = q->front->data;
//將隊(duì)頭指向下一個節(jié)點(diǎn)
q->front = q->front->next;
//鏈?zhǔn)疥?duì)列的元素個數(shù)-1
q->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);
}????????簡單示例：當(dāng)我們輸入正數(shù)時，入隊(duì)并遍歷整個隊(duì)列；當(dāng)我們輸入負(fù)數(shù)時，出隊(duì)一個元素，并再次遍歷隊(duì)列；輸入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;
}四、結(jié)語
????????
????????隊(duì)列作為一種基本的數(shù)據(jù)結(jié)構(gòu)，在我們的編程生涯中扮演著重要的角色。希望這篇文章提供了一個清晰、詳細(xì)的隊(duì)列概述，幫助你理解隊(duì)列的基本概念和操作，以及如何用C語言實(shí)現(xiàn)隊(duì)列。
????????選擇順序隊(duì)列還是鏈?zhǔn)疥?duì)列取決于實(shí)際應(yīng)用的需求。如果你需要一個固定大小的隊(duì)列，可以考慮使用順序隊(duì)列。如果你希望隊(duì)列大小能夠根據(jù)需要進(jìn)行動態(tài)調(diào)整，那么鏈?zhǔn)疥?duì)列更適合。在大多數(shù)情況下，鏈?zhǔn)疥?duì)列具有更好的擴(kuò)展性和靈活性。
????????更多C語言、Linux系統(tǒng)、ARM板實(shí)戰(zhàn)和數(shù)據(jù)結(jié)構(gòu)相關(guān)文章，關(guān)注專欄：
? ?手撕C語言
? ? ? ? ? ? 玩轉(zhuǎn)linux
????????????????????腳踢數(shù)據(jù)結(jié)構(gòu)文章來源：http://www.zghlxwxcb.cn/news/detail-651478.html
?? ? ? ? ? ? ? ? ?? ? ? ? ? 6818（ARM）開發(fā)板實(shí)戰(zhàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-651478.html
??寫在最后
- 今天的分享就到這啦~
- 覺得博主寫的還不錯的煩勞?
一鍵三連喔~ - ??感謝關(guān)注??
到了這里，關(guān)于【腳踢數(shù)據(jù)結(jié)構(gòu)】隊(duì)列（順序和鏈?zhǔn)剑┑奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
