柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】數(shù)組循環(huán)隊(duì)列的實(shí)現(xiàn)

http://yzkb.51969.com/

隊(duì)列（Queue）是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循FIFO（First In First Out，先入先出）的原則。隊(duì)列只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。

隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除，所以又稱為先進(jìn)先出（FIFO—first in first out）線性表，簡(jiǎn)稱隊(duì)列。

在程序中，隊(duì)列常常被用來(lái)處理需要按一定順序處理的任務(wù)，例如打印任務(wù)隊(duì)列、線程任務(wù)調(diào)度等。此外，隊(duì)列也在許多算法中發(fā)揮著重要作用，如廣度優(yōu)先搜索（BFS）等。

隊(duì)列的實(shí)現(xiàn)方式有多種，包括基于數(shù)組的靜態(tài)隊(duì)列、基于鏈表的動(dòng)態(tài)隊(duì)列等。在實(shí)際應(yīng)用中，可以根據(jù)具體需求選擇合適的隊(duì)列實(shí)現(xiàn)方式。

隊(duì)列的主要特點(diǎn)包括：

先進(jìn)先出：隊(duì)列中的元素按照進(jìn)入隊(duì)列的先后順序依次出隊(duì)。 操作受限：隊(duì)列只允許在隊(duì)尾插入元素（入隊(duì)），在隊(duì)頭刪除元素（出隊(duì)），其他位置的元素?zé)o法直接訪問或修改。 有序性：由于遵循FIFO原則，隊(duì)列中的元素始終保持一定的順序。

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為：

typedef int QDataType;

// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列

typedef struct QListNode

{

struct QListNode* next;

QDataType data;

}QNode;

// 隊(duì)列的結(jié)構(gòu)

typedef struct Queue

{

QNode* front;

QNode* rear;

int size;

}Queue;

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)為：

#define MAXQSIZE 100 //隊(duì)列可能達(dá)到的最大長(zhǎng)度

typedef struct

{

QElemType* base; //存儲(chǔ)空間的基地址

int front; //頭指針

int rear; //尾指針

}SqQueue;

假設(shè)當(dāng)前隊(duì)列分配的空間最大為6，則當(dāng)隊(duì)列處于上圖的最后一個(gè)狀態(tài)時(shí)，就不可以在繼續(xù)插入新的隊(duì)尾元素，否則會(huì)出現(xiàn)溢出的情況，即因數(shù)組越界而導(dǎo)致程序的非法操作錯(cuò)誤。但是隊(duì)列的實(shí)際空間并未占滿，這種現(xiàn)象就被稱為假溢出。 那么怎么解決這個(gè)問題呢？ 我們就可以運(yùn)用一個(gè)較為巧妙的方法：循環(huán)隊(duì)列 但這里我們面臨一個(gè)問題，就是front==rear的時(shí)候時(shí)隊(duì)空還是隊(duì)滿 可以發(fā)現(xiàn)并不好來(lái)判斷 下面我們就有兩種方法來(lái)解決下列問題

多開辟用一個(gè)空間（即少用一個(gè)元素空間），假設(shè)隊(duì)列的空間為k+1，但當(dāng)有m個(gè)元素的時(shí)候就認(rèn)為時(shí)隊(duì)滿即(Q.rear + 1)%(k+1) == Q.front即為隊(duì)滿，Q.rear == Q.front時(shí)為隊(duì)空用一個(gè)標(biāo)志位來(lái)Size判斷隊(duì)列是空還是隊(duì)滿即當(dāng)Size == k時(shí)為隊(duì)滿，Size == 0時(shí)為隊(duì)空–

下面我們就用一種方法來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列

結(jié)構(gòu)體定義：

typedef int QDataType;

typedef struct {

QDataType* a;

int front;//指向頭

int rear;//指向尾的下一位

int k;//隊(duì)列的長(zhǎng)度

} MyCircularQueue;

創(chuàng)建隊(duì)列

MyCircularQueue* myCircularQueueCreate(int k) {

MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

//開辟一個(gè)大小為（k+1）的數(shù)組空間，多開一個(gè)空間以便判斷隊(duì)列為空還是滿的

//防止假溢出現(xiàn)象

obj->a = (QDataType*)malloc((k + 1) * sizeof(QDataType));

obj->k = k;

obj->front = obj->rear = 0;

return obj;

}

判斷隊(duì)空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

return obj->rear == obj->front;

}

判斷隊(duì)滿

bool myCircularQueueIsFull(MyCircularQueue* obj) {

return (obj->rear + 1) % (obj->k + 1) == obj->front;

}

入隊(duì)

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

if (myCircularQueueIsFull(obj))

{

return false;

}

obj->a[obj->rear] = value;

obj->rear++;

obj->rear %= obj->k + 1;

return true;

}

出隊(duì)

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

{

return false;

}

obj->front++;

obj->front %= obj->k + 1;

return true;

}

取出隊(duì)頭元素

int myCircularQueueFront(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

return -1;

else

return obj->a[obj->front];

}

取出隊(duì)尾元素

int myCircularQueueRear(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

return -1;

else

return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];

}

銷毀隊(duì)列

void myCircularQueueFree(MyCircularQueue* obj) {

free(obj->a);

free(obj);

}

柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】數(shù)組循環(huán)隊(duì)列的實(shí)現(xiàn)

http://yzkb.51969.com/

文章鏈接