隊列

使用場景：排隊

隊列介紹

• 隊列是一個有序列表，可以用數(shù)組或是鏈表來實現(xiàn)。
• 遵循先入先出的原則。即：先存入隊列的數(shù)據(jù)，要先取出。后存入的要后取出
• 示意圖：(使用數(shù)組模擬隊列示意圖)

---

數(shù)組模擬隊列

• 隊列本身是有序列表，若使用數(shù)組的結(jié)構(gòu)來存儲隊列的數(shù)據(jù)，則隊列數(shù)組的聲明如下圖, 其中 maxSize 是該隊列的最大容量。
• 因為隊列的輸出、輸入是分別從前后端來處理，因此需要兩個變量 front及 rear分別記錄隊列前后端的下標(biāo)，front 會隨著數(shù)據(jù)輸出而改變，而 rear則是隨著數(shù)據(jù)輸入而改變，如圖所示:

數(shù)組模擬隊列

當(dāng)我們將數(shù)據(jù)存入隊列時稱為”addQueue”，addQueue 的處理需要有兩個步驟：思路分析

將尾指針往后移：rear+1 , 當(dāng)front == rear 【空】

若尾指針 rear 小于隊列的最大下標(biāo) maxSize-1，則將數(shù)據(jù)存入 rear所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。 rear ?== maxSize - 1[隊列滿]

代碼實現(xiàn)

