快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)不掛科指南之隊(duì)列詳解

更新時(shí)間：2022年09月29日 17:11:59 作者：夢(mèng)想橡皮擦

這篇博客主要介紹一下隊(duì)列的概念，并且采用 C 語言，編寫兩種存儲(chǔ)實(shí)現(xiàn)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，當(dāng)然還有常規(guī)的隊(duì)列基本操作的實(shí)現(xiàn)算法

隊(duì)列

這篇博客主要介紹一下隊(duì)列的概念，并且采用 C 語言，編寫兩種存儲(chǔ)實(shí)現(xiàn)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，當(dāng)然還有常規(guī)的隊(duì)列基本操作的實(shí)現(xiàn)算法

隊(duì)列基本概念

標(biāo)準(zhǔn)解釋：隊(duì)列（Queue）是有限個(gè)**同類型數(shù)據(jù)元素的線性序列，是一種先進(jìn)先出**（First In First Out FIFO）的線性表，新鍵入的數(shù)據(jù)元素插在隊(duì)列尾端，出隊(duì)列的數(shù)據(jù)元素在隊(duì)列首部被刪除。

教材中給了一個(gè)示意圖，不錯(cuò)

順序隊(duì)列結(jié)構(gòu)類型中有三個(gè)域：data、front、rear。

data:一維數(shù)組，存儲(chǔ)隊(duì)列中的數(shù)據(jù)元素 font：指向隊(duì)列首元素的前一個(gè)單元 rear：指向?qū)嶋H的隊(duì)列尾元素單元

參考示意圖

入隊(duì)列操作可以用兩條賦值語句

SQ.rear = SQ.rear+1;
SQ.data[SQ.rear] = x;

出隊(duì)列操作可以用一條語句完成

SQ.front = SQ.front+1

但是，會(huì)出現(xiàn)一些問題，通過示意圖說明一下

當(dāng)然還有一種情況，一邊入隊(duì)列，一邊出隊(duì)列注意下圖，SQ.front 下面還有空間

所以為了解決這種假溢出問題，聰明的開發(fā)人員，想出來新的解決辦法了，造一個(gè)環(huán)兒~

循環(huán)隊(duì)列

下面看一個(gè)圖，重點(diǎn)看一下 SQ.rear 與 SQ.front 的對(duì)應(yīng)位置

如果上述圖翻譯成 C 語言代碼，入隊(duì)核心邏輯為

SQ.rear = (SQ.rear+1) % maxsize ;
SQ.data[SQ.rear] = x;

出隊(duì)列的核心邏輯為

SQ.front = (SQ.front+1)%maxsize;

你在學(xué)習(xí)的時(shí)候，肯定對(duì)SQ.rear+1和SQ.front+1有疑問

我們舉例來說明一下吧

順序隊(duì)列的 C 語言實(shí)現(xiàn)

接下來難度指數(shù)上升，開始用 C 語言編寫代碼吧

一頓操作之后，還是比較簡單的，總之不寫鏈?zhǔn)酱鎯?chǔ)，順序的還是比較簡單的

#include <stdio.h>
#include <stdlib.h>

//循環(huán)隊(duì)列最大數(shù)據(jù)元素個(gè)數(shù)
const int maxsize = 8;

//循環(huán)隊(duì)列的結(jié)構(gòu)體
typedef struct cycqueue{
    int *data;
    int front,rear;
} CycQue;


//隊(duì)列初始化
void init(CycQue *CQ){
    CQ->data = (int *)malloc(maxsize*sizeof(int));
    CQ->front = 0;
    CQ->rear = 0;
}


//判斷隊(duì)列是否為空
int empty(CycQue *CQ){
    if(CQ->rear==CQ->front) return 1;
    else return 0;
}


//入隊(duì)列
int EnQueue(CycQue *CQ,int x){
    if((CQ->rear+1)%maxsize==CQ->front){
        printf("隊(duì)列滿");
        return 0;
    }
    else{
        CQ->rear =(CQ->rear+1) % maxsize;
        CQ->data[CQ->rear] = x;
        return 1;
    }

}

//出隊(duì)列
int OutQueue(CycQue *CQ){
    if(empty(CQ)){
        printf("隊(duì)列為空");
        return 0;
    }
    else{
        CQ->front = (CQ->front+1) % maxsize;
        return 1;

    }

}

int main()
{
    CycQue CQ;
    init(&CQ);

    EnQueue(&CQ,2);
    EnQueue(&CQ,4);
    printf("%d",CQ.rear);
    OutQueue(&CQ);
    printf("%d",CQ.front);
    return 0;
}

鏈?zhǔn)疥?duì)列的 C 語言實(shí)現(xiàn)

鏈?zhǔn)疥?duì)列其實(shí)有之前的經(jīng)驗(yàn)之后，寫起來難度系數(shù)也不會(huì)太高，接下來我們編寫一個(gè)核心的部分代碼

隊(duì)列的鏈接實(shí)現(xiàn)實(shí)際上是用一個(gè)帶有頭結(jié)點(diǎn)的單鏈表來表示隊(duì)列，成為鏈隊(duì)列頭指針指向鏈表的頭結(jié)點(diǎn) 單鏈表的頭結(jié)點(diǎn)的 next 域指向隊(duì)列首結(jié)點(diǎn) 尾指針指向隊(duì)列尾結(jié)點(diǎn)，即單鏈表的最后一個(gè)結(jié)點(diǎn)

初始化

#include <stdio.h>
#include <stdlib.h>
typedef struct LinkQueueNode{
	int *data;
	struct LinkQueueNode *next;
} LkQueNode;

typedef struct LkQueue{
    LkQueNode *front,*rear;
} LkQue;


void init(LkQue *LQ){
    LkQueNode *temp;
    temp = (LkQueNode *)malloc(sizeof(LkQueNode)); //生成隊(duì)列的頭結(jié)點(diǎn)
    LQ->front = temp;    //隊(duì)列頭指針指向隊(duì)列頭結(jié)點(diǎn)
    LQ->rear = temp;     //隊(duì)列尾指針指向隊(duì)列尾結(jié)點(diǎn)
    (LQ->front)->next = NULL;

}

核心兩個(gè)操作入隊(duì)列和出隊(duì)列

入隊(duì)列代碼如下

//入隊(duì)列
void EnQueue(LkQue *LQ,int x){

    LkQueNode *temp;
    temp = (LkQueNode *)malloc(sizeof(LkQueNode));
    temp->data = x;
    temp-next = NULL;
    (LQ->rear)->next = temp;
    LQ->rear = temp;
}

出隊(duì)列這個(gè)事情就交給你自己吧，好好理解一下，就可以寫出來了