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學院整理),希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復大家的。在此也非常感謝大家對網站的支持!