? 作者：小胡_不糊涂
?? 作者主頁：小胡_不糊涂的個人主頁
?? 收錄專欄：淺談數(shù)據(jù)結構
?? 持續(xù)更文，關注博主少走彎路，謝謝大家支持 ??
1.什么是隊列
隊列： 只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(FirstIn First Out) 入隊列：進行插入操作的一端稱為隊尾（Tail/Rear）出隊列：進行刪除操作的一端稱為隊頭（Head/Front）
2. 隊列的使用
在Java中，Queue是個接口，底層是通過鏈表實現(xiàn)的：
| 方法 | 功能 |
|---|---|
| boolean offer(E e) | 入隊列 |
| E poll() | 出隊列 |
| peek() | 獲取隊頭元素 |
| int size() | 獲取隊列中有效元素個數(shù) |
| boolean isEmpty() | 檢測隊列是否為空 |
Queue是個接口，在實例化時必須實例化LinkedList的對象，因為LinkedList實現(xiàn)了Queue接口。
上述方法的實現(xiàn)：
import java.util.LinkedList;
import java.util.Queue;
public class Main {
//方法的實現(xiàn)
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 從隊尾入隊列
System.out.println(q.size());
System.out.println(q.peek()); // 獲取隊頭元素
q.poll();
System.out.println(q.poll()); // 從隊頭出隊列，并將刪除的元素返回
if(q.isEmpty()){
System.out.println("隊列空");
}else{
System.out.println(q.size());
}
}
}
3. 隊列的模擬實現(xiàn)
我們知道隊列中既然可以存儲元素，那底層肯定要有能夠保存元素的空間，通過線性表可以了解到常見的空間類型有兩種：順序結構和鏈式結構。
模擬實現(xiàn)隊列：
public class MyQueue {
//雙向鏈表節(jié)點
static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//隊頭
public ListNode last;//隊尾
public int usedSize;//隊列元素個數(shù)
// 入隊列---向雙向鏈表位置插入新節(jié)點
public boolean offer(int val) {
ListNode node = new ListNode(val);
if(head == null) {
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = last.next;
}
usedSize++;
return true;
}
// 出隊列---將雙向鏈表第一個節(jié)點刪除掉
// 1. 隊列為空
// 2. 隊列中只有一個元素----鏈表中只有一個節(jié)點---直接刪除
// 3. 隊列中有多個元素---鏈表中有多個節(jié)點----將第一個節(jié)點刪除
public int poll() {
if(head == null) {
return -1;
}
int retVal = head.val;
if(head.next == null) {
head = null;
last = null;
return retVal;
}
head = head.next;
head.prev = null;//第一個節(jié)點刪除
usedSize--;
return retVal;
}
// 獲取隊頭元素---獲取鏈表中第一個節(jié)點的值域
public int peek() {
if(head == null) {
return -1;
}
return head.val;
}
public boolean empty() {
return head == null;
}
public int size() {
return usedSize;
4. 循環(huán)隊列
循環(huán)隊列顧名思義就是首位相連的隊列，自然界中的生產者消費者分解者模型可以使用循環(huán)隊列來描述。而環(huán)形隊列通常使用數(shù)組實現(xiàn)。
數(shù)組下標循環(huán)的小技巧
- 下標最后再往后(offset 小于 array.length): index = (index + offset) % array.length
- 下標最前再往前(offset 小于 array.length): index = (index + array.length - offset) %array.length
如何區(qū)分空與滿？
- 通過添加 size 屬性記錄
- 保留一個位置
- 使用標記
循環(huán)隊列的實現(xiàn)：
class MyCircularQueue {
public int[] elem;
public int front;//隊頭
public int rear;//隊尾
public MyCircularQueue(int k) {
elem = new int[k+1];
}
//隊尾入隊
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[rear] = value;
rear = (rear+1) % elem.length;
return true;
}
//隊頭出隊
public boolean deQueue() {
if(isEmpty()) {
return false;
}
front = (front+1) % elem.length;
return true;
}
//得到隊頭元素
public int Front() {
if(isEmpty()) {
return -1;
}
return elem[front];
}
//得到隊尾元素
public int Rear() {
if(isEmpty()) {
return -1;
}
int index = (rear == 0) ? elem.length-1 : rear-1;
return elem[index];
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear+1)%elem.length == front;
}
}
5. 雙端隊列(Deque)
**雙端隊列（deque）**是指允許兩端都可以進行入隊和出隊操作的隊列。
Deque是一個接口，使用時必須創(chuàng)建LinkedList的對象:文章來源：http://www.zghlxwxcb.cn/news/detail-713322.html
在實際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口:文章來源地址http://www.zghlxwxcb.cn/news/detail-713322.html
Deque<Integer> stack = new ArrayDeque<>();//雙端隊列的線性實現(xiàn)
Deque<Integer> queue = new LinkedList<>();//雙端隊列的鏈式實現(xiàn)
到了這里，關于【數(shù)據(jù)結構】隊列-Queue的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
