什么是隊列锋勺?
之前探討過一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)-棧搀崭,那是否有先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)呢?這就是我們本篇需要討論的另外一種操作受限的數(shù)據(jù)結(jié)構(gòu)-隊列虹茶。
隊列(queue)是一種操作受限的線性表刀森,只允許在表的一端進(jìn)行插入操作(入隊enqueue)而在另一端進(jìn)行刪除(出隊dequeue)的線性表踱启。進(jìn)行插入操作的端稱為隊尾,進(jìn)行刪除操作的一端稱為隊頭研底。隊列中沒有數(shù)據(jù)元素時稱為空隊列埠偿。
隊列的操作是按照先進(jìn)先出(first in first out)或后進(jìn)后出(last in last out)的原則進(jìn)行的。因此榜晦,隊列又被稱為FIFO表冠蒋。
隊列的分類
單向隊列(普通隊列)
相對于棧比較而言,隊列的實現(xiàn)稍微復(fù)雜點乾胶,棧的實現(xiàn)我們只需要一個棧頂指針就可以了抖剿,但是隊列需要兩個指針,一個是head指針识窿,指向隊頭斩郎,一個是tail指針,指向隊尾喻频。tail指針的任務(wù)就是尋找空位缩宜。
- 如果我們需要插入
f
字符串,那么我們只需要執(zhí)行queue[tail] = f
即可半抱。 - 此時
head = 0 tail = 6
脓恕。 - 如果我們執(zhí)行兩次出隊操作膜宋,執(zhí)行兩次
queue[head++] = null
即可窿侈。 - 此時
head = 2 tail = 6
。
定義抽象類型
Queue.java
public interface Queue<T> extends Iterable<T> {
void offer(T elem);
T poll();
T peek();
int size();
boolean isEmpty();
}
基于數(shù)組實現(xiàn)的隊列被稱為順序隊列
如何判斷隊空還是隊滿秋茫?
隊空:tail = queue.length
隊滿:head = tail
代碼實現(xiàn)
public class ArrayQueue<T> implements Queue<T> {
private Object[] data;
private int head;
private int tail;
private int size;
private int capacity;
private static final int DEFAULT_CAPACITY = 10;
public ArrayQueue() {
this(DEFAULT_CAPACITY);
}
public ArrayQueue(int capacity) {
this.data = new Object[capacity];
this.head = 0;
this.tail = 0;
this.capacity = capacity;
}
@Override
public void offer(T elem) {
if (tail == capacity) {
return;
}
data[tail++] = elem;
size++;
}
@Override
public T poll() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!");
}
T t = element(head);
data[head] = null;
head++;
size--;
return t;
}
@Override
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!");
}
T t = element(head);
return t;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return head == tail;
}
@SuppressWarnings("unchecked")
private T element(int index) {
return (T) data[index];
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private int index = head;
@Override
public boolean hasNext() {
return index < tail;
}
@Override
public T next() {
return element(index++);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
基于數(shù)組實現(xiàn)的隊列會有這樣一種情況:
例如上述的例子史简,出隊兩次之后,head = 2 tail = 6
,head之前的兩個位置就會空著圆兵,但是我們隊滿的判斷是tail == capacity
跺讯,所以出隊的話,head總要自增殉农,之前的位置就為空刀脏,如果此時tail移到最右邊,head之前還有位置超凳,此時的隊列是不滿的愈污,然而要入隊的話可能就會導(dǎo)致入隊失敗,那么我們需要對入隊的代碼轮傍,優(yōu)化下暂雹。
那么我們怎么實現(xiàn),head前面的位置是空创夜,我們還能執(zhí)行入隊操作呢杭跪,對!就是利用數(shù)據(jù)搬移的技術(shù)驰吓。代碼如下:
// moved是否需要數(shù)據(jù)搬移
public void enqueue(T elem, boolean moved) {
if (elem == null) {
throw new NullPointerException();
}
if (isFull()) {
doubleCapacity();
}
if (head != 0 && tail == capacity && moved) {
System.arraycopy(data, head, data, 0, tail - head);
for (int i = 0; i < head; i++) {
data[data.length - i - 1] = null;
}
tail -= head;
head = 0;
}
data[tail++] = elem;
size++;
}
實際上涧尿,基于數(shù)組實現(xiàn)的隊列還有一個問題,就是需要初始化數(shù)組大小檬贰,如果隊滿就不能添加元素现斋,所以想要添加元素,我們可以使用動態(tài)數(shù)組來實現(xiàn)偎蘸,對內(nèi)部數(shù)組進(jìn)行擴(kuò)容庄蹋,代碼如下:
private void doubleCapacity() {
int newCapacity = capacity << 1;
if (newCapacity < 0) {
throw new IllegalStateException("illegal Capacity: " + newCapacity);
}
Object[] newData = new Object[newCapacity];
System.arraycopy(data, head, newData, 0, tail - head);
data = newData;
}
不過還是建議不要擴(kuò)容,不要使用數(shù)組來實現(xiàn)無界隊列迷雪,想要實現(xiàn)無界隊列限书,可以使用鏈表。
基于鏈表實現(xiàn)的隊列被稱為鏈?zhǔn)疥犃?/h4>
public class LinkedQueue<T> implements Queue<T> {
private Node<T> head;
private Node<T> tail;
private int size;
@Override
public void offer(T elem) {
if (tail == null) {
Node<T> newNode = new Node<>(elem, null);
head = newNode;
tail = newNode;
} else {
tail.next = new Node<>(elem, null);
tail = tail.next;
}
size++;
}
@Override
public T poll() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!");
}
T value = head.data;
head = head.next;
if (head == null) {
tail = null;
}
size--;
return value;
}
@Override
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!");
}
T value = head.data;
return value;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return head == null;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private Node<T> p = head;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public T next() {
T data = p.data;
p = p.next;
return data;
}
};
}
private static class Node<T> {
private T data;
private Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
}
public class LinkedQueue<T> implements Queue<T> {
private Node<T> head;
private Node<T> tail;
private int size;
@Override
public void offer(T elem) {
if (tail == null) {
Node<T> newNode = new Node<>(elem, null);
head = newNode;
tail = newNode;
} else {
tail.next = new Node<>(elem, null);
tail = tail.next;
}
size++;
}
@Override
public T poll() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!");
}
T value = head.data;
head = head.next;
if (head == null) {
tail = null;
}
size--;
return value;
}
@Override
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!");
}
T value = head.data;
return value;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return head == null;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private Node<T> p = head;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public T next() {
T data = p.data;
p = p.next;
return data;
}
};
}
private static class Node<T> {
private T data;
private Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
}
基于鏈表實現(xiàn)的隊列章咧,從代碼中可以看出倦西,鏈?zhǔn)疥犃惺遣恍枰獢U(kuò)容,不需要數(shù)據(jù)搬移赁严,也不需要判斷隊滿扰柠,這是一個無界隊列。這會引發(fā)一個問題疼约,如果無限添加數(shù)據(jù)卤档,有可能這個隊列會很大,造成內(nèi)存溢出或者其他意想不到的錯誤程剥。
循環(huán)隊列
我們剛才使用數(shù)組來實現(xiàn)的隊列劝枣,當(dāng)tail = n && head != 0 的時候,執(zhí)行入隊操作,會有數(shù)據(jù)搬移的操作舔腾,這樣入隊操作就會受到影響溪胶,畢竟數(shù)據(jù)搬移的操作時間復(fù)雜度為O(n)
。想要解決這個問題稳诚,我們可以使用鏈?zhǔn)疥犃谢┎保擎準(zhǔn)疥犃幸灿袉栴},就是可能會產(chǎn)生內(nèi)存溢出扳还。那有沒有更好的方案去實現(xiàn)呢?
之前我們學(xué)過循環(huán)鏈表懒熙,那隊列是否也可以循環(huán)起來利用呢?當(dāng)tail == capacity && head != 0
的時候普办,是否可以將tail = 0
呢工扎?對,就是這樣去實現(xiàn)一個循環(huán)隊列衔蹲,這樣既能解決入隊會有數(shù)據(jù)搬移的操作肢娘,也能解決無界問題,實現(xiàn)有界隊列舆驶。
注意:循環(huán)隊列會浪費一個數(shù)組的存儲空間橱健。
就為什么循環(huán)隊列會浪費一個數(shù)組的存儲空間,談?wù)勎覍Υ说睦斫馍沉紫任覀儼凑枕樞蜿犃械娜腙牪僮鱽硌菔疽幌隆?/p>
- 初始化一個容量為8的循環(huán)隊列拘荡,
front=rear=0
; - 如果我們按照之前的順序隊列的實現(xiàn)方案來說的話撬陵,A進(jìn)隊珊皿,我們需要執(zhí)行
queue[rear] = A;rear++;
- 重復(fù)步驟2,因此讓
BCDEFG
進(jìn)隊巨税,那此時就是rear = 7
; - 此時H進(jìn)隊蟋定,
rear=7
的位置確實有個空位,那H進(jìn)隊以后草添,執(zhí)行queue[rear]=H;
驶兜。由于是循環(huán)隊列,所以執(zhí)行rear=0
远寸; - 由于rear指針的認(rèn)為是尋找空位抄淑,但是
queue[0]
是有元素的,rear
不能設(shè)置為0驰后,所以應(yīng)該在rear=7的時候就應(yīng)該判斷出此時已經(jīng)隊滿肆资,不能讓H進(jìn)隊。 - 其實主要問題是循環(huán)隊列判斷隊滿的條件是什么倡怎?如果不浪費空間迅耘,我們應(yīng)該如何判斷呢?
rear=queue.length?
注意這是循環(huán)隊列监署,如果僅僅是這么判斷是不行的颤专,front
指針可能會在任意位置。rear=front=0
也不能表示隊滿钠乏,也有可能隊空栖秕。這樣確實不好判斷,如果要判斷晓避,我們可能需要引入第三方變量簇捍,也是需要一個額外的空間去存儲queue的size。那如果浪費一個存儲空間呢俏拱?此時隊空的判斷條件依然是front==rear
暑塑,隊滿的判斷條件(rear + 1)%queue.length = front
代碼實現(xiàn):
public class ArrayCircularQueue<T> implements Queue<T> {
private Object[] data;
private int head;
private int tail;
private int n;
private static final int DEFAULT_CAPACITY = 10;
public ArrayCircularQueue() {
this(DEFAULT_CAPACITY);
}
public ArrayCircularQueue(int capacity) {
data = new Object[capacity + 1];
head = 0;
tail = 0;
n = capacity + 1;
}
@Override
public void offer(T elem) {
if (isFull()) {
throw new RuntimeException("Queue is full");
}
data[tail] = elem;
tail = adjustIndex(tail);
}
@Override
public T poll() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
T element = element(head);
head = adjustIndex(head);
return element;
}
@Override
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
return element(head);
}
@Override
public int size() {
return (tail + n - head) >= n ? tail - head : tail + n - head;
}
@Override
public boolean isEmpty() {
return tail == head;
}
public boolean isFull() {
return (tail + 1) % n == head;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public T next() {
return element(p++);
}
};
}
private int adjustIndex(int index) {
return (index + 1) % n;
}
@SuppressWarnings("unchecked")
private T element(int index) {
return (T) data[index];
}
}
雙端隊列
雙端隊列(deque)是指允許兩端都可以進(jìn)行入隊和出隊操作的隊列,deque 是 “double ended queue” 的簡稱锅必。那就說明元素可以從隊頭出隊和入隊事格,也可以從隊尾出隊和入隊。
雙端隊列也是有兩種實現(xiàn)方式
- 基于數(shù)組實現(xiàn)的可以參考Java源碼
java.util.ArrayDeque
- 基于鏈表實現(xiàn)的可以參考java源碼
java.util.LinkedList
雙端循環(huán)隊列代碼示例:
public class ArrayCircularDeque<T> implements Deque<T> {
private int head;
private int tail;
private Object[] data;
private int n;
private static final int DEFAULT_CAPACITY = 10;
public ArrayCircularDeque() {
this(DEFAULT_CAPACITY);
}
public ArrayCircularDeque(int capacity) {
data = new Object[capacity + 1];
head = 0;
tail = 0;
n = capacity + 1;
}
@Override
public void offerFirst(T t) {
if (isFull()) {
throw new RuntimeException("deque is full");
}
head = (head - 1 + n) % n;
data[head] = t;
}
@Override
public void offerLast(T t) {
if (isFull()) {
throw new RuntimeException("deque is full");
}
data[tail] = t;
tail = (tail + 1) % n;
}
@Override
public T pollFirst() {
if (isEmpty()) {
throw new RuntimeException("deque is empty");
}
T elements = elements(head);
data[head] = null;
head = (head + 1) % n;
return elements;
}
@Override
public T pollLast() {
if (isEmpty()) {
throw new RuntimeException("deque is empty");
}
T elements = elements(tail);
data[tail] = null;
tail = (tail - 1 + n) % n;
return elements;
}
@Override
public T peekFirst() {
if (isEmpty()) {
throw new RuntimeException("deque is empty");
}
return elements(head);
}
@Override
public T peekLast() {
if (isEmpty()) {
throw new RuntimeException("deque is empty");
}
return elements((tail - 1 + n) % n);
}
@Override
public void offer(T elem) {
offerLast(elem);
}
@Override
public T poll() {
return pollFirst();
}
@Override
public T peek() {
return peekFirst();
}
@Override
public int size() {
return (tail + n - head) >= n ? tail - head : tail + n - head;
}
@Override
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return (tail + 1) % n == head;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public T next() {
return elements(p++);
}
};
}
@SuppressWarnings("unchecked")
private T elements(int index) {
return (T) data[index];
}
}
其余分類
下面的隊列的分類舉例搞隐,應(yīng)該都屬于隊列的使用的實際案例驹愚,不太屬于隊列的分類,我覺得歸類為實際使用案例會更加貼切一點吧劣纲。下面的代碼目前不提供手動代碼實現(xiàn)逢捺,優(yōu)先級隊列可以等我們討論堆這樣一種數(shù)據(jù)結(jié)構(gòu)的時候,再來詳細(xì)的討論癞季。阻塞隊列和并發(fā)隊列等以后學(xué)習(xí)并發(fā)編程的時候再來詳細(xì)討論劫瞳。下面只提供一些概念上的內(nèi)容,不提供具體代碼實現(xiàn)绷柒。
優(yōu)先級隊列
優(yōu)先隊列中的每個元素都有各自的優(yōu)先級柠新,優(yōu)先級最高的元素最先得到服務(wù);優(yōu)先級相同的元素按照其在優(yōu)先隊列中的順序得到服務(wù)辉巡。優(yōu)先隊列往往用堆來實現(xiàn)恨憎。
java.util.PriorityQueue
阻塞隊列
簡單來說,在隊列的基礎(chǔ)上加上了阻塞操作郊楣。隊空的時候憔恳,不允許出隊,阻塞净蚤,等有數(shù)據(jù)才返回钥组。隊滿的時候,不允許入隊今瀑,等有空閑位置才能插入程梦。
那么其實這就是一個典型的点把,生產(chǎn)者,消費者模型S旄健@商印!
這種基于阻塞隊列實現(xiàn)的生產(chǎn)者挺份,消費者模型褒翰,可以有效地協(xié)調(diào)生產(chǎn)和消費的速度。當(dāng)生產(chǎn)者生產(chǎn)的數(shù)據(jù)速度過快匀泊,消費者來不及消費优训,存儲數(shù)據(jù)的隊列很快滿了,這個時候生產(chǎn)者就阻塞等待各聘,直到消費者消費了數(shù)據(jù)揣非。生產(chǎn)者才會被喚醒繼續(xù)生產(chǎn)。
我們還可以協(xié)調(diào)生產(chǎn)者消費者的個數(shù)躲因,來提高數(shù)據(jù)的處理效率妆兑。
java.util.concurrent.ArrayBlockingQueue
并發(fā)隊列
最簡單的方式就是在enqueue,dequeue方法上加鎖,但是鎖粒度大并發(fā)度會比較低毛仪,同一時刻僅允許一個存或者取搁嗓。實際上,基于數(shù)組實現(xiàn)的循環(huán)隊列箱靴,利用CAS原子操作腺逛,可以實現(xiàn)非常高效的并發(fā)隊列,這就是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因衡怀。
java.util.concurrent.ConcurrentLinkedQueue
隊列的應(yīng)用場景
-
線程池棍矛,java和python中的并發(fā)編程里,在線程池中都有隊列的身影抛杨。
線程池沒有空閑線程時够委,新的任務(wù)請求線程資源時,線程池該如何處理怖现?各種處理策略又是如何實現(xiàn)的呢茁帽?我們一般有兩種處理策略。第一種是非阻塞的處理方式屈嗤,直接拒絕任務(wù)請求潘拨;另一種是阻塞的處理方式,將請求排隊饶号,等到有空閑線程時铁追,取出排隊的請求繼續(xù)處理。那如何存儲排隊的請求呢茫船?我們希望公平地處理每個排隊的請求琅束,先進(jìn)者先服務(wù)扭屁,所以隊列這種數(shù)據(jù)結(jié)構(gòu)很適合來存儲排隊請求。
我們前面說過涩禀,隊列有基于鏈表和基于數(shù)組這兩種實現(xiàn)方式料滥。這兩種實現(xiàn)方式對于排隊請求又有什么區(qū)別呢?
基于鏈表的實現(xiàn)方式埋泵,可以實現(xiàn)一個支持無限排隊的無界隊列(unbounded queue)幔欧,但是可能會導(dǎo)致過多的請求排隊等待罪治,請求處理的響應(yīng)時間過長丽声。所以,針對響應(yīng)時間比較敏感的系統(tǒng)觉义,基于鏈表實現(xiàn)的無限排隊的線程池是不合適的雁社。
而基于數(shù)組實現(xiàn)的有界隊列(bounded queue),隊列的大小有限晒骇,所以線程池中排隊的請求超過隊列大小時霉撵,接下來的請求就會被拒絕,這種方式對響應(yīng)時間敏感的系統(tǒng)來說洪囤,就相對更加合理徒坡。不過,設(shè)置一個合理的隊列大小瘤缩,也是非常有講究的喇完。隊列太大導(dǎo)致等待的請求太多,隊列太小會導(dǎo)致無法充分利用系統(tǒng)資源剥啤、發(fā)揮最大性能锦溪。
除了前面講到隊列應(yīng)用在線程池請求排隊的場景之外,隊列可以應(yīng)用在任何有限資源池中府怯,用于排隊請求刻诊,比如數(shù)據(jù)庫連接池等。實際上牺丙,對于大部分資源有限的場景则涯,當(dāng)沒有空閑資源時,基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)請求排隊冲簿。
除了池化資源還有那些排隊場景呢是整?
- 超市排隊結(jié)賬
- 肯德基排隊取餐
- Web服務(wù)器請求管理
-
可以用來跟蹤最近添加的X個元素。當(dāng)隊列中超過的x個元素民假,只要將超過的元素從隊頭中取出浮入,那么剩下的就是最近添加的x個元素。
- 經(jīng)典的滑動窗口算法
廣度優(yōu)先搜索(BFS)圖遍歷
隊列的復(fù)雜度分析
操作 | 復(fù)雜度 |
---|---|
enqueue |
O(1) 如果涉及到數(shù)據(jù)搬移羊异,擴(kuò)容那就是o(n)
|
dequeue | O(1) |
peek | O(1) |
棧和隊列的區(qū)別
- 棧是先進(jìn)后出事秀,隊列是先進(jìn)先出彤断。
- 棧主要是兩個操作,入棧易迹,出棧宰衙。隊列主要是兩個操作,入隊睹欲,出隊
- 棧只允許在一端進(jìn)行操作供炼,隊列只允許一端進(jìn)行刪除,另一端插入窘疮。
總結(jié)
隊列最大的特點就是先進(jìn)先出袋哼,主要的兩個操作是入隊和出隊。
用數(shù)組實現(xiàn)的叫順序隊列闸衫,用鏈表實現(xiàn)的叫鏈?zhǔn)疥犃小?/p>
在數(shù)組實現(xiàn)隊列的時候涛贯,會有數(shù)據(jù)搬移操作,要想解決數(shù)據(jù)搬移的問題蔚出,我們需要循環(huán)隊列弟翘。
循環(huán)隊列最難的地方是要確定好隊空和隊滿的判定條件。
循環(huán)隊列解決了兩個問題骄酗,數(shù)據(jù)搬移和無界稀余。
循環(huán)隊列為什么需要浪費一個數(shù)組的存儲空間,我的理解是為了更方便的判斷隊滿的條件趋翻,不需要引入size這個變量睛琳,不需要額外的內(nèi)存空間,如果在并發(fā)編程里也無需考慮size變量的線程安全性嘿歌。
雙端隊列比普通隊列的操作更加靈活掸掏。
其余的高級隊列,我的理解是隊列的一種應(yīng)用宙帝。例如阻塞隊列丧凤,并發(fā)隊列,優(yōu)先級隊列步脓。
隊列的應(yīng)用場景很廣泛愿待,主要是判斷出是否是一個排隊的請求。池化資源靴患,訂單系統(tǒng)等等仍侥。