隊列
我在這一章的前半部分向大家介紹了棧這種資料結構，那麼我在這章的後部分，向大家介紹隊列這種資料結構。
隊列的概括
隊列，本身也是一種線性資料結構，換句話說資料依舊是排成一排，這一點和棧一樣。不過和棧不同的是，隊列隻能從一端添加元素，而從另一端取出元素v，通常。我們添加元素的一端稱為隊尾，而取出元素的一端稱為隊首**。事實上這一切都非常好了解，隊列這個名字的由來也和我們生活中，排隊那個隊列是一緻的。
我們簡單的看一個如圖示範：
假設這就是一個隊列，可以想象一下，比如說
- 我們去銀行辦事情，相應的就有一個櫃台，隊列就是排隊到這個櫃台辦業務
- 那麼一旦來了一個新的人。在資料結構領域，其實就是來了一個新的元素，這個新的元素就應該從隊尾的位置進入隊列
- 下面再來一個新的元素，這個新的元素依然是從隊尾的位置進入隊列，以此類推……
- 但是現在要出隊了，比如說，在櫃台的服務人員已經辦完了上一個業務，已經有空閑處理下一個任務啦，那麼此時，就要隊列中取出一個元素，取出的元素就應該是隊首元素，這種情況下取出的元素就應該是1。
通過分析可以看出，隊列是一種先進先出的資料結構，也就是生活中的先到先得，這是和棧的後進先出不一樣，這個差別（從每端取出資料的差別）看似很小的。但是，在實際的應用中卻大不相同。如果我們在生活中用棧這種方式來進行排隊辦理業務的話，相信沒有人會願意的。相應的這種先進先出，英文就是first in first out，縮寫成FIFO
隊列的實作
針對隊列這種資料結構來說，基本上寫了隻涉及這5個操作，分别是
- 向隊列中添加一個元素，也都是入隊，通常叫做
enqueue
- 從隊列中取出一個元素，也叫做出隊，通常叫做
dequeue
- 看一下隊首列的元素是誰，這個動作通常叫做
getFront
- 看一下隊列裡一共有多少個元素
getSize
- 判斷一下隊列是否為空
isEmpty
我們實作的方式也是寫一個接口叫做queue，我們依托不同的底層的資料結構可以實作這個接口。在隊列的實作中，我将非常快速的和之前的棧一樣，複用Array這個動态數組類來實作ArrayQueue
需要提一下，從使用者的角度來看，隻要實作上述操作就好，具體底層實作，使用者并不關心，實際上，底層确實有多種實作方式。
我們準備在之前實作的動态數組基礎上，來實作"隊列"這種資料結構。
先定義一個接口Interface，如下：
|
ArrayQueue實作代碼如下：
package com.lihe.leetcode;
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
//構造函數
public ArrayQueue(int capacity) {
array = new Array<>(capacity);
}
//無參構造函數
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
@Override
public E getFront() {
return array.getFirst();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public String toString(){
StringBuilder ret = new StringBuilder();
ret.append("Queue:");
ret.append("Front [");
for (int i = 0; i < array.getSize(); i++) {
ret.append(array.get(i));
if(i != array.getSize() - 1)
ret.append(", ");
}
ret.append("] tail");
return ret.toString();
}
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
/** 結果：
* Queue:Front [0] tail
* Queue:Front [0, 1] tail
* Queue:Front [0, 1, 2] tail
* Queue:Front [1, 2] tail
* Queue:Front [1, 2, 3] tail
* Queue:Front [1, 2, 3, 4] tail
* Queue:Front [1, 2, 3, 4, 5] tail
* Queue:Front [2, 3, 4, 5] tail
* Queue:Front [2, 3, 4, 5, 6] tail
* Queue:Front [2, 3, 4, 5, 6, 7] tail
* Queue:Front [2, 3, 4, 5, 6, 7, 8] tail
* Queue:Front [3, 4, 5, 6, 7, 8] tail
* Queue:Front [3, 4, 5, 6, 7, 8, 9] tail
*/
}
隊列的複雜度分析
最後，對于我們實作的ArrayQueue數組隊列，進行一下簡單的複雜度分析，這個複雜度分析大部分和之前的棧一樣。
在添加元素（入隊enqueue）的時候，每一次都是向數組的最後一個位置添加元素，在對進行均攤複雜度分析，最終是O(1)的複雜度，同時
getSize
，
isEmpty
，
getFront
也都是O(1)的複雜度。不過，我們出隊（dequeue）操作是一個O(n)複雜度的操作。這是因為在出隊的時候，需要把整個數組的第一個元素（索引為0）拿出來，而數組中後面剩下的所有元素都要向前挪一個位置，這顯然是O(n)的複雜度。
ArrayQueue<E>
·void enqueue(E) O(1) 均攤
·E dequeue() O(n)
·E getFront() O(1)
·int getSize() O(1)
·boolean isEmpty() O(1)
循環隊列
- 數組隊列的出隊操作的複雜度是O(n)，性能很差，解決方法就是使用循環隊列（Loop Queue）
- 正常情況：front指向隊列第一個元素，tail指向隊列中最後一個元素的後一個位置
- 隊列為空時，front和tail都指向第一個元素位置，不為空時，front != tail
- 入隊時：tail ++, 出隊時： front ++
- 循環隊列的示意圖如下：
-
資料結構基礎----隊列
入隊出隊過程：入隊5個元素
出隊兩個元素（隻需要front指向改變，不需要移動所有元素，複雜度為O（1））：
入隊4個元素
注意：因為front == tail表示隊列為空，故此時如果在添加一個元素會導緻front == tail，然而此時表示隊列已滿。
是以，當tail + 1 == front 時表示隊列為滿。因為是循環隊列故使用（tail + 1）% c == front（當front=0,tail=7時，使用（7+1）%8 ==0）。c代表capacity(容積)。，循環隊列操作front和tail都需要使用%
結論：循環隊列使用%，類似鐘表11點之後叫12點或者0點
- 實作循環隊列的業務邏輯，并進行測試：
資料結構基礎----隊列 -
package com.lihe.datastructure; public class LoopQueue<E> implements Queue<E>{ private E[] data; //隊列 private int front,tail; //隊列隊首隊尾 private int size; //隊列元素個數 //有參構造函數 public LoopQueue(int capacity) { //因為循環隊列浪費一個空間，需要存儲capacity個元素，故需要capacity+1的空間 data = (E[])new Object[capacity + 1]; front = 0; tail = 0; size = 0; } //無參構造函數 public LoopQueue() { this(10);//直接調用有參數的構造函數，然後傳入一個預設值 } //實際存儲資料為容積-1,有意浪費一個空間 //容積比長度少一 public int getCapacity(){ return data.length - 1; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } //入隊 @Override public void enqueue(E e) { if((tail + 1) % data.length == front){ //擴容成所能存放個數的兩倍，不是空間的兩倍，因為浪費了一個空間 resize(getCapacity() * 2); } data[tail] = e; tail = (tail + 1) % data.length; //循環隊列% size ++; } //擴容 private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity + 1]; for (int i = 0; i < size; i++) { //data中的元素不一定從0開始，與newData之間偏移量front, //因是循環隊列防止越界，故用%data.length newData[i] = data[(front + i) % data.length]; } data = newData; front = 0; tail = size;//元素個數不變 } //出隊 @Override public E dequeue() { if(isEmpty()){ throw new IllegalArgumentException("Cannot enqueue from an empty queue"); } E ret = data[front]; front = (front + 1) % data.length; size --; if(size == getCapacity() / 4 && getCapacity() / 2 != 0) resize(getCapacity() / 2); return ret; } @Override public E getFront() { if(isEmpty()){ throw new IllegalArgumentException("Queue is empty "); } return data[front]; } //override代表複用 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue:size=%d,capacity=%d\n", size, getCapacity())); res.append("front ["); //周遊循環隊列，隊首是front，隊尾是tail-1, // 因為是循環故tail可能<front,故條件為i != tail不是i < tail， // 故遞增為 i= (i + 1) % data.length for (int i = front; i != tail; i= (i + 1) % data.length ) { res.append(data[i]); //不是最後一個元素的判斷條件 if ((i + 1) % data.length != tail) { res.append(','); } } res.append("] tail"); return res.toString(); } //測試 public static void main(String[] args) { LoopQueue<Integer> queue = new LoopQueue<>(); for (int i = 0; i < 10; i++) { queue.enqueue(i); System.out.println(queue); if(i % 3 == 2){ queue.dequeue(); System.out.println(queue); } } } } /** * 周遊循環隊列中兩種方法： * 法一： * for (int i = 0; i < size; i++) { * //data中的元素不一定從0開始，與newData之間偏移量front, * //因是循環隊列防止越界，故用%data.length * newData[i] = data[(front + i) % data.length]; * } * * 法二： * //周遊循環隊列，隊首是front，隊尾是tail-1, * // 因為是循環故tail可能<front,故條件為i != tail不是i < tail， * // 故遞增為 i= (i + 1) % data.length * for (int i = front; i != tail; i= (i + 1) % data.length ) { * res.append(data[i]); * //不是最後一個元素的判斷條件 * if ((i + 1) % data.length != tail) { * res.append(','); * } * } */ - 輸出結果：
-
/** * 結果： * Queue:size=1,capacity=10 * front [0] tail * Queue:size=2,capacity=10 * front [0,1] tail * Queue:size=3,capacity=10 * front [0,1,2] tail * Queue:size=2,capacity=5 * front [1,2] tail * Queue:size=3,capacity=5 * front [1,2,3] tail * Queue:size=4,capacity=5 * front [1,2,3,4] tail * Queue:size=5,capacity=5 * front [1,2,3,4,5] tail * Queue:size=4,capacity=5 * front [2,3,4,5] tail * Queue:size=5,capacity=5 * front [2,3,4,5,6] tail * Queue:size=6,capacity=10 * front [2,3,4,5,6,7] tail * Queue:size=7,capacity=10 * front [2,3,4,5,6,7,8] tail * Queue:size=6,capacity=10 * front [3,4,5,6,7,8] tail * Queue:size=7,capacity=10 * front [3,4,5,6,7,8,9] tail */
循環隊列的複雜度分析
-
LoopQueue<E> ·void enqueue(E) O(1) 均攤 ·E dequeue() O(1) 均攤 ·E getFront() O(1) ·int getSize() O(1) ·boolean isEmpty() O(1)
使用簡單算例測試ArrayQueue與LoopQueue的性能差異
package com.lihe.datastructure;
import java.util.Random;
public class Main {
// 測試使用q運作opCount個enqueue和dequeue操作所需要的時間，機關：秒
private static double testQueue(Queue<Integer> q, int opCount) {
long startTime = System.nanoTime();//計時
Random random = new Random();
//多次入隊
for (int i = 0; i < opCount; i++) {
q.enqueue(random.nextInt(Integer.MAX_VALUE));
}
//多次出對
for (int i = 0; i < opCount; i++) {
q.dequeue();
}
long endTime = System.nanoTime();//計時
return (endTime - startTime) / 1000000000.0;//用時
}
public static void main(String[] args) {
int opCount = 100000; //操作數量
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}
- 輸出結果
-
ArrayQueue, time: 5.891407568 s LoopQueue, time: 0.018795095 s