java 数据队列_Java 数据结构 - 队列
Java 數據結構 - 隊列
我們今天要講的數據結構是隊列，比如 Java 線程池任務就是隊列實現的。
1. 什么是隊列
和棧一樣，隊列也是一種操作受限的線性結構。使用隊列時，在一端插入元素，而在另一端刪除元素。
1.1 隊列的主要特性
隊列中的數據元素遵守 "先進先出"(First In First Out)的原則，簡稱 FIFO 結構。
限定只能在隊列一端插入，而在另一端進行刪除操作。
1.2 隊列的相關概念
入隊(enqueue)：隊列的插入操作。
出隊(dequeue)：隊列的刪除操作。
2. 復雜度分析
和棧一樣，隊列也有兩種實現方案，我們簡單分析一下這兩種隊列的復雜度：
動態隊列(鏈表)：也叫鏈式隊列。其插入、刪除時間復雜度都是 O(1)。
靜態隊列(數組)：也叫順序隊列。當隊列隊尾指針移到最后時，此時有兩種操作：一是進行簡單的數據搬移，二是進行隊列循環。
關于隊列的實現，我們只實現如下的基本操作。
public interface Queue {
Queue enqueue(Object obj); // 入隊
Object dequeue(); // 出隊
int size(); // 元素個數
}
2.1 鏈式隊列
鏈式隊列的實現非常簡單，其插入和刪除的時間復雜度都是 O(1)。為了簡化代碼的實現，我們引入哨兵結點。如下圖所示，head 頭結點是哨兵結點，不保存任何數據，從 head.next 開始保存數據，tail 結點指向最后一個元素結點。鏈表隊列頭結點和尾結點說明：
頭結點：head 結點為哨兵結點，不保存任何數據，數據從第二個結點開始。
尾結點：tail 結點指向最后一個數據結點。
根據上圖，我們可以輕松實現一個鏈表組成的隊列，代碼也很簡單。
public class LinkedQueue implements Queue {
private Node head;
private Node tail;
private int size;
public LinkedQueue() {
head = new Node(null, null);
tail = head;
}
@Override
public Queue enqueue(Object obj) {
tail.next = new Node(obj, null);
tail = tail.next;
size++;
return this;
}
@Override
public Object dequeue() {
Node next = head.next;
if (next == null) {
return null;
}
head = head.next;
size--;
return next.item;
}
@Override
public int size() {
return size;
}
public static class Node {
private Object item;
private Node next;
public Node(Object item, Node next) {
this.item = item;
this.next = next;
}
}
}
2.2 順序隊列
如果是數組實現的隊列，則比鏈表要復雜一些，當尾結點指向數組的最后一個位置時，沒有剩余的空間存放數據時，此時該如何處理？通過我們有兩種解決方案：
數據搬移：將 head ~ tail 結點的數據搬移到從 0 結點開始。
循環隊列：tail 結點從 0 開始循環使用，不用搬移數據。
我們先看一下循環隊列
如上圖所示，當尾結點指向數組最后一個位置，當 tail 指向數組最后位置時，觸發數據搬移，將 head ~ tail 結點的數據搬移到從 0 結點開始。數組隊列頭結點和尾結點說明：
頭結點：head 結點指向第一個數據結點。當 head == tail 時說明隊列處于隊空狀態，直接返回 null。
尾結點：tail 結點指向最后一個數據之后的空結點。當 tail == capcity 時說明隊列處于隊滿狀態，需要擴容或進行數據搬移。
根據上述理論代碼實現如下：
public class ArrayQueue implements Queue {
private Object[] array;
private int capcity;
// head指向第一個數據結點的位置，tail指向最后一個數據結點之后的位置
private int head;
private int tail;
public ArrayQueue() {
this.capcity = 1024;
this.array = new Object[this.capcity];
}
public ArrayQueue(int capcity) {
this.capcity = capcity;
this.array = new Object[capcity];
}
/**
* tail 指向數組最后位置時，需要觸發擴容或數組搬移
* 1. head!=0 說明數組還有剩余的空間，將 head 搬運到隊列 array[0]
* 2. head==0 說明數組沒有剩余的空間，擴容
*/
@Override
public Queue enqueue(Object obj) {
if (tail == capcity) {
if (head == 0) {
resize();
} else {
rewind();
}
}
array[tail++] = obj;
return this;
}
@Override
public Object dequeue() {
if (head == tail) {
return null;
}
Object obj = array[head];
array[head] = null;
head++;
return obj;
}
// 將 head 搬運到隊列 array[0]
private void rewind() {
for (int i = head; i < tail; i++) {
array[i - head] = array[i];
array[i] = null;
}
tail -= head;
head = 0;
}
// 擴容
private void resize() {
int oldCapcity = this.capcity;
int newCapcity = this.capcity * 2;
Object[] newArray = new Object[newCapcity];
for (int i = 0; i < oldCapcity; i++) {
newArray[i] = array[i];
}
this.capcity = newCapcity;
this.array = newArray;
}
@Override
public int size() {
return tail - head;
}
}
說明： 數組隊列出隊的時間復雜度始終是 O(1)。但入隊時要分為三種情況：
有空間：大多數情況，也是最好時間復雜度 O(1)。
沒有空間需要數據搬移：執行 n 后觸發一次數據搬移，最壞時間復雜度 O(n)。
沒有空間需要擴容：執行 n 后觸發一次數據搬移，最壞時間復雜度 O(n)。
如果采用攤還分析法，最好時間復雜度 O(1)，最壞時間復雜度 O(n)，攤還時間復雜度為 O(1)。雖然，平均時間復雜度還是 O(1)，但我們能不能不進行數據搬移，直接循環使用數組呢？
2.3 循環隊列
循環隊列是一種非常高效的隊列，我們需要重點掌握它，要能輕松寫出無 BUG 的循環隊列。
數組隊列頭結點和尾結點說明：
頭結點：head 結點指向第一個數據結點。當 head == tail 時說明隊列處于隊空狀態，直接返回 null。否則在元素出隊后，需要重新計算 head 值。
尾結點：tail 結點指向最后一個數據之后的空結點。每次插入元素后重新計算 tail 值，當 tail == head 時說明隊列處于隊滿狀態，需要擴容。
元素位置：對數組長度取模 (tail + 1) % length ，所以這種數據為了提高效率，都要求數組長度為 2^n，通過位運算取模 (tail + 1) & (length - 1)。
public class ArrayCircularQueue implements Queue {
private Object[] array;
private int capcity;
// 頭結點指向
private int head;
private int tail;
public ArrayCircularQueue() {
this.capcity = 1024;
this.array = new Object[this.capcity];
}
public ArrayCircularQueue(int capcity) {
this.capcity = capcity;
this.array = new Object[capcity];
}
@Override
public Queue enqueue(Object obj) {
array[tail] = obj;
if ((tail = (tail + 1) % capcity) == head) {
resize();
}
return this;
}
@Override
public Object dequeue() {
if (head == tail) {
return null;
}
Object obj = array[head];
array[head] = null;
head = (head + 1) % capcity;
return obj;
}
// 不擴容，要先判斷能否往數組中添加元素
public Queue enqueue2(Object obj) {
if ((tail + 1) % capcity == head) return this;
array[tail] = obj;
tail = (tail + 1) % capcity;
return this;
}
// 擴容
private void resize() {
// 說明還有空間
if (head != tail) {
return;
}
int oldCapcity = this.capcity;
int newCapcity = this.capcity * 2;
Object[] newArray = new Object[newCapcity];
for (int i = head; i < oldCapcity; i++) {
newArray[i - head] = array[i];
}
for (int i = 0; i < head; i++) {
newArray[capcity - head + i] = array[i];
}
this.capcity = newCapcity;
this.array = newArray;
this.head = 0;
this.tail = oldCapcity;
}
@Override
public int size() {
return tail - head;
}
}
說明： 循環隊列關鍵是判斷隊空和空滿的狀態分別進行處理。除開擴容操作，循環隊列的入隊和出隊的時間復雜度都是 O(1)，同時也可以充分利用 CPU 緩存，所以說一種高效的數據結構。
2.4 阻塞隊列和并發隊列
3. 隊列在軟件工程中應用
如 JDK 線程池，當線程池沒有空閑線程時，新的任務請求線程資源時，線程池該如何處理？各種處理策略又是如何實現的呢？我們一般有兩種處理策略。
非阻塞的處理方式，直接拒絕任務請求；
阻塞的處理方式，將請求排隊，等到有空閑線程時，取出排隊的請求繼續處理。
每天用心記錄一點點。內容也許不重要，但習慣很重要！
總結
以上是生活随笔為你收集整理的java 数据队列_Java 数据结构 - 队列的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： js百度地图android定位不准,百度
- 下一篇： Android入门简书,android