什么是隊(duì)列結(jié)構(gòu)：

隊(duì)列是允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的的線性表。
隊(duì)列是一種先進(jìn)先出的(First in First out)的線性表，簡稱為FIFO.允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。
如果從數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)進(jìn)一步劃分,隊(duì)列結(jié)構(gòu)包括兩類.

• 順序隊(duì)列存儲(chǔ)結(jié)構(gòu):即使用一組地址連續(xù)的內(nèi)存單元依次保存隊(duì)列中的數(shù)據(jù),在程序中,可以定義一個(gè)指定大小的結(jié)構(gòu)數(shù)組作為隊(duì)列.
• 即使用鏈表形式保存隊(duì)列中各元素的值.

典型的隊(duì)列結(jié)構(gòu)如下圖:

image

舉兩個(gè)生活中的例子。相信大家，在用電腦工作娛樂時(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è)程序，需要通過一個(gè)管道輸出，而按先后順序排隊(duì)造成的。

還有有個(gè)例子，在我們打客服熱線時(shí)，有時(shí)會(huì)出現(xiàn)等待的現(xiàn)象。當(dāng)其他客戶掛斷電話，客服人員才會(huì)接通我們的電話。因?yàn)榭头藛T相對于客戶而言，總是不夠的，當(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ì)列長度等簡單操作.下面我們就分析怎么用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ì)列的最大長度QUEUELEN,然后定義了隊(duì)列中結(jié)點(diǎn)的數(shù)據(jù)DATA4,SQType是我們定義的隊(duì)列結(jié)構(gòu)類.其中數(shù)組
data是用來保存隊(duì)列數(shù)據(jù)的,head表示隊(duì)列的隊(duì)頭,tail是表示隊(duì)列的對尾,每一次添加一個(gè)元素的時(shí)候,就是入隊(duì)列.我們把元素指向當(dāng)前tail所指向的位置,tail所指向的就是隊(duì)尾,現(xiàn)在原來隊(duì)尾就是空的,現(xiàn)在添加元素了,我們把tail指向下一個(gè)空,我們?nèi)〕鰯?shù)據(jù)的時(shí)候,也就是出隊(duì)列.隊(duì)頭肯定是有數(shù)據(jù)的,所以我們直接通過head取出一個(gè)數(shù)據(jù),然后把head指向下一個(gè)元素,也就是讓下一個(gè)元素當(dāng)隊(duì)頭.Ok,隊(duì)列的入隊(duì)列操作和出隊(duì)列操作就是這樣!下面我們開始吧

初始化隊(duì)列機(jī)構(gòu)

在使用順序隊(duì)列之前,首先要?jiǎng)?chuàng)建一個(gè)空的順序結(jié)構(gòu),也就是初始化一個(gè)隊(duì)列結(jié)構(gòu),步驟如下:
1.按符號(hào)常量QUEUELEN指定的大小申請一片內(nèi)存空間,用來保存隊(duì)列中的數(shù)據(jù).
2.設(shè)置head=0,和tail=0,表示一個(gè)空棧.
代碼如下:

public SQType SQTypeInit(){
    SQType q;
    if((q=new SQType())!=null){                     //申請內(nèi)存
        q.head = 0;                                 //設(shè)置隊(duì)尾
        q.tail = 0;                                 //設(shè)置隊(duì)尾
        return q;
    }else
    {
        return null;                                 //返回null
    }
}

在上訴代碼,使用關(guān)鍵字new申請內(nèi)存,申請成功后設(shè)置隊(duì)頭和隊(duì)尾,然后返回申請內(nèi)存的地址.如果申請內(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)中沒有多余的空間來保存額外數(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ì)頭的位置推出來,步驟如下:
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ì)列長度

獲取隊(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;
    }