Java隊列篇之實現數組模擬隊列及可復用環形隊列詳解
隊列簡介
隊列是一個有序列表，可以用數組或是鏈表來實現。
遵循先入先出的原則。即先存入隊列的數據，先取出，後存入的後取出。
示意圖：(使用數組模擬隊列示意圖)
有兩個分別指向頭部和尾部的“指針”。
數組模擬隊列（無法復用）
1、實現思路
隊列本身是有序列表，若使用數組的結構來存儲隊列的數據，則隊列數組的聲明如下圖，其中maxSize是該隊列的最大容量。
因為隊列的輸出、輸入是分別從前後端來處理，因此需要兩個變量front及rear分別記錄隊列前後端的下標，front會隨著數據輸出而改變，而rear則是隨著數據輸入而改變，如圖所示：
當我們將數據存入隊列時稱為addQueue，addQueue的處理需要有兩個步驟：
①將尾指針往後移。
②若尾指針rear小於隊列的最大下標maxSize-1，則將數據存入rear 所指的數組元素中，否則無法存入數據。
rear+1當front== rear[空]
rear==maxSize-1[隊列滿]
2、代碼實現
①數組實現隊列類
class ArrQueue {
private int maxSize; //隊列（數組）最大容量
private int front; //指向隊列頭部
private int rear; //指向隊列尾部
private int[] queue;
//創造隊列的構造器
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new int[maxSize];
front = -1; //其實是隊列第一個元素的前一個索引
rear = -1; //最後一個元素的索引
}
//判斷是否滿
public boolean isFull(){
return rear == maxSize - 1;
}
//判斷是否空
public boolean isEmpty(){
return front == rear;
}
//添加元素
public void addQueue(int n){
if (isFull()){
System.out.println("隊列已經滿瞭，無法添加！");
return;
}else {
rear++;
queue[rear] = n;
}
}
//取出元素
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("隊列為空，無元素可取！");
}else {
front++;
return queue[front];
}
}
//顯示隊列
public void showQueue(){
if (isEmpty()){
System.out.println("隊列為空，沒有元素可顯示！");
return;
}
for (int i : queue){
System.out.println(i);
}
}
//顯示頭數據
public void headQueue(){
if (isEmpty()){
throw new RuntimeException("隊列為空，沒有頭數據！");
}
int i = front;
System.out.println(queue[++i]);
}
}
②測試類
import java.util.Scanner;
/**
* @Author: Yeman
* @Date: 2021-10-11-22:02
* @Description:
*/
public class ArrayQueueTest {
public static void main(String[] args) {
//創建一個隊列
ArrQueue arrQueue = new ArrQueue(3);
//創建一個用戶輸入
Scanner scanner = new Scanner(System.in);
//創建一個功能菜單
char key = ' ';
boolean isShow = true;
while (isShow){
System.out.println("s:顯示隊列");
System.out.println("a:添加數據");
System.out.println("g:取出數據");
System.out.println("h:顯示頭數據");
System.out.println("e:退出程序");
key = scanner.next().charAt(0);
switch (key){
case 's' :
arrQueue.showQueue();
break;
case 'a' :
System.out.println("請輸入一個數：");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g' :
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h' :
try {
arrQueue.headQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e' :
isShow = false;
break;
}
}
System.out.println("程序退出...");
}
}
數組模擬環形隊列（可復用）
對前面的數組模擬隊列的優化，充分利用數組。將數組看做是一個環形的，即取出之後，有位置可以空出來添加。(通過取模的方式來實現即可)
分析說明:
①尾索引的下一個為頭索引時表示隊列滿，即將隊列容量空出一個作為約定。在作判斷隊列滿的時候需要註意(rear+ 1) % maxSize== front [滿]
②rear == front [空]
1、思路如下:
①front 變量的含義調整：front 指向隊列的第一個元素, 也就是說arr[front]就是隊列的第一個元素，front的初始值為0。
②rear 變量的含義調整：rear 指向隊列的最後一個元素的後一個位置，因為希望空出一個空間做為約定，rear的初始值=0。
③當隊列滿時，條件是(rear + 1) % maxSize == front [滿]
④對隊列為空的條件是rear== front[空]
⑤當我們這樣分析，隊列中有效的數據的個數(rear + maxSize - front) % maxSize
⑥我們就可以在原來的隊列上修改得到一個環形隊列
2、代碼實現
①數組實現環形隊列類
class ArrQueue {
private int maxSize; //隊列（數組）最大容量
private int front; //指向隊列頭部，隊列第一個元素的索引
private int rear; //指向隊列尾部，隊列最後一個元素的後一個索引
private int[] queue;
//創造隊列的構造器
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new int[maxSize];
}
//判斷是否滿
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
//判斷是否空
public boolean isEmpty(){
return front == rear;
}
//添加元素
public void addQueue(int n){
if (isFull()){
System.out.println("隊列已經滿瞭，無法添加！");
return;
}else {
queue[rear] = n;
rear = (rear + 1) % maxSize;
}
}
//取出元素
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("隊列為空，無元素可取！");
}else {
int data = queue[front];
front = (front + 1) % maxSize;
return data;
}
}
//顯示隊列
public void showQueue(){
if (isEmpty()){
System.out.println("隊列為空，沒有元素可顯示！");
return;
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d] = %d\n",i % maxSize,queue[i % maxSize]);
}
}
//求當前隊列有效數據個數
public int size(){
return (rear + maxSize - front) % maxSize;
}
//顯示頭數據
public void headQueue(){
if (isEmpty()){
throw new RuntimeException("隊列為空，沒有頭數據！");
}
System.out.println(queue[front]);
}
}
②測試類
import java.util.Scanner;
/**
* @Author: Yeman
* @Date: 2021-10-11-22:02
* @Description:
*/
public class ArrayQueueTest {
public static void main(String[] args) {
//創建一個隊列
ArrQueue arrQueue = new ArrQueue(3); //說明該環形隊列的最大有效數據為2
//創建一個用戶輸入
Scanner scanner = new Scanner(System.in);
//創建一個功能菜單
char key = ' ';
boolean isShow = true;
while (isShow){
System.out.println("s:顯示隊列");
System.out.println("a:添加數據");
System.out.println("g:取出數據");
System.out.println("h:顯示頭數據");
System.out.println("e:退出程序");
key = scanner.next().charAt(0);
switch (key){
case 's' :
arrQueue.showQueue();
break;
case 'a' :
System.out.println("請輸入一個數：");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g' :
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h' :
try {
arrQueue.headQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e' :
isShow = false;
break;
}
}
System.out.println("程序退出...");
}
}
到此這篇關於Java隊列篇之實現數組模擬隊列及可復用環形隊列詳解的文章就介紹到這瞭,更多相關Java 隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！