隊(duì)列的定義：

隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。 

（1）允許刪除的一端稱為隊(duì)頭（Front）。

（2）允許插入的一端稱為隊(duì)尾（Rear）。

（3）當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。

（4）隊(duì)列亦稱作先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱為FIFO表。

   隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來(lái)的成員總是加入隊(duì)尾，每次離開的成員總是隊(duì)列頭上的（不允許中途離隊(duì)）。

隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

（1） 順序隊(duì)列的定義：

  隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。

（2）順序隊(duì)列的表示：

和順序表一樣，順序隊(duì)列利用內(nèi)存中一段連續(xù)的存儲(chǔ)空間來(lái)存放當(dāng)前隊(duì)列中的元素。

由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，設(shè)置兩個(gè)指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素，它們的初值在隊(duì)列初始化時(shí)均應(yīng)置為0。

（3）順序隊(duì)列的基本操作

入隊(duì)時(shí)：將新元素插入rear所指的位置的后一位。

出隊(duì)時(shí)：刪去front所指的元素，然后將front加1并返回被刪元素。

（4）順序表的溢出現(xiàn)象

 ①“下溢”現(xiàn)象

 當(dāng)隊(duì)列為空時(shí)，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。

② "真上溢"現(xiàn)象

當(dāng)隊(duì)列滿時(shí)，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。

③ "假上溢"現(xiàn)象

由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無(wú)法重新利用。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于內(nèi)存中本分配的空間時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為"假上溢"現(xiàn)象。如下圖

循環(huán)隊(duì)列：

如上圖所示，這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列（circular queue）。

循環(huán)隊(duì)列中需要注意的幾個(gè)重要問題：

①隊(duì)空的判定條件，隊(duì)空的條件是front=rear；

②隊(duì)滿的判定條件，（rear+1）%QueueSize=front。QueueSize為隊(duì)列初始空間大小。

循環(huán)隊(duì)列的java實(shí)現(xiàn)代碼

 public class Queue { 
   private int size;  //當(dāng)前隊(duì)列元素個(gè)數(shù) 
   private int[] Array;//存放隊(duì)列元素的數(shù)組 
   private int MaxSize;//隊(duì)列最大尺寸 
   //構(gòu)造函數(shù) 
   public Queue(int maxsize){ 
     MaxSize = maxsize; 
     Array = new int[MaxSize]; 
     size = 0;   
   } 
   //判斷隊(duì)列是否為空 
   public int IsEmpty(){ 
     if(size == 0) 
       return 0; 
     return -1; 
   } 
   //判斷隊(duì)列是否為滿 
   public int IsFull(){ 
     if(size == MaxSize) 
       return 0; 
     return -1; 
   } 
   //返回隊(duì)列長(zhǎng)度 
   public int GetLength(){ 
     return this.size; 
   } 
   //隊(duì)列插入 
   public int EnQueue(int x){ 
     //若隊(duì)列不滿，把x插到隊(duì)尾，返回0；否則返回-1； 
     if(IsFull() == -1){ 
       Array[size] = x; 
       size++; 
       return 0; 
     } 
     return -1; 
   } 
   //隊(duì)列刪除 
   public int DeEmpty(){ 
     //若隊(duì)列不空，則刪除對(duì)頭元素，返回該元素的值，否則返回-404； 
     if(IsEmpty() == -1){ 
       int x = Array[0]; 
       for(int j=0; j<MaxSize-1; j++) 
         Array[j] = Array[j+1];//前移 
       MaxSize--; 
       return x; 
     } 
     return -404; 
   } 
   //讀取隊(duì)列頭部元素 
   public int GetFront(){ 
     //讀隊(duì)頭，若隊(duì)列非空，則返回隊(duì)列頭元素的值，否則返回-404； 
     if(IsEmpty() == -1){ 
       return Array[0]; 
     } 
     return -404; 
   } 
 } 

以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)之隊(duì)列(動(dòng)力節(jié)點(diǎn)Java學(xué)院整理)，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

最新評(píng)論