Java三十篇：初識隊列
以下的都是我自己理解，不對的觀點請及時聯(lián)系我
1.什么是隊列？
隊列是數(shù)據(jù)結構中比較重要的一種類型（是一種數(shù)據(jù)結構），它支持 FIFO，尾部添加、頭部刪除（先進隊列的元素先出隊列），跟我們生活中的排隊類似。
2.什么情況下使用隊列？
一般情況下，如果是對一些及時消息的處理，并且處理時間很短的情況下是不需要隊列的，直接阻塞式的方法調用就可以了。但是如果在消息處理的時候特別費時間，這個時候如果有新消息來了，就只能處于阻塞狀態(tài)，造成用戶等待。這個時候便需要引入隊列了。當接收到消息后，先把消息房貸隊列中，然后再用行的線程進行處理，這個時候就不會有消息阻塞了。
3.隊列介紹：
隊列有兩種：① 單隊列 ：就是常見的隊列，每次添加元素時，都是添加對隊尾。② 循環(huán)隊列
4.隊列Queue
add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常 remove 移除并返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常 element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常 offer 添加一個元素并返回true 如果隊列已滿，則返回false poll 移除并返問隊列頭部的元素 如果隊列為空，則返回null peek 返回隊列頭部的元素 如果隊列為空，則返回null put 添加一個元素 如果隊列滿，則阻塞 take 移除并返回隊列頭部的元素 如果隊列為空，則阻塞
java集合中Queue繼承自Collection接口，Deque，Linkedlist，PriorityQueue，BlockingQueue等類都實現(xiàn)了它
Queue 用來存放 等待處理元素 的集合，這種場景一般用于緩沖、并發(fā)訪問。
除了繼承 Collection 接口的一些方法，Queue 還添加了額外的 添加、刪除、查詢操作。
隊列的使用場景
銀行排隊的案例：
隊列介紹
隊列是一個有序列表， 可以用數(shù)組或是鏈表來實現(xiàn)。
遵循先入先出的原則， 即：先存入隊列的數(shù)據(jù)， 要先取出，后存入的要后取出
示意圖：(使用數(shù)組模擬隊列示意圖)
數(shù)組模擬隊列
思路分析
maxSize ：隊列容量（數(shù)組的長度）
arr ：模擬隊列的數(shù)組
front ：指向隊列頭部元素的前一個元素，初始值為 -1
rear ：指向隊列尾部元素，初始值為 -1
基本操作
隊列判空：front == rear
隊列判滿：rear == (maxSize - 1) ，即 rear 是否已經(jīng)指向了數(shù)組的最后一個位置
隊列元素個數(shù)：rear - front
隊列入隊：隊列不滿才能入隊，arr[++rear] = value
隊列出隊：隊列不空才能出隊，return arr[front++]
代碼實現(xiàn)
//隊列的定義
// 使用數(shù)組模擬隊列-編寫一個ArrayQueue類
class ArrayQueue {
privateint maxSize; // 表示數(shù)組的最大容量
privateint front; // 隊列頭
privateint rear; // 隊列尾
privateint[] arr; // 該數(shù)據(jù)用于存放數(shù)據(jù), 模擬隊列
// 創(chuàng)建隊列的構造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = newint[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()) {
// 通過拋出異常
thrownew RuntimeException("隊列空，不能取數(shù)據(jù)");
}
front++; // front后移
return arr[front];
}
// 顯示隊列的所有數(shù)據(jù)
public void showQueue() {
// 遍歷
if (isEmpty()) {
System.out.println("隊列空的，沒有數(shù)據(jù)~~");
return;
}
for (int i = front + 1; i <= rear; i++) {
// Java 中也能用占位符誒
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// 顯示隊列的頭數(shù)據(jù)， 注意不是取出數(shù)據(jù)
public int headQueue() {
// 判斷
if (isEmpty()) {
thrownew RuntimeException("隊列空的，沒有數(shù)據(jù)~~");
}
return arr[front + 1];
}
}
測試代碼
publicclass 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ù)");
System.out.println();
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': // 取出數(shù)據(jù)
try {
int res = queue.getQueue();
System.out.printf("取出的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case'h': // 查看隊列頭的數(shù)據(jù)
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("程序退出~~");
}
}
程序運行結果
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
s
隊列空的，沒有數(shù)據(jù)~~
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
1
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
2
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
s
arr[0]=1
arr[1]=2
arr[2]=3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
4
隊列滿，不能加入數(shù)據(jù)~
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
取出的數(shù)據(jù)是1
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
取出的數(shù)據(jù)是2
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
取出的數(shù)據(jù)是3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
隊列空，不能取數(shù)據(jù)
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
目前數(shù)組使用一次就不能用， 沒有達到復用的效果，造成內存空間的浪費
將這個數(shù)組使用算法， 改進成一個環(huán)形的隊列（取模：%）
解決問題如下：
數(shù)組模擬環(huán)形隊列
思路分析
對前面的隊列進行優(yōu)化，改造為環(huán)形隊列（通過取模實現(xiàn)）
maxSize ：隊列容量（數(shù)組的長度）
arr ：模擬隊列的數(shù)組
front ：指向隊列頭部元素，初始值為 0
rear ：指向隊列尾部元素的后一個元素，初始值為 0
代碼實現(xiàn)
class CircleArray {
privateint maxSize; // 表示數(shù)組的最大容量
// front 變量的含義做一個調整：front 就指向隊列的第一個元素, 也就是說 arr[front] 就是隊列的第一個元素
// front 的初始值 = 0
privateint front;
// rear 變量的含義做一個調整：rear 指向隊列的最后一個元素的后一個位置. 因為希望空出一個空間做為約定.
// rear 的初始值 = 0
privateint rear; // 隊列尾
privateint[] arr; // 該數(shù)據(jù)用于存放數(shù)據(jù), 模擬隊列
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = newint[maxSize];
}
// 判斷隊列是否滿
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判斷隊列是否為空
public boolean isEmpty() {
return rear == front;
}
// 添加數(shù)據(jù)到隊列
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()) {
// 通過拋出異常
thrownew RuntimeException("隊列空，不能取數(shù)據(jù)");
}
// 這里需要分析出 front是指向隊列的第一個元素
// 1. 先把 front 對應的值保留到一個臨時變量
// 2. 將 front 后移, 考慮取模
// 3. 將臨時保存的變量返回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// 顯示隊列的所有數(shù)據(jù)
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]);
}
}
// 求出當前隊列有效數(shù)據(jù)的個數(shù)
public int size() {
// rear = 2
// front = 1
// maxSize = 3
return (rear + maxSize - front) % maxSize;
}
// 顯示隊列的頭數(shù)據(jù)， 注意不是取出數(shù)據(jù)
public int headQueue() {
// 判斷
if (isEmpty()) {
thrownew RuntimeException("隊列空的，沒有數(shù)據(jù)~~");
}
return arr[front];
}
}
測試代碼
publicclass CircleArrayQueueDemo {
public static void main(String[] args) {
// 測試一把
System.out.println("測試數(shù)組模擬環(huán)形隊列的案例~~~");
// 創(chuàng)建一個環(huán)形隊列
CircleArray queue = new CircleArray(4); // 說明設置4, 其隊列的有效數(shù)據(jù)最大是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ù)");
System.out.println();
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': // 取出數(shù)據(jù)
try {
int res = queue.getQueue();
System.out.printf("取出的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case'h': // 查看隊列頭的數(shù)據(jù)
try {
int res = queue.headQueue();
System.out.printf("隊列頭的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
程序運行結果
測試數(shù)組模擬環(huán)形隊列的案例~~~
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
1
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
2
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
s
arr[0]=1
arr[1]=2
arr[2]=3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
a
輸出一個數(shù)
4
隊列滿，不能加入數(shù)據(jù)~
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
取出的數(shù)據(jù)是1
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
取出的數(shù)據(jù)是2
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
s
arr[2]=3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
取出的數(shù)據(jù)是3
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
g
隊列空，不能取數(shù)據(jù)
s(show): 顯示隊列
e(exit): 退出程序
a(add): 添加數(shù)據(jù)到隊列
g(get): 從隊列取出數(shù)據(jù)
h(head): 查看隊列頭的數(shù)據(jù)
總結：
1、隊列有兩種：① 單隊列 ：就是常見的隊列，每次添加元素時，都是添加對隊尾。② 循環(huán)隊列（環(huán)形隊列）
2、遵循先入先出的原則， 即：先存入隊列的數(shù)據(jù)， 要先取出，后存入的要后取出
加強自身學習，提高自身素質。 積累工作經(jīng)驗，改進工作方法，向周圍同志學習，注重別人優(yōu)點，學習他們處理問題的方法，查找不足，提高自己。