package com.henu.queue;import java.util.Scanner;/*** @author George* @description**/ public class ArrayQueueDemo {public static void main(String[] args) {//測試//創(chuàng)建一個隊列ArrayQueue queue = new ArrayQueue(3);char key;//接收用戶輸入Scanner scanner = new Scanner(System.in);boolean loop = true;while(loop){System.out.println("s(show):顯示隊列");System.out.println("e(exit):退出程序");System.out.println("a(add):添加數(shù)據(jù)");System.out.println("g(get):從隊列取出數(shù)據(jù)");System.out.println("h(head):查看隊列頭的數(shù)據(jù)");key = scanner.next().charAt(0);//接收一個字符switch (key){case 's':queue.showQueue();break;case 'a':System.out.println("輸入一個數(shù)");int value = scanner.nextInt();queue.addQueue(value);break;case 'g':try{int res = queue.getQueue();System.out.printf("取出的數(shù)據(jù)是%d\n",res);}catch (Exception e){System.out.println(e.getMessage());}break;case 'h':try {int res = queue.headQueue();System.out.printf("隊列頭的數(shù)據(jù)是%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':scanner.close();loop = false;break;default:break;}}} }//使用數(shù)組模擬隊列-編寫一個ArrayQueue類 class ArrayQueue{private int maxSize;//表示數(shù)組的最大容量private int front;//隊列頭private int rear;//隊列尾private int[] arr;//該數(shù)據(jù)用于存放數(shù)據(jù)，模擬隊列//創(chuàng)建隊列的構(gòu)造器public ArrayQueue(int arrMaxSize){maxSize = arrMaxSize;arr = new int[maxSize];front = -1;//指向隊列頭部，分析出front是指向隊列頭的前一個位置rear = -1;//指向隊列尾，指向隊列尾的數(shù)據(jù)（即就是隊列的最后一個數(shù)據(jù)）}//判斷隊列是否滿public boolean isFull(){return rear == maxSize-1;}//判斷隊列是否為空public boolean isEmpty(){return rear == front;}//添加數(shù)據(jù)到隊列public void addQueue(int n){if (isFull()) {System.out.println("隊列滿，不能加入數(shù)據(jù)~");return;}rear++;//讓rear后移arr[rear] = n;}//獲取隊列的數(shù)據(jù)，出隊列public int getQueue(){//判斷隊列是否為空if (isEmpty()) {//拋出異常throw new RuntimeException("隊列空，不能取出數(shù)據(jù)");}front++;//front后移return arr[front];}//顯示隊列的所有數(shù)據(jù)public void showQueue(){//遍歷if (isEmpty()) {System.out.println("隊列空的，沒有數(shù)據(jù)~");return;}for (int i = 0; i < arr.length; i++) {System.out.printf("arr[%d]=%d\n",i,arr[i]);}}//顯示隊列的頭數(shù)據(jù)，注意不是取出數(shù)據(jù)public int headQueue(){//判斷if (isEmpty()){throw new RuntimeException("隊列空的，沒有數(shù)據(jù)~");}return arr[front+1];}}

具體測試結(jié)果就不展示了，不過這樣寫有它的缺陷。【可以自己測試測試】

問題發(fā)現(xiàn)并分析：

目前數(shù)組使用一次就不能用，沒有達到復(fù)用的效果。

將這個數(shù)組使用算法，改進成一個環(huán)形的隊列 取模：%

package com.henu.queue;import java.util.Scanner;/*** @author George* @description 環(huán)形隊列**/ public class CircleArrayQueueDemo {public static void main(String[] args) {//測試System.out.println("測試數(shù)據(jù)模擬環(huán)形隊列");//創(chuàng)建一個環(huán)形隊列CircleArray queue = new CircleArray(4);//設(shè)置為4,其隊列的最大有效長度是3char key;//接收用戶輸入Scanner scanner = new Scanner(System.in);boolean loop = true;while(loop){System.out.println("s(show):顯示隊列");System.out.println("e(exit):退出程序");System.out.println("a(add):添加數(shù)據(jù)");System.out.println("g(get):從隊列取出數(shù)據(jù)");System.out.println("h(head):查看隊列頭的數(shù)據(jù)");key = scanner.next().charAt(0);//接收一個字符switch (key){case 's':queue.showQueue();break;case 'a':System.out.println("輸入一個數(shù)");int value = scanner.nextInt();queue.addQueue(value);break;case 'g':try{int res = queue.getQueue();System.out.printf("取出的數(shù)據(jù)是%d\n",res);}catch (Exception e){System.out.println(e.getMessage());}break;case 'h':try {int res = queue.headQueue();System.out.printf("隊列頭的數(shù)據(jù)是%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':scanner.close();loop = false;break;default:break;}}System.out.println("程序退出");} }class CircleArray{private int maxSize;//表示數(shù)組的最大容量//front 變量的含義做一個調(diào)整：front就指向隊列的第一個元素，也就是說arr[front]就是隊列的第一個元素//front的初始值 = 0private int front;//rear 變量的含義做出調(diào)整：rear指向隊列最后一個元素的后一個位置，因為希望空出一個空間作為約定//rear 的初始值 = 0private int rear;//隊列尾private int[] arr;//該數(shù)據(jù)用于存放數(shù)據(jù)，模擬隊列public CircleArray(int arrMaxSize){maxSize = arrMaxSize;arr = new int[maxSize];}//判斷隊列是否為滿public boolean isFull(){return (rear +1)%maxSize == front;}//判斷隊列是否為空public boolean isEmpty(){return rear == front;}//判斷隊列是否為空public void addQueue(int n){//判斷隊列是否滿if (isFull()){System.out.println("隊列滿，不能加入數(shù)據(jù)~");return;}//直接將數(shù)據(jù)加入arr[rear] = n;//將rear后移，這里必須考慮取模rear = (rear+1)%maxSize;}//獲取隊列的數(shù)據(jù)，出隊列public int getQueue(){//判斷隊列是否控if (isEmpty()){//通過拋出異常throw new RuntimeException("隊列空，不能取數(shù)據(jù)~");}//這里需要分析出front是指向隊列的第一個元素//1.先把front對應(yīng)的值保留到一個臨時變量//2.將front后移，考慮取模//3.將臨時保存的變量返回int value = arr[front];front = (front + 1) % maxSize;return value;}//求出當(dāng)前隊列有效數(shù)據(jù)的個數(shù)public int size(){//rear = 2//front = 1//maxSize = 3return (rear+maxSize-front)%maxSize;}//顯示隊列中的所有元素public void showQueue(){//遍歷if (isEmpty()){System.out.println("隊列空的，沒有數(shù)據(jù)~");return;}//思路：從front考試遍歷，遍歷多少個元素//動腦筋for (int i = front; i < front+size(); i++) {System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);}}public int headQueue(){//判斷if (isEmpty()) {throw new RuntimeException("隊列空的，沒有數(shù)據(jù)~");}return arr[front];}}

?

總結(jié)

以上是生活随笔為你收集整理的JAVA数据结构与算法【队列、数组模拟（环形）队列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。