隊列的定義：

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

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

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

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

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

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

隊列的存儲結(jié)構(gòu)及實現(xiàn)

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

（1） 順序隊列的定義：

  隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運算受限的順序表。

（2）順序隊列的表示：

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

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

（3）順序隊列的基本操作

入隊時：將新元素插入rear所指的位置的后一位。

出隊時：刪去front所指的元素，然后將front加1并返回被刪元素。

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

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

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

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

當(dāng)隊列滿時，做進(jìn)棧運算產(chǎn)生空間溢出的現(xiàn)象。“真上溢”是一種出錯狀態(tài)，應(yīng)設(shè)法避免。

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

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

循環(huán)隊列：

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

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

①隊空的判定條件，隊空的條件是front=rear；

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

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

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

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

最新評論