Java隊列數據結構的實現
1.隊列的基本概念
什麼是隊列?
- 隊列是一種特殊的線性表
- 它隻允許在表的前端(隊頭)進行刪除操作
- 在表的後端(隊尾)進行插入操作
- 隊列是一個有序表(可以用數組或鏈表實現)
- 隊列先進先出
- 隊列開辟的是一塊連續的空間
順序隊列中的溢出現象:
- 真溢出:當隊列滿時,做進棧運算產生空間溢出的現象。
- 假上溢:由於入隊和出隊操作中,頭尾指針隻增加不減小,致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小於向量空間的規模時,也可能由於尾指針已超越向量空間的上界而不能做入隊操作。
2.循環隊列
在實際使用隊列時,為瞭使隊列空間能重復使用,往往對隊列的使用方法稍加改進:無論插入或刪除,一旦rear指針增1或front指針增1 時超出瞭所分配的隊列空間,就讓它指向這片連續空間的起始位置。自己真從MaxSize-1
增1變到0,可用取餘運算rear%MaxSize
和front%MaxSize
來實現。這實際上是把隊列空間想象成一個環形空間,環形空間中的存儲單元循環使用,用這種方法管理的隊列也就稱為循環隊列。除瞭一些簡單應用之外,真正實用的隊列是循環隊列
3.實現思路
由於普通隊列存在溢出問題所以這裡用數組來實現環形隊列
- 1、front指向隊列的首元素 初始為0
- 2、rear指向隊列尾元素的後一個位置 (空出來的一塊空間作為約定)初始為0
- 3、隊列滿的條件
:(rear+1) % maxSize = front
- 4、隊列空的條件:
rear = front
- 5、隊列中元素的個數
:(rear+maxSize-front) % maxSize
為什麼隊列滿的條件是(rear+1) % maxSize = front
(1)假設rear>front
由於當
rear-front=maxSize-1
rear+1-maxSize=front
rear>front
隊列滿時rear+1
一定等於maxSize
(2)假設
(rear+1) % maxSize = rear+1-maxSize =0
front>rear
由於當
front-rear=1
rear+1=front
front>rear
時rear+1
一定小於maxSize
所以(rear+1) % maxSize=rear+1
(3)有上述所示可以得出隊列滿的條件是
(rear+1) % maxSize = front
元素個數的計數與這相似
4.代碼實現
public class Queue { private int maxSzie; //隊列中能存儲的最大個數 private int frontPoint; //頭指針指向隊頭 private int rearPoint; //尾指針指向隊尾的後一個數據 private int[] array; //模擬隊列的數組 /** * 初始化隊列 */ public Queue(int max) { maxSzie = max; frontPoint = 0; rearPoint = 0; array = new int[max]; } /** * 判斷隊列是否為空 */ public boolean isEmpty(){ return frontPoint == rearPoint; } /** * 判斷隊列是否已滿 */ public boolean isFull(){ return (rearPoint+1)%maxSzie == frontPoint; } /** * 向隊列中添加數據 */ public void add(int x){ if (isFull()){ System.out.println("當前隊列已滿"); return; } //添加數據 array[rearPoint] = x ; //後移尾指針 rearPoint = (rearPoint+1) % maxSzie; System.out.println("添加成功"); } /** * 取出隊列中的數據 */ public int remove(){ if (isEmpty()){ throw new RuntimeException("當前隊列為空"); } //把隊頭的值賦值給臨時變量 int x = array[frontPoint]; //移除數據後頭指針需要向後移動 時其指向新的隊頭 frontPoint = (frontPoint+1) % maxSzie; System.out.println("移除成功"); return x; } /** * 獲取隊列頭數據 */ public int gethead(){ if (isEmpty()){ throw new RuntimeException("當前隊列為空"); } return array[frontPoint]; } /** * 遍歷隊列 */ public void show(){ int x = 0; for (int i = frontPoint; i <= (rearPoint+maxSzie-frontPoint)%maxSzie; i++) { x++; System.out.println("隊列的第"+x+"個數據是"+array[i]); } } }
public class QueueTest { public static void main(String[] args) { Queue queue = new Queue(5); Scanner scanner = new Scanner(System.in); char systemIn = ' '; boolean noEnd = true; while (noEnd){ System.out.println("a:add(添加數據)"); System.out.println("r:remove(刪除數據)"); System.out.println("h:head(獲取隊頭)"); System.out.println("s:show(遍歷隊列)"); System.out.println("e:exit(退出程序)"); System.out.println("請輸入字符"); systemIn = scanner.next().charAt(0); switch (systemIn){ case 'a': System.out.println("請輸入入隊的數據(數字)"); int x = Integer.parseInt(scanner.next()); queue.add(x); break; case 'r': queue.remove(); break; case 'h': int head = queue.gethead(); System.out.println("隊頭是"+head); break; case 's': queue.show(); break; case 'e': noEnd = false; break; } } } }
5.測試
插入元素:
當添加到第五個的時候隊列已滿插入失敗:
遍歷隊列:
移除元素:
查看隊頭:
刪除一個元素後再次遍歷隊列:
到此這篇關於Java隊列數據結構的實現的文章就介紹到這瞭,更多相關Java隊列數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java基礎之數組模擬循環隊列
- java數據結構循環隊列的空滿判斷及長度計算
- Java隊列篇之實現數組模擬隊列及可復用環形隊列詳解
- Java動態循環隊列是如何實現的
- java數據結構基礎:順序隊列和循環隊列