C語言數(shù)據(jù)結(jié)構(gòu)不掛科指南之隊列詳解
隊列
這篇博客主要介紹一下隊列的概念，并且采用 C 語言，編寫兩種存儲實現(xiàn)方式：順序存儲和鏈?zhǔn)酱鎯?/strong>，當(dāng)然還有常規(guī)的隊列基本操作的實現(xiàn)算法
隊列基本概念
標(biāo)準(zhǔn)解釋：隊列（Queue）是有限個**同類型數(shù)據(jù)元素的線性序列，是一種先進先出**（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)文章
C++缺省參數(shù)與重載函數(shù)(超詳細(xì)!)
無論使用什么語言函數(shù)都是代碼段中必不可少的部分,因此我們有必要深入認(rèn)識一下C++中函數(shù)的兩種特殊用法,缺省參數(shù),函數(shù)重載,這篇文章主要給大家介紹了關(guān)于C++缺省參數(shù)與重載函數(shù)的相關(guān)資料,需要的朋友可以參考下2024-06-06
在之前的文章里，我們學(xué)習(xí)的一直是一對一的線性結(jié)構(gòu)，可現(xiàn)實中，還有很多一對多的情況需要處理，所以我們需要研究這樣一種一對多的數(shù)據(jù)結(jié)構(gòu)——樹2022-05-05
C++實現(xiàn)LeetCode(676.實現(xiàn)神奇字典)
這篇文章主要介紹了C++實現(xiàn)LeetCode(676.實現(xiàn)神奇字典),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
win10系統(tǒng)VS2019配置點云庫PCL1.12.1的詳細(xì)流程
這篇文章主要介紹了win10系統(tǒng)VS2019配置點云庫PCL1.12.1的教程與經(jīng)驗總結(jié),本文記錄小白在配置過程中踩過的一些小坑，需要的朋友可以參考下2022-07-07
C++實現(xiàn)惡搞電腦關(guān)機小程序的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用C++實現(xiàn)一個簡單的惡搞電腦關(guān)機小程序，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以嘗試一下2022-11-11
C語言輾轉(zhuǎn)相除法求2個數(shù)的最小公約數(shù)
輾轉(zhuǎn)相除法最大的用途就是用來求兩個數(shù)的最大公約數(shù)。下面通過本文給大家介紹C語言輾轉(zhuǎn)相除法求2個數(shù)的最小公約數(shù)，非常不錯，感興趣的朋友一起看看吧2016-12-12
這篇文章主要介紹了C++歸并算法,實例分析了C++實現(xiàn)基于歸并算法合并線性表的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
c++中關(guān)鍵字有幾十個，其中類型修飾關(guān)鍵字有l(wèi)ong, short, singed, unsigned。今天我們就來談一下經(jīng)常被大家忽視的signed關(guān)鍵字2015-01-01
C語言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實現(xiàn)
這篇文章主要介紹了C語言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實現(xiàn),,文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的朋友可以參考一下2022-09-09
C 語言restrict 關(guān)鍵字的使用淺談，需要的朋友可以參考一下2013-04-04