java中用數組實現環形隊列的示例代碼
本篇文章主要講述瞭使用數組實現環形隊列的思路以及具體代碼
一、隊列是什麼
我們先來看下百科的解釋：
隊列是一種特殊的線性表，特殊之處在於它隻允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
總結起來兩點：
1.一種線性表
2.添加操作隻能在表尾，刪除操作在表頭（先進先出）
二、實現隊列的思路
1.初始化一個空隊列
初始化一個大小固定的數組，並將頭指針，尾指針都指向下表為0的位置，但其實這種初始化頭指針指向的是隊首，尾指針指向的是隊尾的後一個元素。
2.往隊列裡添加元素
往隊列裡添加元素，尾指針後移一位。
一直添加直到隊列滿
這個時候尾指針已經出現在數組下標外瞭
3.消費隊列元素
每消費一個隊列元素，頭指針指向的元素出隊，並且後移一位
再消費兩個
這個時候我們想往隊列裡繼續添加元素，尾指針後移，然後發現出現瞭假溢出的情況，因為尾指針無法再向後移動，而隊列實際上並沒有滿，我們又無法繼續往隊列裡添加數據。這個時候其實有兩種解決方案。
方案一：我們每消費一個元素，其後面的元素都整體往前移動一位，就像我們生活中排隊打飯一樣，後面的人都往前挪一挪。但這種方案帶來的後果是，帶來的時間開銷太大，因為基本上要操作所有的元素，所以這種方案不可行。
方案二：尾指針在指向下表為最後一個元素時，再添加元素，如果還有空位，就將尾指針重新指向0，頭指針在取到下表數組末尾時，如果前面還有元素，頭指針也指向0，這就是我們說的環形隊列。
三、實現環形隊列
1.環形隊列示例圖
尾指針重新指向零
再添加一個元素
連續消費三個元素，如果前面還有元素，頭指針也指向0
這個時候我們發現那個原來熟悉的隊列又回來瞭。
2.代碼實現
/**
* description:數組實現環形隊列
* author: xiaowang
* */
public class MyQueue<E> {
// 隊列最大個數
private int size;
// 元素真實個數
private int number;
// 頭指針，指向隊列的第一個元素即隊頭
private int front;
// 尾指針，指向隊尾的後一個元素(非隊尾)
private int rear;
// 隊列具體值
private Object[] values;
// 隊列滿標記，當隊列是滿的時候為true
private boolean isFullFlag;
/**構造器*/
public MyQueue(int size){
if (size<0){
throw new RuntimeException("初始化隊列時，隊列最大元素個數不能為負");
}
this.front = 0;
this.rear = 0;
this.number = 0;
this.isFullFlag = false;
this.size = size;
this.values = new Object[size];
}
/**往隊列裡添加元素 添加成功返回true 失敗返回false*/
public boolean addToQueue(E e){
// 判斷隊列是否已經滿瞭
if (isFullFlag){
System.out.println("隊列已滿,無法繼續添加元素");
return false;
}
// 添加元素
values[rear] = e;
// 元素個數加一
number++;
// 尾指針後移一位，若已經指向數組最後的下表，則重新指向0
if (rear == size-1){
rear = 0;
}else{
rear++;
}
// 添加完這個元素，判斷隊列是否已經滿瞭，若滿則標記為true
if (rear==front){
isFullFlag = true;
}
return true;
}
/**從隊列裡取出數據，隊頭數據*/
public E getFromQueue(){
// 判斷隊列是否為空
if (number==0||size==0){
System.out.println("隊列為空，無法從隊列中獲取數據");
return null;
}
// 臨時變量
E e = (E) values[front];
// 隊頭置空
values[front] = null;
// 個數減一
number--;
// 頭指針後移，若已經指向數組最後的下表，則重新指向0
if (front==size-1){
front = 0;
}else {
front++;
}
// 取隊列之前若是滿的狀態，則更新狀態
if (isFullFlag){
isFullFlag = false;
}
return e;
}
/**獲取目前有幾個元素正在進行排隊*/
public int getNumber(){
return number;
}
/**獲取隊列的最大個數*/
public int getSize(){
return size;
}
/**查看隊列在數組裡保存的詳細情況*/
public String toString(){
StringBuffer valueStr = new StringBuffer();
valueStr.append("[");
for (int i = 0; i < size; i++) {
if (i!=size-1){
valueStr.append(values[i]+",");
}else{
valueStr.append(values[i]+"]");
}
}
return valueStr.toString();
}
}
測試代碼
public class TestQueue {
public static void main(String[] args) {
MyQueue<String> queue = new MyQueue<String>(5);
Scanner scanner = new Scanner(System.in);
Scanner scanner2 = new Scanner(System.in);
boolean isCan = true;
while (isCan){
System.out.println("歡迎來到小王排隊系統，您可以使用以下功能。\n添加：1；取出：2；展示：3；獲取排隊個數：4；退出：0。");
int flag = scanner.nextInt();
switch (flag){
case 1 :
System.out.println("請輸入一個數據：");
String data = scanner2.nextLine();
boolean isSuccess = queue.addToQueue(data);
if (isSuccess){
System.out.println("添加成功~~~");
}
break;
case 2 :
String dataFromQueue = queue.getFromQueue();
if (dataFromQueue!=null){
System.out.println("本次取出的數據為："+dataFromQueue);
}
break;
case 3 :
System.out.println("隊列詳情為：\n"+queue.toString());
break;
case 4 :
System.out.println("目前有"+queue.getNumber()+"個元素正在進行排隊");
break;
default:
isCan = false;
System.out.println("已退出...");
break;
}
}
}
}
總結
到此這篇關於java中用數組實現環形隊列的示例代碼的文章就介紹到這瞭,更多相關java 數組環形隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- None Found