程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> Java數據結構之隊列(動力節點Java學院整理)

Java數據結構之隊列(動力節點Java學院整理)

編輯:關於JAVA

Java數據結構之隊列(動力節點Java學院整理)。本站提示廣大學習愛好者:(Java數據結構之隊列(動力節點Java學院整理))文章只能為提供參考,不一定能成為您想要的結果。以下是Java數據結構之隊列(動力節點Java學院整理)正文


隊列的定義:

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

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

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

(3)當隊列中沒有元素時稱為空隊列。

(4)隊列亦稱作先進先出(First In First Out)的線性表,簡稱為FIFO表。

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

隊列的存儲結構及實現

隊列的順序存儲結構

(1) 順序隊列的定義:

  隊列的順序存儲結構稱為順序隊列,順序隊列實際上是運算受限的順序表。

(2)順序隊列的表示:

和順序表一樣,順序隊列利用內存中一段連續的存儲空間來存放當前隊列中的元素。

由於隊列的隊頭和隊尾的位置是變化的,設置兩個指針front和rear分別指示隊頭元素和隊尾元素,它們的初值在隊列初始化時均應置為0。

(3)順序隊列的基本操作

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

出隊時:刪去front所指的元素,然後將front加1並返回被刪元素。

(4)順序表的溢出現象

 ①“下溢”現象

 當隊列為空時,做出隊運算產生的溢出現象。“下溢”是正常現象,常用作程序控制轉移的條件。

② "真上溢"現象

當隊列滿時,做進棧運算產生空間溢出的現象。“真上溢”是一種出錯狀態,應設法避免。

③ "假上溢"現象

由於入隊和出隊操作中,頭尾指針只增加不減小,致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小於內存中本分配的空間時,也可能由於尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。如下圖

循環隊列:

如上圖所示,這種頭尾相接的順序存儲結構稱為循環隊列(circular queue)。

循環隊列中需要注意的幾個重要問題:

①隊空的判定條件,隊空的條件是front=rear;

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

循環隊列的java實現代碼

 public class Queue { 
   private int size;  //當前隊列元素個數 
   private int[] Array;//存放隊列元素的數組 
   private int MaxSize;//隊列最大尺寸 
   //構造函數 
   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數據結構之隊列(動力節點Java學院整理),希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復大家的。在此也非常感謝大家對網站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved