Java基礎之數組模擬循環隊列
一、隊列簡介
隊列是一個有序列表,遵循“先入先出”的原則,即先存入隊列的數據要先取出,後存入的數據後取出。
隊列有兩種存儲表示,順序表示和鏈式表示。順序表示可以用數組來實現。
二、數組模擬隊列
用數組模擬隊列時,設兩個值front=0,rear=0。front表示隊列首部第一個數據所在位置,rear表示尾部最後一個數據的下一個位置。
將數據插入數組隊列時(入隊),從尾部進行插入,即array[rear] = value,同時rear後移,rear++。取出數據時(出隊),從頭部取出數據,value = array[front],同時front後移front++。
當front=0,rear=maxSize(數組的最大長度),隊列滿,不能再存入數據。
這時如果執行出隊操作,又有空間可以存儲,但繼續插入數據,會出現溢出現象,即因數組越界而導致程序非法操作錯誤。而實際上空間並未占滿,所以稱這種現象為“假溢出”。這是由“隊尾入隊,隊頭出隊”的限制操作所造成的。
如何解決“假溢出”的問題呢?
答案就是循環隊列。
三、數組模擬循環隊列
將順序隊列變為一個環狀空間,front、rear和隊列元素之間的關系不變,隻是在循環隊列中,front、rear依次後移加1的操作可用“模”運算來實現。
通過取模,front、rear就可以在順序表空間內以頭尾銜接的方式“循環”移動。
元素出隊後,front = (front+1)%maxSize ;
元素入隊後,rear = (rear+1)%maxSize 。
(maxSize為數組隊列的最大長度)
例如,隊列最大長度為4,當rear=3時,存入數據,array[3]=value,rear後移一位,如果沒有取模運算,則rear=4,這時繼續插入數據,array[4]越界。
如果進行取模運算,rear = (rear+1)%maxSize ,這時rear=0,rear又重新回到瞭0的位置。這樣的運算,使得rear的值在0、1、2、3之間循環。
front的值同理。
寫瞭這麼多字,感覺還不如看代碼來得更容易理解一點。
四、代碼實現
數組模擬循環隊列
package com.ArrayQueue; import java.util.Scanner; public class CircleArrayQueueDemo { public static void main(String args[]){ int maxSize = 4; CircleArrayQueue queue = new CircleArrayQueue(maxSize); Scanner scanner = new Scanner(System.in); char key; boolean loop = true; while (loop) { //根據輸入的不同字母,進行對應的操作 System.out.println("a(add):添加一個數據"); System.out.println("g(get):取出一個數據"); System.out.println("h(head):展示頭部數據"); System.out.println("s(show):展示所有數據"); System.out.println("q(quit):退出程序"); //因為判滿條件的緣故,隊列的最大容量實為maxSize-1 System.out.printf("(隊列的最大容量為:%d)\n",maxSize-1); key = scanner.next().charAt(0);//接收一個字符 try { switch (key) { case 'a': System.out.println("請輸入一個數:"); int value = scanner.nextInt(); queue.addQueue(value); System.out.println("數據添加成功。"); break; case 'g': System.out.printf("取出的數據為:%d\n", queue.getQueue()); break; case 'h': queue.headQueue(); break; case 's': queue.showQueue(); break; case 'q': scanner.close(); loop = false; System.out.println("程序已退出。"); break; default: break; } } catch (RuntimeException e) { System.out.println(e.getMessage()); } } } } /** * 隊列的順序表示 * 數組模擬循環隊列 */ class CircleArrayQueue{ private int maxSize; private int front;//指向頭元素所在位置 private int rear;//指向尾元素所在位置的下一個位置 private int arr[];//存放數據的數組 //構造器,傳入數組最大容量值 public CircleArrayQueue(int size){ maxSize = size; front = 0; rear = 0; //雖然數組最大容量為maxSize,但實際用於存儲的隻有maxSize-1 arr = new int[maxSize]; } //判空條件:front == rear public boolean isEmpty(){ return front == rear; } //判滿條件:(rear+1)%maxSize == front public boolean isFull(){ return (rear+1)%maxSize == front; } //添加數據,入隊 public void addQueue(int n){ //判滿 checkFull(); arr[rear] = n; rear = (rear+1)%maxSize; } //取出數據,出隊 public int getQueue(){ //判空 checkEmpty(); int value = arr[front]; front = (front+1)%maxSize; return value; } //隊列中的有效值個數 public int size(){ return (rear-front+maxSize)%maxSize; } //展示隊列的所有數據 public void showQueue(){ //判空 checkEmpty(); for(int i=front;i<front+size();i++){ System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]); } System.out.printf("當前front=%d,rear=%d\n",front,rear); } //展示位於隊列頭部的元素值,不改變front的指向 public void headQueue(){ //判空 checkEmpty(); System.out.printf("頭部數據是:%d\n",arr[front]); } //檢測出隊列為空時,打印當前front,rear的值,拋出異常 public void checkEmpty(){ if (isEmpty()) { System.out.printf("當前front=%d,rear=%d\n",front,rear); throw new RuntimeException("隊列為空,不能取數據"); } } //檢測出隊列滿時,打印當前front,rear的值,拋出異常 public void checkFull(){ if(isFull()){ System.out.printf("當前front=%d,rear=%d\n",front,rear); throw new RuntimeException("隊列已滿,不能添加數據"); } } }
五、運行結果
到此這篇關於Java基礎之數組模擬循環隊列的文章就介紹到這瞭,更多相關Java數組模擬循環隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- java數據結構循環隊列的空滿判斷及長度計算
- Java隊列數據結構的實現
- Java隊列篇之實現數組模擬隊列及可復用環形隊列詳解
- java數據結構基礎:順序隊列和循環隊列
- Java動態循環隊列是如何實現的