C++中隊(duì)列的建立與操作詳細(xì)解析
什么是隊(duì)列結(jié)構(gòu)
隊(duì)列結(jié)構(gòu)是從數(shù)據(jù)運(yùn)算來分類的，也就是說隊(duì)列結(jié)構(gòu)具有特殊的運(yùn)算規(guī)則。而從數(shù)據(jù)的邏輯結(jié)構(gòu)來看，隊(duì)列結(jié)構(gòu)其實(shí)就是一種線性結(jié)構(gòu)。如果從數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)來進(jìn)一步劃分，隊(duì)列結(jié)構(gòu)可以分成兩類。
順序隊(duì)列結(jié)構(gòu)：即使用一組地址連續(xù)的內(nèi)存單元依次保存隊(duì)列中的數(shù)據(jù)。在程序中，可以定義一個(gè)指定大小的結(jié)構(gòu)數(shù)組來作為隊(duì)列。
鏈?zhǔn)疥?duì)列結(jié)構(gòu)：即使用鏈表形式保存隊(duì)列中各元素的值。
在隊(duì)列結(jié)構(gòu)中允許對(duì)兩端進(jìn)行操作，但是兩端的操作不同。在表的一端只能進(jìn)行刪除操作，稱為隊(duì)頭；在表的另一端只能進(jìn)行插入操作，稱為隊(duì)尾。如果隊(duì)列中沒有數(shù)據(jù)元素，則稱之為空隊(duì)列。從數(shù)據(jù)的運(yùn)算角度分析，隊(duì)列是按照“先進(jìn)先出”的原則處理結(jié)點(diǎn)的。
可以將隊(duì)列結(jié)構(gòu)理解成是：超市排隊(duì)結(jié)賬的人群，排在隊(duì)首的人先結(jié)賬，然后不斷會(huì)有人排在隊(duì)尾等待結(jié)賬，這就是一個(gè)先來先服務(wù)的隊(duì)列的現(xiàn)實(shí)中的例子。
一般隊(duì)列結(jié)構(gòu)的基本操作只有兩個(gè)：
入隊(duì)列：將一個(gè)元素添加到隊(duì)尾（相當(dāng)于到隊(duì)列最后排隊(duì)等待）
出隊(duì)列：將對(duì)頭的元素取出，同時(shí)刪除該元素，使后一個(gè)元素成為隊(duì)頭。
初次之外，還有初始化隊(duì)列、獲取隊(duì)列長(zhǎng)度的簡(jiǎn)單運(yùn)算。下面，我們就是用C++建立順序隊(duì)列結(jié)構(gòu)，并完成順序隊(duì)列結(jié)構(gòu)的基本運(yùn)算。
準(zhǔn)備數(shù)據(jù)
準(zhǔn)備數(shù)據(jù)就是定義在隊(duì)列操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等。
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //隊(duì)列數(shù)組
int head; //隊(duì)頭
int tail; //隊(duì)尾
};
這里，定義了隊(duì)列結(jié)構(gòu)的最大長(zhǎng)度QUEUELEN ,隊(duì)列結(jié)構(gòu)數(shù)據(jù)元素的類型DATA以及隊(duì)列結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)SQType。在數(shù)據(jù)結(jié)構(gòu)SQType中，data為數(shù)據(jù)元素，head為隊(duì)首的序號(hào)，tail為隊(duì)尾的序號(hào)。當(dāng)head=0時(shí)表示隊(duì)列為空，當(dāng)tail=QUEUELEN時(shí)表示隊(duì)列滿。
初始化隊(duì)列數(shù)據(jù)
順序隊(duì)列的初始化操作步驟如下：
（1）按符號(hào)常量QUEUELEN指定的大小申請(qǐng)一段內(nèi)存空間，用來保存隊(duì)列中的數(shù)據(jù)。
（2）設(shè)置head=0和tail=0，表示一個(gè)空棧。
示例代碼如下：
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申請(qǐng)隊(duì)列的內(nèi)存空間
{
q->head=0; //設(shè)置隊(duì)首
q->tail=0; //設(shè)置隊(duì)尾
return q;
}
else
{
return NULL; //返回空
}
}
首先使用new申請(qǐng)內(nèi)存，申請(qǐng)成功以后設(shè)置隊(duì)頭和隊(duì)尾，然后返回申請(qǐng)內(nèi)存的首地址，如果申請(qǐng)失敗則返回NULL。
判斷空隊(duì)列
判斷空隊(duì)列是判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為空。如果是空隊(duì)列，則表示該隊(duì)列結(jié)構(gòu)中國(guó)沒有數(shù)據(jù)。此時(shí)可以進(jìn)入如隊(duì)列操作，不可以進(jìn)行出隊(duì)列操作。
示例代碼如下：
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
輸入?yún)?shù)q為一個(gè)指向操作的隊(duì)列的指針。程序中，根據(jù)隊(duì)列head是否等于tail判斷隊(duì)列是否為空。
判斷滿隊(duì)列
判斷滿隊(duì)列就是判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為滿。如果是滿隊(duì)列，則表示該隊(duì)列中沒有多余的空間來保存額外數(shù)據(jù)。測(cè)試不可以進(jìn)行入隊(duì)列操作，可以進(jìn)行出隊(duì)列操作。
示例代碼如下：
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN)
}
輸入?yún)?shù)q為一個(gè)指向操作的隊(duì)列的指針。程序中，根據(jù)隊(duì)列tail是否等于隊(duì)列的最大值QUEUELEN判斷隊(duì)列是否是滿的。
清空隊(duì)列
清空隊(duì)列就是清楚一個(gè)隊(duì)列中的所有的數(shù)據(jù)。示例代碼如下：
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
將隊(duì)列頂指針head和尾指針tail設(shè)置為0，表示執(zhí)行清空操作。
釋放空間
釋放空間是釋放隊(duì)列結(jié)構(gòu)所占用的內(nèi)存單元。由前面可知，在初始化隊(duì)列結(jié)構(gòu)時(shí)，使用了new關(guān)鍵字分配內(nèi)存單元。雖然可以使用清空隊(duì)列操作，但是清空隊(duì)列操作并沒有釋放內(nèi)存空間，這就需要使用delete關(guān)鍵字釋放所占的內(nèi)存單元。
示例代碼如下：
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
程序中，調(diào)用了得delete釋放new申請(qǐng)的內(nèi)存空間。
入隊(duì)列
入隊(duì)列是隊(duì)列結(jié)構(gòu)的基本操作，主要操作是將數(shù)據(jù)元素保存到隊(duì)列結(jié)構(gòu)。入隊(duì)列操作的具體步驟如下：
（1）首先判斷隊(duì)尾，如果tail等于QUEUELEN，則表示溢出，進(jìn)行出錯(cuò)處理。否則執(zhí)行以下操作。
（2）設(shè)置tail=tail+1（隊(duì)列頂指針加1，指向入隊(duì)列地址）
（3）就將入隊(duì)列元素保存到tail指向的位置
示例代碼如下：
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"隊(duì)列已滿！操作失?。?<<endl;
return 0;
}else
{
q-data[q->tail++]=data; //將元素入隊(duì)列
return 1;
}
}
輸入?yún)?shù)q為指向操作的隊(duì)列的指針，輸入?yún)?shù)data為需要入隊(duì)列的數(shù)據(jù)元素。程序中首先判斷隊(duì)列是否溢出，如果溢出則不進(jìn)行入隊(duì)列操作，否則修改隊(duì)列頂指針的值，再將元素入隊(duì)列。
因?yàn)閠ail的值從0開始，當(dāng)前的值就是要插入的數(shù)組對(duì)應(yīng)的元素的位置，所以寫成q->tail++。
出隊(duì)列
出隊(duì)列是隊(duì)列結(jié)構(gòu)的基本操作，主要操作與入隊(duì)列相反，其實(shí)從隊(duì)列頂彈出一個(gè)數(shù)據(jù)元素。出隊(duì)列操作的具體步驟如下：
（1）首先判斷隊(duì)首head，如果head等于tail，則表示為空隊(duì)列，進(jìn)行出錯(cuò)處理。否則，執(zhí)行下面的步驟
（2）從隊(duì)列首部取出隊(duì)頭元素（實(shí)際返回隊(duì)頭元素的指針）
（3）修改隊(duì)首head的序號(hào)，使其指向后一個(gè)元素。
示例代碼如下：
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
cout<<"隊(duì)列已空！操作失?。?<<endl;
exit(0);
}else
{
return &(q->data[q->head++]);
}
}
輸入?yún)?shù)q為指向操作的隊(duì)列的指針。該函數(shù)返回值是一個(gè)DATA類型的數(shù)據(jù)，返回值是指向該數(shù)據(jù)元素的指針。
讀結(jié)點(diǎn)數(shù)據(jù)
讀結(jié)點(diǎn)數(shù)據(jù)也就是讀取隊(duì)列結(jié)構(gòu)中結(jié)點(diǎn)的數(shù)據(jù)，這里的讀操作其實(shí)就是讀隊(duì)列頭的數(shù)據(jù)。需要助于的是，讀結(jié)點(diǎn)數(shù)據(jù)的操作和出隊(duì)列操作不同。讀結(jié)點(diǎn)數(shù)據(jù)的操作僅是顯示隊(duì)列頂結(jié)點(diǎn)數(shù)據(jù)的內(nèi)容，而出隊(duì)列操作則將隊(duì)列頂數(shù)據(jù)彈出，該數(shù)據(jù)不再存在。
示例代碼如下：
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空隊(duì)列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
該函數(shù)返回值同樣是一個(gè)DATA類型的指針數(shù)據(jù)，返回值是指向數(shù)據(jù)元素的指針。
計(jì)算隊(duì)列長(zhǎng)度
計(jì)算隊(duì)列長(zhǎng)度就是統(tǒng)計(jì)該隊(duì)列中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。計(jì)算隊(duì)列長(zhǎng)度的方法比較簡(jiǎn)單，直接隊(duì)尾序號(hào)減去隊(duì)首序號(hào)即可。
示例代碼如下：
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
隊(duì)列結(jié)構(gòu)操作實(shí)例代碼：
完整的代碼會(huì)比較長(zhǎng)，不過函數(shù)部分和上面介紹的基本一致，主要是看main函數(shù)中這些函數(shù)的用法：
#include<iostream>
#include<string>
using namespace std;
#define QUEUELEN 10
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //隊(duì)列數(shù)組
int head; //隊(duì)頭
int tail; //隊(duì)尾
};
/*******************隊(duì)列的初始化*************************/
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申請(qǐng)隊(duì)列的內(nèi)存空間
{
q->head=0; //設(shè)置隊(duì)首
q->tail=0; //設(shè)置隊(duì)尾
return q;
}
else
{
return NULL; //返回空
}
}
/*******************判斷空隊(duì)列*************************/
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
/*******************判斷滿隊(duì)列*************************/
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN);
}
/*******************清空隊(duì)列*************************/
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
/*******************釋放空間*************************/
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
/*******************入隊(duì)列操作*************************/
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"隊(duì)列已滿！操作失敗！"<<endl;
return 0;
}else
{
q->data[q->tail++]=data; //將元素入隊(duì)列
return 1;
}
}
/*******************出隊(duì)列操作*************************/
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
return NULL;
}else
{
return &(q->data[q->head++]);
}
}
/*******************讀結(jié)點(diǎn)數(shù)據(jù)*************************/
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空隊(duì)列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
/*******************計(jì)算隊(duì)列長(zhǎng)度*************************/
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
/*********************主函數(shù)******************************/
int main()
{
SQType *stack;
DATA data,*p;
stack=SQTypeInit(); //執(zhí)行初始化操作
cout<<"執(zhí)行入隊(duì)列操作："<<endl;
cout<<"輸入姓名,年齡進(jìn)行入隊(duì)操作："<<endl;
while(1)
{
cin>>data.name>>data.age;
if(data.age==0)
{
break; //若輸入為0，則退出
}
else
{
InSQType(stack,data);
}
}
cout<<"進(jìn)行出棧操作："<<endl;
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"讀取首結(jié)點(diǎn)數(shù)據(jù)："<<endl;
p=PeekSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"執(zhí)行出棧操作："<<endl;
while(1)
{
if(SQTypeIsEmpty(stack))
{
cout<<"所有數(shù)據(jù)出棧完畢，棧為空！"<<endl;
break;
}else
{
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
}
}
SQTypeFree(stack);
return 0;
}
程序運(yùn)行界面：
上一篇：結(jié)構(gòu)體類型數(shù)據(jù)作為函數(shù)參數(shù)(三種方法)
欄 目：C語言
本文標(biāo)題：C++中隊(duì)列的建立與操作詳細(xì)解析
本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/3957.html
您可能感興趣的文章
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對(duì)數(shù)函數(shù)的表達(dá)式 c語言中對(duì)數(shù)怎么表達(dá)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 01-10深入理解C++中常見的關(guān)鍵字含義
- 01-10使用C++實(shí)現(xiàn)全排列算法的方法詳解
- 01-10深入Main函數(shù)中的參數(shù)argc,argv的使用詳解
- 01-10APUE筆記之:進(jìn)程環(huán)境詳解
- 01-10c++中inline的用法分析
- 01-10如何尋找數(shù)組中的第二大數(shù)
閱讀排行
- 1C語言 while語句的用法詳解
- 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹的示例代碼(圣誕
- 3利用C語言實(shí)現(xiàn)“百馬百擔(dān)”問題方法
- 4C語言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
- 5c語言計(jì)算三角形面積代碼
- 6什么是 WSH(腳本宿主)的詳細(xì)解釋
- 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
- 8正則表達(dá)式匹配各種特殊字符
- 9C語言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
- 10C語言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對(duì)數(shù)函數(shù)的表達(dá)式 c語言中對(duì)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
- 04-02jquery與jsp,用jquery
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10使用C語言求解撲克牌的順子及n個(gè)骰子
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能？
- 01-10delphi制作wav文件的方法
- 01-10C#中split用法實(shí)例總結(jié)
- 01-11ajax實(shí)現(xiàn)頁(yè)面的局部加載
- 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什