C利用語言實現(xiàn)數(shù)據(jù)結(jié)構(gòu)之隊列
前言：
隊列在生活中也比較常見，例如購物排隊——新來的成員總是加入隊尾,每次離開的成員總是隊列頭上的。
隊列按存儲方式可以分為兩種：順序隊列和鏈隊列。
一、鏈隊列
鏈?zhǔn)疥犃兄忻總€元素定義成一個結(jié)點，含數(shù)據(jù)域與指針域（指向下一結(jié)點），并設(shè)頭尾指針。用圖表示就是。
二、鏈隊的表示
前面的鏈?zhǔn)浇Y(jié)構(gòu)，總是使用一個結(jié)點的結(jié)構(gòu)來表示鏈表，但是在這里使用新的存儲結(jié)構(gòu)。定義一個結(jié)點結(jié)構(gòu)，和一個隊列結(jié)構(gòu)。兩個結(jié)構(gòu)嵌套。
//定義節(jié)點結(jié)構(gòu)
typedef struct QNode
{
QElemType data; /*數(shù)據(jù)域*/
struct QNode * next; /*指針域*/
}QNode, *QueuePtr;
//定義隊列結(jié)構(gòu)
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
三、鏈隊的基本操作
1. 鏈隊的初始化
Status initQueue(LinkQueue *Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
2. 鏈隊的銷毀
Status destroyQueue(LinkQueue *Q)
{
while (Q.front)
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
3. 入隊
Status enQueue(LinkQueue *Q, QElemType e)
{
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
//插入數(shù)據(jù)
p->data = e;
p->next = NULL;
//Q.rear一直指向隊尾
Q.rear->next = p;
Q.rear = p;
return OK;
}
4. 出隊
Status deQueue(LinkQueue *Q, QElemType e)
{
if(Q.front == Q.rear) return ERROR;
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next; //隊頭元素p出隊
if(Q.rear == p) //如果隊中只有一個元素p, 則p出隊后成為空隊
Q.rear = Q.front; //給隊尾指針賦值
free(p); //釋放存儲空間
return OK;
}
四、順序隊列
用一組連續(xù)的存儲單元依次存放隊列的元素，并設(shè)兩個指針front、rear分別指示隊頭和隊尾元素的位置。
front：指向?qū)嶋H的隊頭；rear：指向?qū)嶋H隊尾的下一位置。
初態(tài)：front＝rear＝0；隊空：front＝rear;隊滿：rear＝M;
入隊：q[rear]=x; rear＝ rear+1; 出隊：x=q[front];front=front+1;
順序隊列的表示：
#define MAXQSIZE 100
typedef struct
{
QElemType *base;
int front; //頭指針指示器
int rear; //尾指針指示器
} SqQueue;
存在的問題：
隨著入隊、出隊操作的進行，整個隊列會整體向后移動，這樣就出現(xiàn)了下圖的現(xiàn)象：隊尾指針雖然已經(jīng)移到了最后，而隊列卻未真滿的“假溢出”現(xiàn)象，使得隊列的空間沒有得到有效的利用
那我們該如何解決假溢出的問題呢？
有以下兩種方法：
- 將隊中元素向隊頭移動：當(dāng)移動數(shù)據(jù)較多時將會影響隊列的操作速度。
- 采用循環(huán)隊列：Q[0]接在Q[MAXQSIZE-1]之后，一個更有效的方法是將隊列的數(shù)據(jù)區(qū)Q[0 .. MAXQSIZE-1]看成是首尾相連的環(huán)，即將表示隊首的元素Q[0]與表示隊尾的元素Q[MAXQSIZE–1]連接起來，形成一個環(huán)形表，這就成了循環(huán)隊列。當(dāng)Q.rear=MAXQSIZE-1時再入隊，令Q.rear=0, 則可以利用已被刪除的元素空間。如下圖。
五、循環(huán)隊列
在循環(huán)隊列中，不可以根據(jù)等式front == rear可以判別隊滿和隊空。因為此時條件是相同的，解決這種問題的方法一般有兩種。
少用（損失）一個空間,以尾指針加1等于頭指針作為隊滿的標(biāo)志。因此：當(dāng)front==rear，表示循環(huán)隊列為空；當(dāng)front ==（rear+1）% MAXLEN，表示循環(huán)隊列為滿。
在定義結(jié)構(gòu)體時，附設(shè)一個存儲循環(huán)隊列中元素個數(shù)的變量n，當(dāng)n==0時表示隊空；當(dāng)n==MAXLEN時為隊滿。
循環(huán)隊列的基本操作：
1. 初始化
Status initQueue (SqQueue *Q)
{
Q.base=(QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
if (!Q.base) exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
2. 求隊列長度
int queueLength(SqQueue *Q)
{
return (Q.rear - Q.front+MAXQSIZE) % MAXQSIZE;
}
3. 入隊
Status enQueue (SqQueue *Q, QElemType e)
{
if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}
4. 出隊
Status deQueue (SqQueue *Q, QElemType e)
{
if(Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1)%MAXQSIZE;
return OK;
}
到此這篇關(guān)于C利用語言實現(xiàn)數(shù)據(jù)結(jié)構(gòu)之隊列的文章就介紹到這了,更多相關(guān)C語言實現(xiàn)數(shù)據(jù)結(jié)構(gòu) 隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++編程中操作符的種類和用法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下，希望能夠給你帶來幫助2021-09-09
JSON是一種輕量級的數(shù)據(jù)交換格式,常用于在網(wǎng)絡(luò)之間傳輸數(shù)據(jù),本文主要介紹了C語言中cJSON的使用,具有一定的參考價值,感興趣的可以了解一下2024-04-04
C++中實現(xiàn)WebSocket通信的兩種方法：libwebsockets庫、Boost.Beast?庫
C++中WebSocket庫主要有以下幾個?：cpp-websocket?、asio_websocket?、websockets++?、?websocketpp?、?libwebsockets?、?uWebSockets?、Boost.Beast?、Simple-WebSocket-Server?,這篇文章使用libwebsockets庫、Boost.Beast?庫來實現(xiàn)c++中的WebSocket通信2025-01-01
c/c++ 標(biāo)準(zhǔn)庫 bind 函數(shù)詳解
bind是一組用于函數(shù)綁定的模板。在對某個函數(shù)進行綁定時，可以指定部分參數(shù)或全部參數(shù)，也可以不指定任何參數(shù)，還可以調(diào)整各個參數(shù)間的順序。這篇文章主要介紹了c/c++ 標(biāo)準(zhǔn)庫 bind 函數(shù) ,需要的朋友可以參考下2018-09-09
C語言函數(shù)調(diào)用的三種實現(xiàn)方法實例
C語言中函數(shù)的調(diào)用主要有如下三種方法,直接調(diào)用,函數(shù)指針調(diào)用,函數(shù)指針傳遞調(diào)用其中后兩種本質(zhì)一樣,但在有無返回值時還稍有差別,下面這篇文章主要給大家介紹了關(guān)于C語言函數(shù)調(diào)用的三種實現(xiàn)方法,需要的朋友可以參考下2022-01-01
本篇文章主要介紹了Qt實現(xiàn)FTP的上傳和下載的實例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07
大家好，本篇文章主要講的是C語言楊輝三角兩種實現(xiàn)方法，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
這篇文章主要介紹了C++中模板(Template)實現(xiàn)元素的反序，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
OpenCV4 實現(xiàn)背景分離的詳細步驟(背景減法模型)
背景分離（BS）是一種通過使用靜態(tài)相機來生成前景掩碼（即包含屬于場景中的移動對象像素的二進制圖像）的常用技術(shù)，本文給大家介紹OpenCV4 實現(xiàn)背景分離的詳細步驟，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了用C語言如何來實現(xiàn)字符串相乘的方法，這里我們會利用到memset函數(shù)，memset函數(shù)是對較大的結(jié)構(gòu)體或數(shù)組進行清零操作的一種最快方法，可以說是初始化內(nèi)存的“萬能函數(shù)”，下面我們詳細了解一下2022-03-03