一：隊列

1.1 隊列的概念

• 隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出的特點。
• 入隊列：進行插入操作的一端稱為隊尾 。
• 出隊列：進行刪除操作的一端稱為隊頭。

例如：比如生活中排隊買東西，先排隊的先購買

1.2 隊列的介紹

1. 隊列是一個有序列表，可以用數組或是鏈表來實現。
2. 遵循先入先出的原則。即：先存入隊列的數據，要先取出。后存入的要后取出

1.3 隊列示意圖

二：數組模擬隊列

2.1 介紹

• 隊列本身是有序列表，若使用數組的結構來存儲隊列的數據，則隊列數組的聲明如下圖, 其中 maxSize 是該隊列的最大容量。

• 因為隊列的輸出、輸入是分別從前后端來處理，因此需要兩個變量 front及 rear分別記錄隊列前后端的下標，front 會隨著數據輸出而改變，而 rear則是隨著數據輸入而改變，如圖所示:

• 

2.2 思路

當我們將數據存入隊列時稱為”addQueue”，addQueue 的處理需要有兩個步驟：思路分析

1. 將尾指針往后移：rear+1 , 當front == rear 【空】
2. 若尾指針 rear 小于隊列的最大下標 maxSize-1，則將數據存入 rear所指的數組元素中，否則無法存入數據。 rear == maxSize - 1[隊列滿]

注：
rear 是隊列最后[含]
front 是隊列最前元素[不含]

2.3 代碼實現

2.3.1 定義隊列基本信息

 /*** 最大容量*/private int maxSize;/*** 隊列頭*/private int front;/*** 隊列尾*/private int rear;/*** 該數組用于存放數據*/private int[] arr;

2.3.2 初始化隊列

