什么是隊(duì)列結(jié)構(gòu)：
隊(duì)列是允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的的線性表蒜茴。
隊(duì)列是一種先進(jìn)先出的(First in First out)的線性表条获，簡(jiǎn)稱(chēng)為FIFO.允許插入的一端稱(chēng)為隊(duì)尾，允許刪除的一端稱(chēng)為隊(duì)頭多搀。
如果從數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)進(jìn)一步劃分,隊(duì)列結(jié)構(gòu)包括兩類(lèi).
- 順序隊(duì)列存儲(chǔ)結(jié)構(gòu):即使用一組地址連續(xù)的內(nèi)存單元依次保存隊(duì)列中的數(shù)據(jù),在程序中,可以定義一個(gè)指定大小的結(jié)構(gòu)數(shù)組作為隊(duì)列.
- 即使用鏈表形式保存隊(duì)列中各元素的值.
典型的隊(duì)列結(jié)構(gòu)如下圖:
舉兩個(gè)生活中的例子。相信大家灾部，在用電腦工作娛樂(lè)時(shí)康铭，都會(huì)碰到這樣的現(xiàn)象。當(dāng)我們點(diǎn)擊程序或進(jìn)行其他操作時(shí)赌髓，電腦處于死機(jī)狀態(tài)从藤。正當(dāng)我們準(zhǔn)備Reset時(shí)催跪，它突然像打了雞血似的，突然把剛才我們的操作呛哟，按順序執(zhí)行了一遍叠荠。之所以會(huì)出現(xiàn)這個(gè)現(xiàn)象，是因?yàn)椴僮飨到y(tǒng)的多個(gè)程序扫责，需要通過(guò)一個(gè)管道輸出榛鼎，而按先后順序排隊(duì)造成的。
還有有個(gè)例子鳖孤，在我們打客服熱線時(shí)者娱，有時(shí)會(huì)出現(xiàn)等待的現(xiàn)象。當(dāng)其他客戶掛斷電話苏揣，客服人員才會(huì)接通我們的電話黄鳍。因?yàn)榭头藛T相對(duì)于客戶而言，總是不夠的平匈，當(dāng)客戶量大于客服人員時(shí)框沟，就會(huì)造成排隊(duì)等待的想象。
操作系統(tǒng)增炭、客服系統(tǒng)忍燥，都是應(yīng)用了一種數(shù)據(jù)結(jié)構(gòu)才實(shí)現(xiàn)了這種先進(jìn)先出的排隊(duì)功能，這個(gè)數(shù)據(jù)結(jié)構(gòu)就是隊(duì)列隙姿。
隊(duì)列的基本操作一般只有兩個(gè):
- 入隊(duì)列:將一個(gè)元素添加到隊(duì)尾(相當(dāng)于到隊(duì)列最后排隊(duì)等候)
- 出隊(duì)列:將隊(duì)頭的元素依次取出,同時(shí)刪除該元素,使后一個(gè)元素成為隊(duì)頭.
除了這兩個(gè)主要的還有初始化隊(duì)列,獲取隊(duì)列長(zhǎng)度等簡(jiǎn)單操作.下面我們就分析怎么用java實(shí)現(xiàn)隊(duì)列結(jié)構(gòu).
準(zhǔn)備數(shù)據(jù)
static final int QUEUELEN = 15;
class DATA4
{
String name;
int age;
}
class SQType
{
DATA4 [] data = new DATA4[QUEUELEN]; //隊(duì)列數(shù)組
int head; //隊(duì)頭
int tail; //隊(duì)尾
}
首先我們定義了一個(gè)隊(duì)列的最大長(zhǎng)度QUEUELEN,然后定義了隊(duì)列中結(jié)點(diǎn)的數(shù)據(jù)DATA4,SQType是我們定義的隊(duì)列結(jié)構(gòu)類(lèi).其中數(shù)組
data是用來(lái)保存隊(duì)列數(shù)據(jù)的,head表示隊(duì)列的隊(duì)頭,tail是表示隊(duì)列的對(duì)尾,每一次添加一個(gè)元素的時(shí)候,就是入隊(duì)列.我們把元素指向當(dāng)前tail所指向的位置,tail所指向的就是隊(duì)尾,現(xiàn)在原來(lái)隊(duì)尾就是空的,現(xiàn)在添加元素了,我們把tail指向下一個(gè)空,我們?nèi)〕鰯?shù)據(jù)的時(shí)候,也就是出隊(duì)列.隊(duì)頭肯定是有數(shù)據(jù)的,所以我們直接通過(guò)head取出一個(gè)數(shù)據(jù),然后把head指向下一個(gè)元素,也就是讓下一個(gè)元素當(dāng)隊(duì)頭.Ok,隊(duì)列的入隊(duì)列操作和出隊(duì)列操作就是這樣!下面我們開(kāi)始吧
初始化隊(duì)列機(jī)構(gòu)
在使用順序隊(duì)列之前,首先要?jiǎng)?chuàng)建一個(gè)空的順序結(jié)構(gòu),也就是初始化一個(gè)隊(duì)列結(jié)構(gòu),步驟如下:
1.按符號(hào)常量QUEUELEN指定的大小申請(qǐng)一片內(nèi)存空間,用來(lái)保存隊(duì)列中的數(shù)據(jù).
2.設(shè)置head=0,和tail=0,表示一個(gè)空棧.
代碼如下:
public SQType SQTypeInit(){
SQType q;
if((q=new SQType())!=null){ //申請(qǐng)內(nèi)存
q.head = 0; //設(shè)置隊(duì)尾
q.tail = 0; //設(shè)置隊(duì)尾
return q;
}else
{
return null; //返回null
}
}
在上訴代碼,使用關(guān)鍵字new申請(qǐng)內(nèi)存,申請(qǐng)成功后設(shè)置隊(duì)頭和隊(duì)尾,然后返回申請(qǐng)內(nèi)存的地址.如果申請(qǐng)內(nèi)存失敗,將返回null.
判斷空隊(duì)列
判斷空隊(duì)列即判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為空,只需要判斷head==tail就可以了.空隊(duì)列則不能在出隊(duì)列.
public boolean SQTypeIsEmpty(SQType q){
if(q!=null){
return q.head ==q.tail;
}
return false;
}
判斷滿隊(duì)列
判斷一個(gè)隊(duì)列是否為滿,如果滿隊(duì)列,則表示該隊(duì)列結(jié)構(gòu)中沒(méi)有多余的空間來(lái)保存額外數(shù)據(jù),滿了就不可以進(jìn)行入隊(duì)列操作,而可以進(jìn)行出隊(duì)列.
public boolean SQTypeIsFull(SQType q){
if(q!=null){
return q.tail == QUEUELEN;
}
return false;
}
清空隊(duì)列
清空一個(gè)隊(duì)列中所有的數(shù)據(jù).
public void SQTypeClear(SQType q){
if(q!=null){
q.head = 0;
q.tail = 0;
}
}
釋放空間
釋放空間及釋放隊(duì)列結(jié)構(gòu)所占用的內(nèi)存單元.
public void SQTypeFree(SQType q){
if(q!=null){
q = null;
}
}
入隊(duì)列
入隊(duì)列是隊(duì)列結(jié)構(gòu)的基本操作.主要是把數(shù)據(jù)保存到隊(duì)列結(jié)構(gòu)中,步驟如下:
1.首先判斷隊(duì)列是否滿了,如果隊(duì)列滿了,就算了
2.把當(dāng)前數(shù)據(jù)元素指向現(xiàn)在的隊(duì)尾tail
3.把tail=tail+1 ,向后移動(dòng)一個(gè)位置.
public boolean SQTypeInsert(SQType q,DATA4 data){
if(!SQTypeIsFull(q)){ //判斷隊(duì)列是否滿了
q.data[q.tail++] = data; //先入隊(duì)列,后位置向后移動(dòng)
return true; //入隊(duì)列成功
}
return false; //入隊(duì)列失敗
}
出隊(duì)列
出隊(duì)列是隊(duì)列結(jié)構(gòu)的基本操作,主要把數(shù)據(jù)從隊(duì)列結(jié)構(gòu)中隊(duì)頭的位置推出來(lái),步驟如下:
1.判斷隊(duì)列head,如果head等于tail,等表示為空隊(duì)列.
2.從隊(duì)列首部取出隊(duì)頭元素(實(shí)際是返回隊(duì)頭元素的引用)
3.設(shè)修改頭head的序號(hào),使其指向后一個(gè)元素.
public DATA4 SQTypeOut(SQType q){
if(!SQTypeIsEmpty(q)){ //判斷隊(duì)列是否為空
return q.data[q.head++]; //從隊(duì)列取出數(shù)據(jù),并且head指向下一個(gè)元素
}
return null;
}
讀取結(jié)構(gòu)數(shù)據(jù)
讀結(jié)點(diǎn)數(shù)據(jù)的操作僅顯示隊(duì)列頂結(jié)點(diǎn)數(shù)據(jù)的內(nèi)容,而出隊(duì)列操作則將隊(duì)頂數(shù)據(jù)彈出,該數(shù)據(jù)就不再不存在了.
public DATA4 SQTypePeek(SQType q){
if(!SQTypeIsEmpty(q)){ //判斷隊(duì)列是否為空
return q.data[q.head]; //從隊(duì)列取出數(shù)據(jù)
}
return null;
}
計(jì)算隊(duì)列長(zhǎng)度
獲取隊(duì)列結(jié)構(gòu)中結(jié)點(diǎn)的數(shù)據(jù)的個(gè)數(shù).
public int SQTypeInt(SQType q){
int len = 0;
if(q!=null){
len = q.tail-q.head;
}
return len;
}
