C語言數(shù)據(jù)結(jié)構(gòu)不掛科指南之隊列詳解
隊列
這篇博客主要介紹一下隊列的概念，并且采用 C 語言，編寫兩種存儲實現(xiàn)方式：順序存儲和鏈?zhǔn)酱鎯?/strong>，當(dāng)然還有常規(guī)的隊列基本操作的實現(xiàn)算法
隊列基本概念
標(biāo)準(zhǔn)解釋：隊列（Queue）是有限個**同類型數(shù)據(jù)元素的線性序列，是一種先進(jìn)先出**（First In First Out FIFO）的線性表，新鍵入的數(shù)據(jù)元素插在隊列尾端，出隊列的數(shù)據(jù)元素在隊列首部被刪除。
教材中給了一個示意圖，不錯
順序隊列結(jié)構(gòu)類型中有三個域：data、front、rear。
data:一維數(shù)組，存儲隊列中的數(shù)據(jù)元素 font：指向隊列首元素的前一個單元 rear：指向?qū)嶋H的隊列尾元素單元
參考示意圖
入隊列操作可以用兩條賦值語句
SQ.rear = SQ.rear+1; SQ.data[SQ.rear] = x;
出隊列操作可以用一條語句完成
SQ.front = SQ.front+1
但是，會出現(xiàn)一些問題，通過示意圖說明一下
當(dāng)然還有一種情況，一邊入隊列，一邊出隊列 注意下圖，SQ.front 下面還有空間
所以為了解決這種假溢出問題，聰明的開發(fā)人員，想出來新的解決辦法了，造一個環(huán)兒~
循環(huán)隊列
下面看一個圖，重點看一下 SQ.rear 與 SQ.front 的對應(yīng)位置
如果上述圖翻譯成 C 語言代碼，入隊核心邏輯為
SQ.rear = (SQ.rear+1) % maxsize ; SQ.data[SQ.rear] = x;
出隊列的核心邏輯為
SQ.front = (SQ.front+1)%maxsize;
你在學(xué)習(xí)的時候，肯定對SQ.rear+1和SQ.front+1有疑問
我們舉例來說明一下吧
順序隊列的 C 語言實現(xiàn)
接下來難度指數(shù)上升，開始用 C 語言編寫代碼吧
一頓操作之后，還是比較簡單的，總之不寫鏈?zhǔn)酱鎯Γ樞虻倪€是比較簡單的
#include <stdio.h>
#include <stdlib.h>
//循環(huán)隊列最大數(shù)據(jù)元素個數(shù)
const int maxsize = 8;
//循環(huán)隊列的結(jié)構(gòu)體
typedef struct cycqueue{
int *data;
int front,rear;
} CycQue;
//隊列初始化
void init(CycQue *CQ){
CQ->data = (int *)malloc(maxsize*sizeof(int));
CQ->front = 0;
CQ->rear = 0;
}
//判斷隊列是否為空
int empty(CycQue *CQ){
if(CQ->rear==CQ->front) return 1;
else return 0;
}
//入隊列
int EnQueue(CycQue *CQ,int x){
if((CQ->rear+1)%maxsize==CQ->front){
printf("隊列滿");
return 0;
}
else{
CQ->rear =(CQ->rear+1) % maxsize;
CQ->data[CQ->rear] = x;
return 1;
}
}
//出隊列
int OutQueue(CycQue *CQ){
if(empty(CQ)){
printf("隊列為空");
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)疥犃械?C 語言實現(xiàn)
鏈?zhǔn)疥犃衅鋵嵱兄暗慕?jīng)驗之后，寫起來難度系數(shù)也不會太高，接下來我們編寫一個核心的部分代碼
隊列的鏈接實現(xiàn)實際上是用一個帶有頭結(jié)點的單鏈表來表示隊列，成為鏈隊列 頭指針指向鏈表的頭結(jié)點 單鏈表的頭結(jié)點的 next 域指向隊列首結(jié)點 尾指針指向隊列尾結(jié)點，即單鏈表的最后一個結(jié)點
初始化
#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)); //生成隊列的頭結(jié)點
LQ->front = temp; //隊列頭指針指向隊列頭結(jié)點
LQ->rear = temp; //隊列尾指針指向隊列尾結(jié)點
(LQ->front)->next = NULL;
}
核心兩個操作入隊列和出隊列
入隊列代碼如下
//入隊列
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;
}出隊列這個事情就交給你自己吧，好好理解一下，就可以寫出來了
自考要點
在考試中，隊列容易出現(xiàn)編碼題目，占比在 7~10 分，所以還是蠻重要的呢！
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)不掛科指南之隊列詳解的文章就介紹到這了,更多相關(guān)C語言 隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在學(xué)習(xí)了循環(huán)、分支、和函數(shù)之后，可以寫一些簡單的小游戲來給自己的編程之路增添一份樂趣。不僅提升了編碼能力，還可以邊學(xué)邊玩，簡直妙哉妙哉2022-05-05
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)哈夫曼樹的具體代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)三子棋游戲，還可以自由擴展棋盤大小，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
單鏈表是后面要學(xué)的雙鏈表以及循環(huán)鏈表的基礎(chǔ)，要想繼續(xù)深入了解數(shù)據(jù)結(jié)構(gòu)以及C語言，我們就要奠定好這塊基石！接下來就和我一起學(xué)習(xí)吧2022-04-04
進(jìn)度條在很多時候都可以用到，有時我們需要在表格，樹狀欄中直觀顯示任務(wù)進(jìn)度或消耗百分比，本文就詳細(xì)的介紹一下Qt 進(jìn)度條的使用實例，感興趣的可以了解一下2021-06-06
這篇文章主要為大家詳細(xì)介紹了C語言時間函數(shù)之strftime()，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
對于線性表，我們可能要執(zhí)行下列操作：訪問表的第k個結(jié)點、在k這個結(jié)點之前或者之后插入一個新結(jié)點，抑或是刪除第k個結(jié)點等等操作，其中我們會遇到值對第一個或者最后一個結(jié)點插入、刪除、和訪問值的線性表，我們給它們以特殊的名稱：棧、隊列、雙端隊列2022-05-05
這篇文章主要為大家詳細(xì)介紹了C語言的文件操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)