/*** 初始化隊列構造器** @param arrMaxSize*/public ArrayQueue(int arrMaxSize) {maxSize = arrMaxSize;arr = new int[arrMaxSize];//指向隊列頭部的前一個位置，不包含頭部front = -1;//指向隊列尾部具體數據rear = -1;}

2.3.3 判斷隊列是否滿，是否為空

/*** 判斷隊列是否滿** @return*/public boolean isFull() {return rear == maxSize - 1;}/*** 判斷隊列是否為空** @return*/public boolean isEmpty() {return front == rear;}

2.3.4 添加數據到隊列

public void addQueue(int n) {//判斷隊列是否滿，滿了就無法添加數據if (isFull()) {System.out.println("隊列滿了，無法添加數據");return;}//添加數據讓rear后移rear++;arr[rear] = n;}

2.3.5 獲取隊列數據，出隊列

  /*** 獲取隊列數據，出隊列** @return*/public int getQueue() {//判斷隊列是否為空if (isEmpty()) {throw new RuntimeException("隊列為空，無法取出數據");}front++;return arr[front];}

2.3.6 顯示隊列所有數據

   /*** 顯示隊列所有數據*/public void showQueue() {//判斷隊列是否為空if (isEmpty()) {System.out.println("隊列為空，沒有數據");}for (int i = 0; i < arr.length; i++) {System.out.printf("arr[%d]=%d\n", i, arr[i]);}}

2.3.7 顯示隊列頭數據

 /*** 顯示隊列頭數據** @return*/public int headQueue() {//判斷隊列是否為空if (isEmpty()) {throw new RuntimeException("隊列為空，沒有數據");}return arr[front + 1];}

2.3.8 源碼奉上

/*** 隊列頭部輸出數據，尾部輸入數據*/
class ArrayQueue {/*** 最大容量*/private int maxSize;/*** 隊列頭*/private int front;/*** 隊列尾*/private int rear;/*** 該數組用于存放數據*/private int[] arr;/*** 初始化隊列構造器** @param arrMaxSize*/public ArrayQueue(int arrMaxSize) {maxSize = arrMaxSize;arr = new int[arrMaxSize];//指向隊列頭部的前一個位置，不包含頭部front = -1;//指向隊列尾部具體數據rear = -1;}/*** 判斷隊列是否滿** @return*/public boolean isFull() {return rear == maxSize - 1;}/*** 判斷隊列是否為空** @return*/public boolean isEmpty() {return front == rear;}/*** 添加數據到隊列*/public void addQueue(int n) {//判斷隊列是否滿，滿了就無法添加數據if (isFull()) {System.out.println("隊列滿了，無法添加數據");return;}//添加數據讓rear后移rear++;arr[rear] = n;}/*** 獲取隊列數據，出隊列** @return*/public int getQueue() {//判斷隊列是否為空if (isEmpty()) {throw new RuntimeException("隊列為空，無法取出數據");}front++;return arr[front];}/*** 顯示隊列所有數據*/public void showQueue() {//判斷隊列是否為空if (isEmpty()) {System.out.println("隊列為空，沒有數據");}for (int i = 0; i < arr.length; i++) {System.out.printf("arr[%d]=%d\n", i, arr[i]);}}/*** 顯示隊列頭數據** @return*/public int headQueue() {//判斷隊列是否為空if (isEmpty()) {throw new RuntimeException("隊列為空，沒有數據");}return arr[front + 1];}}

2.4 測試ArrayQueue

public class ArrayQueueDemo {public static void main(String[] args) {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):添加數據隊列");System.out.println("g(get):取出數據隊列");System.out.println("h(head):查看頭隊列數據");key = scanner.next().charAt(0);switch (key) {case 's':queue.showQueue();break;case 'a':System.out.println("輸入一個數字");int value = scanner.nextInt();queue.addQueue(value);break;case 'g':try {int res = queue.getQueue();System.out.printf("取出的數據為%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'h':try {int res = queue.headQueue();System.out.printf("隊列頭數據為%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}case 'e':scanner.close();loop = false;default:break;}}System.out.println("程序退出");}}

2.5 問題分析并優化

問題：目前數組使用一次就無法使用，沒有達到復用的效果
優化：將數組改成環形隊列，進行取模

三：數組模擬環形隊列

3.1 分析

對前面的數組模擬隊列的優化，充分利用數組。因此將數組看做是一個環形的。(通過取模的方式來實現即可)

3.2 思路

1. front的含義做出如下調整：front就指向隊列的第一個元素，即arr[front]就是隊列的第一個元素。
2. rear的含義做出如下調整：rear指向隊列最后一個元素的后一個位置。空出一個空間做約定。
3. 隊列滿的條件：（rear+1）%maxSize = front;
4. 隊列空的條件：rear == front;
5. front和rear的初始值都為0；
6. 隊列中有效數據個數：（rear + maxSize - front）% maxSize;

3.3 代碼實現

package com.sysg.dataStructuresAndAlgorithms.queue;import java.util.Scanner;public class CircleArrayQueueDemo {public static void main(String[] args) {//長度為4，有效長度為3，有一個預留的空間CircleArrayQueue queue = new CircleArrayQueue(4);//接收用戶輸入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):添加數據隊列");System.out.println("g(get):取出數據隊列");System.out.println("h(head):查看頭隊列數據");key = scanner.next().charAt(0);switch (key) {case 's':queue.showQueue();break;case 'a':System.out.println("輸入一個數字");int value = scanner.nextInt();queue.addQueue(value);break;case 'g':try {int res = queue.getQueue();System.out.printf("取出的數據為%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'h':try {int res = queue.headQueue();System.out.printf("隊列頭數據為%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}case 'e':scanner.close();loop = false;default:break;}}System.out.println("程序退出");}
}class CircleArrayQueue {/*** 最大容量*/private int maxSize;/*** 隊列頭* 1. front的含義做出如下調整：front就指向隊列的第一個元素，即arr[front]就是隊列的第一個元素。*/private int front;/*** 隊列尾* 2. rear的含義做出如下調整：rear指向隊列最后一個元素的后一個位置。空出一個空間做約定。*/private int rear;/*** 該數組用于存放數據*/private int[] arr;/*** 初始化隊列構造器** @param arrMaxSize*/public CircleArrayQueue(int arrMaxSize) {maxSize = arrMaxSize;arr = new int[arrMaxSize];front = 0;rear = 0;}/*** 判斷隊列是否滿** @return*/public boolean isFull() {//例：front = 1,rear = 5,maxSize = 5,此時隊列就滿了return (rear + 1) % maxSize == front;}/*** 判斷隊列是否為空** @return*/public boolean isEmpty() {return front == rear;}/*** 添加數據到隊列*/public void addQueue(int n) {//判斷隊列是否滿，滿了就無法添加數據if (isFull()) {System.out.println("隊列滿了，無法添加數據");return;}//直接將數據加入arr[rear] = n;//將rear后移，這里必須考慮取模rear = (rear + 1) % maxSize;}/*** 獲取隊列數據，出隊列** @return*/public int getQueue() {//判斷隊列是否為空if (isEmpty()) {throw new RuntimeException("隊列為空，無法取出數據");}//這里需要分析出front是指向隊列的第一個元素//1.先把front的值保存到一個臨時的變量//2.將front后移,考慮取模//3.將臨時變量保存int value = arr[front];front = (front + 1) % maxSize;return value;}/*** 顯示隊列所有數據*/public void showQueue() {//判斷隊列是否為空if (isEmpty()) {System.out.println("隊列為空，沒有數據");}//從front開始遍歷，遍歷多少個元素for (int i = front; i < front + getSize(); i++) {System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);}}/*** 獲取有效數據大小* @return*/public int getSize() {return (rear + maxSize - front) % maxSize;}/*** 顯示隊列頭數據** @return*/public int headQueue() {//判斷隊列是否為空if (isEmpty()) {throw new RuntimeException("隊列為空，沒有數據");}return arr[front];}}