Java隊列的數組實作
文章目錄
- 前言
- 一、隊列介紹
- 二、數組模拟隊列
-
- 1.編寫 隊列 的類
- 2.判斷隊列是否滿
- 3.判斷隊列是否空
- 4.入隊列
- 5.出隊列
- 6.周遊隊列
- 三、數組模拟環形隊列
-
- 1.調整思路如下：
- 2. CircleArray的實作：
- 3.添加資料（入隊列）
- 4.擷取資料（出隊列）
- 5.得到有效資料個數🔺
- 6.隊列是否為空
- 7.隊列是否滿
- 8.周遊環形隊列
- 四、總結
-
- 測試代碼
前言
生活中很多情況都是先來後到, 最直接的就是銀行的業務了吧, 先來的先處理, 隊列可以看成是順序的結構, 我們排隊來一個新人是排在這一隊的尾部, 每次處理頭部的一個人, 隊列可以用數組 和連結清單來實作
一、隊列介紹
隊列本身是有序的清單, 若使用數組的結構來存儲隊列的資料, 則隊列數組中的聲明如下面所示( 我們用maxSize來代表隊列最大容量):
因為隊列的輸入、輸出分别從前後端來進行處理的。是以需要兩個變量（相當于指針的作用）分别來記錄隊列的 隊首 和 隊尾 的下标。顯然，front會随資料的輸出發生變化（在頭部出隊列：排隊的時候在前面的先走）；rear是在資料輸入的時候發生變化（新的人過來，排在隊尾），具體如下圖所示（将兩個指針都初始化為-1）：
二、數組模拟隊列
1.編寫 隊列 的類
代碼如下：
class ArrayQueue{
private int maxSize;//隊列容量
private int front; //隊列頭
private int rear; //隊列尾
private int[] arr; //存放資料，模拟隊列
//構造器：
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1; //指向對象頭部,指向隊列頭的前一個位置
rear = -1; //指向隊列的尾部,指向隊列尾部具體的資料(就是隊列最後一個資料)
}
}
2.判斷隊列是否滿
當rear指針等于maxSize - 1的時候就滿了，代碼如下：
//判斷隊列是否滿
public boolean isFull(){
return rear == maxSize - 1;//上面已經提到
}
3.判斷隊列是否空
當rear指針等于front即為空（和排隊時候對比即可），代碼如下：
//判斷隊列是否為空
public boolean isEmpty(){
return rear == front;
}
4.入隊列
當我們将資料存入隊列的時候，定義方法"addQueue()",處理分為兩個步驟即可：
1.調用isFull()方法判斷隊列是否滿；
2.若隊列沒有滿，可以添加資料：
2.1 尾指針rear後移：即rear = rear + 1；（指針指向空位置給新人）
2.2 将資料存入rear所指的數組位置中即可，
否則，不能加入資料（提醒使用者），傳回即可
代碼如下：
// 添加資料
public void addData(int data){
if(isFull()){
System.out.println("隊列滿,加入資料失敗...");
return;
}
rear++;//排隊有人過來了，隊尾指針後移（到空位置）
arr[rear] = data;//
}
5.出隊列
當我們出隊列的時候，處理分為以下兩個步驟即可：
1.調用isEmpty()方法判斷隊列是否空；
2.若隊列不為空，可以出隊列（還有人在排隊）：
2.2 将頭指針front後移（指向的第一個顧客前一個位置），找到第一個顧客
2.3 将arr[front]出列即可（對顧客進行服務）
否則，不能出隊列（這裡我們采用抛出異常的方法（也可列印提示））
抛出自定義的運作時異常，不用再進行return;(基礎知識點，需要注意下)
代碼如下：
public int getData(){
if(isEmpty()){
throw new RuntimeException("隊列為空,不能取資料");
}
front++;//front後移
return arr[front];
}
6.周遊隊列
當我們周遊隊列的時候，分為以下步驟：
1.調用isEmpty()方法判斷隊列是否空；
2.若隊列不為空，用 foreach 周遊即可：
否則，提示隊列為空即可；
代碼如下：
public void showData(){
//周遊
if(isEmpty()){
System.out.println("隊列為空,沒有資料");
return;
}
for(int i = 0 ; i < arr.length ; i++){
System.out.printf("a[%d] = %d\n" , i , arr[i]);
}
}
三、數組模拟環形隊列
對上面的數組進行優化，充分利用數組：将其看作一個環形的(我們在此通過取模的方式完成) ：
1.調整思路如下：
1.front變量的含義做一個改變：front就是指向隊列第一個元素。
也就是說，現在arr[front]就是隊列的第一個元素；front的初始值 = 0；
2.rear變量的含義做出調整：rear就是指向的隊列的元素的後一個位置。
因為希望空出一個空間來做一個約定（可以不預留）。rear初始值 = 0；
3.當隊列滿的時候，條件是（rear + 1）% maxSize == front
4.隊列為空的時候，rear == front
5.隊列中有效的資料個數為：(rear + maxSize - front) % maxSize
2. CircleArray的實作：
class CircleArray{
private int maxSize; //表示數組最大容量
private int front; //隊列首部
private int rear; //隊列尾部
private int[] arr; //該數組用于存放資料,模拟隊列
// 建立隊列的構造器
public CircleArray (int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
front = 0;//初始化為0
rear = 0;//初始化為0
}
}
3.添加資料（入隊列）
public void addData(int data){
if(isFull()){
System.out.println("隊列滿,不能加入資料");
return;
}
arr[rear] = data;
//後移資料
rear = (rear + 1) % maxSize;
}
4.擷取資料（出隊列）
public int getData(){
if(isEmpty()){
throw new RuntimeException("隊列為空,不能取資料");
}
//這裡考慮front指向的隊列第一個元素
//1.先把front對應的值儲存到一個臨時變量
//2.将front後移,考慮取模
//3.将臨時變量的值傳回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
5.得到有效資料個數🔺
public int size(){
return (rear + maxSize - front) % maxSize;
}
6.隊列是否為空
public boolean isEmpty(){
return rear == front;
}
7.隊列是否滿
// 判斷隊列是否滿
public boolean isFull(){
return ((rear + 1) % maxSize == front);
}
8.周遊環形隊列
// 顯示隊列的所有資料
public void showData(){
//周遊
if(isEmpty()){
System.out.println("隊列為空,沒有資料");
return;
}
for(int i = front ; i < front + size() ; i++){
//這裡需要注意一下：
System.out.printf("a[%d] = %d\n" , i % maxSize , arr[i % maxSize]);
}
}
四、總結
1. 對于普通的隊列：front指向的是第一個元素的前一個位置；
2. 對于普通的隊列：rear指向的是最後一個資料本身位置；
3. 對于環形隊列：reae指向最後一個資料的後一個位置；
4. 對于環形隊列：front指向的就是第一個資料的位置；
5. 對于環形隊列(front 和 rear初始為0)：
需要注意的是關于隊列中元素個數的計算方式；
測試代碼
public class ArrayQueueDemo {
public static void main(String[] args) {
//測試
ArrayQueue queue = new ArrayQueue(3);
char key = ' ';//接收使用者輸入;
Scanner s = new Scanner(System.in);
boolean loop = true;
while(loop){
System.out.println("s(show):顯示隊列");
System.out.println("e(exit):結束程式");
System.out.println("a(add):添加隊列");
System.out.println("g(get):隊列中取資料");
System.out.println("h(head):檢視隊列頭部資料");
key = s.next().charAt(0);
switch (key){
case 's':
queue.showData();
break;
case 'a':
System.out.println("請輸入添加的數字:");
int data = s.nextInt();
queue.addData(data);
break;
case 'g':
try {
int res = queue.getData();
System.out.println("去除的資料是:" + res);
}catch(Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = queue.headData();
System.out.println("隊列頭的資料是" + head);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
default:
System.out.println("操作不存在,請重新輸入:");
break;
}
}
}
}
class ArrayQueue{
private int maxSize; //表示數組最大容量
private int front; //隊列首部
private int rear; //隊列尾部
private int[] arr; //該數組用于存放資料,模拟隊列
// 建立隊列的構造器
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1; //指向對象頭部,指向隊列頭的前一個位置
rear = -1; //指向隊列的尾部,指向隊列尾部具體的資料(就是隊列最後一個資料)
}
// 判斷隊列是否滿
public boolean isFull(){
return rear == maxSize - 1;
}
// 判斷隊列是否為空
public boolean isEmpty(){
return rear == front;
}
// 添加資料
public void addData(int data){
if(isFull()){
System.out.println("隊列滿,不能加入資料");
}
rear++;
arr[rear] = data;
}
// 擷取資料
public int getData(){
// 判斷是否為空
if(isEmpty()){
throw new RuntimeException("隊列為空,不能取資料");
}
front++;
return arr[front];
}
// 顯示隊列的所有資料
public void showData(){
//周遊
if(isEmpty()){
System.out.println("隊列為空,沒有資料");
return;
}
for(int i = 0 ; i < arr.length ; i++){
System.out.printf("a[%d] = %d\n" , i , arr[i]);
}
}
// 顯示頭部資料
public int headData(){
// 判斷
if(isEmpty()){
throw new RuntimeException("隊列為空,沒有資料...");
}
return arr[front + 1];
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)