C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列算法詳解
更新時(shí)間：2021年12月28日 14:29:27 作者：知心寶貝
這篇文章介紹了C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列的算法，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
一、前言
- 隊(duì)列在程序設(shè)計(jì)中經(jīng)常出現(xiàn)，如：操作系統(tǒng)中的排隊(duì)問題。
- 這篇文章主要介紹了隊(duì)列的基本概念、性質(zhì)，順序、鏈、循環(huán)三種不同的方法實(shí)現(xiàn)隊(duì)列，順序和循環(huán)隊(duì)列在算法中比較常用
二、基本概念
??
- 定義：隊(duì)列是允許在一端插入，另一端刪除的線性表
- 隊(duì)頭（front）：允許刪除的一端
- 隊(duì)尾（rear）：允許插入的一端
- 特點(diǎn)：先進(jìn)先出
三、順序隊(duì)列
動(dòng)態(tài)圖：
算法講解：?
- 圖解：入隊(duì)，rear++，出隊(duì)，front++
- 真溢出：front==0，rear==n-1
- 假溢出：front ! = 0，rear==n-1
結(jié)構(gòu)體：
#define MAXQSIZE 100;
Typedef struct{
QElemType element[MAXQSIZE]; //隊(duì)列的元素空間
int front; //頭指針，若隊(duì)列不空，指向隊(duì)頭元素；
int rear; //尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一個(gè)位置
}SeqQueue;
四、鏈隊(duì)列
- 定義：用鏈表實(shí)現(xiàn)的隊(duì)列，為了操作方便，通常采用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，設(shè)置一個(gè)隊(duì)頭指針和隊(duì)尾指針
- 隊(duì)頭指針：始終指向頭結(jié)點(diǎn)
- 隊(duì)尾指針：指向當(dāng)前最后一個(gè)元素
- 空的鏈隊(duì)列：隊(duì)頭指針和隊(duì)尾指針均指向頭結(jié)點(diǎn)
入隊(duì)：
int EnterQueue ( LinkQueue *Q; QElemType x ) {
//1. 為待插入結(jié)點(diǎn)開辟存儲(chǔ)空間
p = ( LinkQueueNode ) malloc ( sizeof ( QNode ) );
if (p==NULL ) return ( FALSE ); // 存儲(chǔ)空間分配失敗
//2. 將值 x放入新結(jié)點(diǎn)的數(shù)據(jù)域,令新結(jié)點(diǎn)的指針域?yàn)榭?
p->data = x; p->next = NULL;
// 3. 將新結(jié)點(diǎn)插入到隊(duì)列 Q 的尾, 并修改隊(duì)列 Q 的隊(duì)尾指針
Q->rear->next = p;
Q->rear = p;
return (TRUE);
} // EnterQueue
出隊(duì)：
int DeleteQueue ( LinkQueue *Q, QElemType *x ) {
// 1.如果隊(duì)列為空則無法進(jìn)行刪除，則返回 ERROR
if ( Q->front = = Q->rear ) return (FALSE);
// 2.令 p 指向隊(duì)列 Q 的頭, 并將隊(duì)頭結(jié)點(diǎn)的值取出并放入 x
p = Q->front->next; x = p->data;
//3. 修改隊(duì)頭指針
Q->front->next = p->next;
// 4. 若隊(duì)中只有一個(gè)元素，則P出隊(duì)后成為空隊(duì)
if ( Q->rear = = p ) Q->rear = Q->front;
free ( p ); // 釋放隊(duì)頭元素所占空間
return (TRUE);
} // DeleteQueue
五、循環(huán)隊(duì)列
概念：隊(duì)列的一種順序表示和實(shí)現(xiàn)方法，與順序棧類似
動(dòng)態(tài)圖：
?算法講解：?
- A? B? C? D入隊(duì)時(shí)，頭指針front不動(dòng)，rear=(rear+1)%n
- A? B? C? D出隊(duì)時(shí)，尾指針rear不動(dòng)，front=(front+1)%n
入隊(duì)：
int EnterQueue(SeqQueue *Q,QueueElementType x)
{
//1. 判斷隊(duì)列是否已經(jīng)滿了
if((Q->rear+1)%MAXSIZE==Q->front)
return (FALSE);
//2. 新元素x入隊(duì)
Q->element[Q->rear]=x;
// 3. 重新設(shè)置隊(duì)尾指針
Q->rear=(Q->rear+1)%MAXSIZE;
return (TRUE);
}
出隊(duì)：
int DeleteQueue(SeqQueue *Q,QueueElementType *x)
{
//1. 判斷隊(duì)列是否已經(jīng)空了
if(Q->front==Q->rear)
return(FALSE);
//2. 刪除隊(duì)列的隊(duì)頭元素，用x返回其值
*x=Q->element[Q->front];
// 3. 重新設(shè)置隊(duì)頭指針
Q->front=(Q->front+1)%MAXSIZE;
return(TRUE);
}
特點(diǎn)：
- 隊(duì)空： rear==front
- 隊(duì)滿：(rear+1)%n==front
- 入隊(duì)：rear=(rear+1)%n
- 出隊(duì)：front=(front+1)%n
- 隊(duì)中元素個(gè)數(shù)：（rear-front+n）%n
六、總結(jié)與提高
對(duì)于使用C++編程來說，上文隊(duì)列的判空、判滿、插入、刪除等等一系列代碼，不需要你完全掌握，C++的STL標(biāo)準(zhǔn)庫中為你準(zhǔn)備好了函數(shù)等你調(diào)用。
C++queue頭文件：
#include<queue> //#include<bits/stdc++.h>或者萬能頭文件 using namespace std;
C++queue具體操作：
用queue定義q類（定義什么都可以，只要把s變成定義的字母就可以調(diào)用C++中的函數(shù)）,具體使用方法為：
| 函數(shù) | 用法 |
|---|---|
| q.empty() | 判斷隊(duì)列是否為空，不為空返回1，為空返回0 |
| q.size() | 返回隊(duì)列中元素個(gè)數(shù) |
| q.pop() | 刪除隊(duì)列首元素 |
| q.front() | 返回隊(duì)列首元素，不刪除該元素 |
| q.back() | 返回隊(duì)列尾元素，不刪除該元素 |
| s.push() | 隊(duì)尾插入新的元素 |
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
使用C語言實(shí)現(xiàn)本地socke通訊的方法
這篇文章主要介紹了?使用C語言實(shí)現(xiàn)本地socke通訊,代碼分為服務(wù)器代碼和客戶端代碼，代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-12-12
這篇文章主要為大家詳細(xì)介紹了如何使用C語言實(shí)現(xiàn)遍歷文件夾中的文件,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考一下2024-02-02
c語言連接mysql數(shù)據(jù)庫的實(shí)現(xiàn)方法
C語言連接mysql數(shù)據(jù)庫，需要相應(yīng)的頭文件和lib文件，如果你安裝Mysql數(shù)據(jù)庫，會(huì)在安裝目錄下找到這些庫文件，如果沒有安裝，也可以在網(wǎng)上找到2012-05-05
C++的繼承機(jī)制相對(duì)其他語言是比較復(fù)雜的一種，不同于java只支持單繼承，C++不僅支持單繼承，也支持多繼承。本文將詳細(xì)講解C++中單繼承與多繼承的使用，需要的可以參考一下2022-04-04
這篇文章主要為大家介紹了深入的分析了C語言與C++的區(qū)別與聯(lián)系，文中通過詳細(xì)的示例進(jìn)行了對(duì)比，以便大家更容易的看懂理解，有需要的朋友可以借鑒參考下2021-11-11
很多C++的初學(xué)者發(fā)現(xiàn),控制臺(tái)的顏色永遠(yuǎn)是黑白的,這未免太單調(diào)了,怎么才能使字體像那些軟件一樣呈彩色呢？現(xiàn)在,我們就將學(xué)習(xí)C++ 設(shè)置字體顏色的方法2023-08-08
C語言遞歸應(yīng)用實(shí)現(xiàn)掃雷游戲
這篇文章主要為大家詳細(xì)介紹了C語言遞歸應(yīng)用實(shí)現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C/C++實(shí)現(xiàn)遍歷文件夾最全方法總結(jié)
這篇文章主要為大家介紹了C/C++實(shí)現(xiàn)遍歷文件夾功能的最全方法總結(jié)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-09-09
柔性數(shù)組既數(shù)組大小待定的數(shù)組, C語言中結(jié)構(gòu)體的最后一個(gè)元素可以是大小未知的數(shù)組,本文就來介紹一下柔性數(shù)組的用法，感興趣的可以了解一下2024-03-03
這篇文章主要為大家詳細(xì)介紹了C語言掃雷游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11