隊(duì)列（queue）是一種采用先進(jìn)先出(FIFO)策略的抽象數(shù)據(jù)結(jié)構(gòu)，即最先進(jìn)隊(duì)列的數(shù)據(jù)元素，同樣要最先出隊(duì)列。隊(duì)列跟我們排隊(duì)買票一樣，先來(lái)排隊(duì)的肯定先買票，后來(lái)排隊(duì)的的后買到票。隊(duì)列如下圖所示：
隊(duì)列有兩個(gè)重要的概念，一個(gè)叫隊(duì)頭，一個(gè)叫隊(duì)尾，隊(duì)頭指向的是第一個(gè)元素，而隊(duì)尾指向的是最后一個(gè)元素。隊(duì)列跟棧一樣也是訪問受限制的，所以隊(duì)列也只有兩個(gè)主要的操作：入隊(duì)(enqueue)操作 和 出隊(duì)(dequeue)操作 。入隊(duì)操作就是將一個(gè)元素添加到隊(duì)尾，出隊(duì)操作就是從隊(duì)頭取出一個(gè)元素。
隊(duì)列的底層實(shí)現(xiàn)可以用數(shù)組和鏈表，基于數(shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，基于鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列，下面我們分別用數(shù)組和鏈表來(lái)簡(jiǎn)單的實(shí)現(xiàn)這兩種隊(duì)列。
基于數(shù)組的隊(duì)列
不管使用那種方式來(lái)實(shí)現(xiàn)隊(duì)列，都需要定義兩個(gè)指針分別指向隊(duì)頭和隊(duì)尾，本文中我們用head指向隊(duì)頭，tail指向隊(duì)尾，后面的示例中這將默認(rèn)使用這個(gè)，有特殊的地方我會(huì)進(jìn)行說(shuō)明，先來(lái)看看順序隊(duì)列的入隊(duì)、出隊(duì)操作。
圖中可以看出，入隊(duì)時(shí)，隊(duì)尾往后移動(dòng)，隊(duì)頭保持不變，出隊(duì)是隊(duì)頭往后移動(dòng)，隊(duì)尾保持不變。入隊(duì)、出隊(duì)操作的邏輯都比較簡(jiǎn)單，可能你有疑問的地方是：出隊(duì)時(shí)為什么隊(duì)頭要往后移動(dòng)而不是一直指向數(shù)組下標(biāo)為0的位置？ 為什么呢？如果我們保持隊(duì)頭一直指向數(shù)組下標(biāo)為0的位置，那每次出隊(duì)操作后，后面的數(shù)據(jù)都需要往前挪一位，換句話說(shuō)每次出隊(duì)操作都需要進(jìn)行數(shù)據(jù)遷移，而數(shù)據(jù)遷移的代價(jià)比較大，每次數(shù)據(jù)遷移的時(shí)間復(fù)雜度為O(n)，這樣會(huì)極大的影響隊(duì)列的使用性能。如果我們出隊(duì)時(shí)，隊(duì)頭往后移動(dòng)一位，這樣我們就避免每次出隊(duì)都進(jìn)行數(shù)據(jù)遷移，我們只需要在只有在tail等于數(shù)組大小且head不等于0時(shí)，進(jìn)行一次數(shù)據(jù)遷移，將已經(jīng)出隊(duì)留下的空間繼續(xù)供入隊(duì)時(shí)使用。下圖是數(shù)據(jù)遷移的過(guò)程：
數(shù)據(jù)遷移時(shí)，從head位置開始的數(shù)據(jù)都需要往前移動(dòng)head位，這樣就把出隊(duì)后的空間騰出來(lái)，供后續(xù)入隊(duì)操作使用。
基于數(shù)組的隊(duì)列實(shí)現(xiàn)代碼：
/**
* 基于數(shù)組的隊(duì)列
*/
public class ArrayQueue {
// 存放數(shù)據(jù)的數(shù)組
private String[] items;
// 容器的大小
private int size = 0;
// 第一個(gè)節(jié)點(diǎn)
private int head = 0;
// 最后一個(gè)節(jié)點(diǎn)
private int tail = 0;
// 構(gòu)造函數(shù)
public ArrayQueue(int size){
this.size = size;
items = new String[size];
}
/**
* 入隊(duì)操作
* @param data
* @return
*/
public int enqueue(String data){
// 如果最后一個(gè)節(jié)點(diǎn)等于容器大小，說(shuō)明隊(duì)列滿了
/**
* 判斷隊(duì)列滿了的條件，tail = size,head = 0,
*/
if (tail == size && head == 0) return -1;
/**
* 如果tail = size，但是head != 0,說(shuō)明前有數(shù)據(jù)刪除，隊(duì)列未滿，需要數(shù)據(jù)遷移
*/
if (tail == size){
// head 后面的數(shù)據(jù)都需要往前遷移 head 位
for (int i= head;i< size;i++){
items[i-head] = items[i];
}
// 將最后一個(gè)元素遷移 head 位
tail -=head;
// 第一個(gè)元素指向 0
head = 0;
}
// 向隊(duì)列中添加元素
items[tail] = data;
tail++;
return 1;
}
/**
* 出隊(duì)操作
* @return
*/
public String dequeue(){
// 第一個(gè)元素和最后一個(gè)元素相等時(shí)，隊(duì)列為空
if (head == tail) return null;
String result = items[head];
// 第一個(gè)元素后移一次，這樣做的好處是在出隊(duì)時(shí)不需要數(shù)據(jù)遷移
head ++ ;
return result;
}
}
鏈?zhǔn)疥?duì)列
鏈?zhǔn)疥?duì)列實(shí)現(xiàn)起來(lái)相對(duì)順序隊(duì)列來(lái)說(shuō)要簡(jiǎn)單很多，我們先來(lái)看看鏈?zhǔn)疥?duì)列的入隊(duì)、出隊(duì)操作：
從圖中可以看出鏈?zhǔn)疥?duì)列入隊(duì)操作是將tail的next指向新增的節(jié)點(diǎn)，然后將tail指向新增的節(jié)點(diǎn)，出隊(duì)操作時(shí)，將head節(jié)點(diǎn)指向head.next節(jié)點(diǎn)。鏈?zhǔn)疥?duì)列與順序隊(duì)列比起來(lái)不需要進(jìn)行數(shù)據(jù)的遷移，但是鏈?zhǔn)疥?duì)列增加了存儲(chǔ)成本。
基于鏈表的隊(duì)列實(shí)現(xiàn)代碼
/**
* 基于鏈表的隊(duì)列
*/
public class LinkQueue {
// 指向隊(duì)首
private Node head;
// 指向隊(duì)尾
private Node tail;
/**
* 入隊(duì)操作
* @param data
* @return
*/
public int enqueue(String data){
Node node = new Node(data,null);
// 判斷隊(duì)列中是否有元素
if (tail == null) {
tail = node;
head = node;
}else {
tail.next = node;
tail = node;
}
return 1;
}
/**
* 出隊(duì)操作
* @return
*/
public String dequeue(){
if (head==null) return null;
String data = head.data;
head = head.next;
// 取出元素后，頭指針為空，說(shuō)明隊(duì)列中沒有元素，tail也需要制為空
if (head == null){
tail = null;
}
return data;
}
class Node{
private String data;
private Node next;
public Node(String data,Node node){
this.data = data;
next = node;
}
}
}
循環(huán)隊(duì)列
循環(huán)隊(duì)列是對(duì)順序隊(duì)列的改進(jìn)，因?yàn)轫樞蜿?duì)列不可避免的數(shù)據(jù)遷移操作，數(shù)據(jù)遷移操作會(huì)導(dǎo)致隊(duì)列的性能下降，為了避免這個(gè)問題，將隊(duì)列改造成循環(huán)的，當(dāng)tail到達(dá)數(shù)組的最大下標(biāo)時(shí)，重新指回?cái)?shù)組下標(biāo)為0的位置，這樣就避免了數(shù)據(jù)遷移。先來(lái)看看循環(huán)隊(duì)列的出隊(duì)、入隊(duì)操作：
因?yàn)殛?duì)列是循環(huán)隊(duì)列，所以在進(jìn)行入隊(duì)、出隊(duì)操作時(shí)，就不能像順序隊(duì)列那樣對(duì)tail、head進(jìn)行簡(jiǎn)單的加1操作，我們需要對(duì)tail、head加1后與數(shù)組的大小進(jìn)行求余操作，來(lái)得出tail、head的值，這樣才能進(jìn)行循環(huán)操作。循環(huán)隊(duì)列需要犧牲一個(gè)存儲(chǔ)空間，對(duì)于一個(gè)存儲(chǔ)空間為n的循環(huán)隊(duì)列來(lái)說(shuō)只能存放n-1為數(shù)據(jù)，因?yàn)槿绻粻奚粋€(gè)存儲(chǔ)空間的話，當(dāng)tail==head時(shí)，就有可能存在隊(duì)空或者隊(duì)滿的情況。
循環(huán)隊(duì)列的實(shí)現(xiàn)代碼
/**
* 環(huán)形隊(duì)列,不需要數(shù)據(jù)遷移，提高性能
*/
public class CircularQueue {
// 存放數(shù)據(jù)的數(shù)組
private String[] items;
// 容器的大小
private int size = 0;
// 第一個(gè)節(jié)點(diǎn)
private int head = 0;
// 最后一個(gè)節(jié)點(diǎn)
private int tail = 0;
// 構(gòu)造函數(shù)
public CircularQueue(int size){
this.size = size;
items = new String[size];
}
/**
* 入隊(duì)操作
* @param data
* @return
*/
public int enqueue(String data){
/**
* 判斷環(huán)形隊(duì)列滿了的條件，(tail+1)求余等于head
*/
if ((tail+1)%size == head) return -1;
// 向隊(duì)列中添加元素
items[tail] = data;
// 因?yàn)槭黔h(huán)形隊(duì)列，所以下邊是數(shù)組長(zhǎng)度的余數(shù)
tail= (tail+1)%size;
return 1;
}
/**
* 出隊(duì)操作
* @return
*/
public String dequeue(){
// 第一個(gè)元素和最后一個(gè)元素相等時(shí)，隊(duì)列為空
if (head == tail) return null;
String result = items[head];
// 因?yàn)槭黔h(huán)形隊(duì)列，所以下邊是數(shù)組長(zhǎng)度的余數(shù)
head = (head+1)% size ;
return result;
}
}
雙端隊(duì)列
雙端隊(duì)列是一種隊(duì)頭、隊(duì)尾都可以進(jìn)行入隊(duì)、出隊(duì)操作的隊(duì)列，雙端隊(duì)列采用雙向鏈表來(lái)實(shí)現(xiàn)，先來(lái)看一下雙端隊(duì)列的入隊(duì)、出隊(duì)操作：
可以從動(dòng)態(tài)圖中看出，雙端隊(duì)列的每一端都是一個(gè)棧，都符合棧先進(jìn)后出的特性，如果我們對(duì)雙端隊(duì)列進(jìn)行禁止隊(duì)頭入隊(duì)和隊(duì)尾出隊(duì)操作的限制，雙端隊(duì)列又變成了一個(gè)鏈?zhǔn)疥?duì)列，雙端隊(duì)列是一種多功能的數(shù)據(jù)結(jié)構(gòu)，我們可以使用它來(lái)提供隊(duì)列和棧兩種功能。
雙端隊(duì)列的實(shí)現(xiàn)代碼
/**
* 雙端隊(duì)列，使用雙向鏈表實(shí)現(xiàn)
*/
public class DoubleEndsQueue {
private static class Node {
String item;
Node next;
Node prev;
Node(Node prev, String element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 第一個(gè)節(jié)點(diǎn)
private Node first;
// 最后一個(gè)節(jié)點(diǎn)
private Node last;
/*
* 在第一個(gè)節(jié)點(diǎn)前面入隊(duì)
*/
public void enqueueFirst(String e) {
final Node f = first;
final Node newNode = new Node(null, e, f);
// 第一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
first = newNode;
if (f == null)
// 最后一個(gè)節(jié)點(diǎn)也指向該節(jié)點(diǎn)
last = newNode;
else
// 當(dāng)前節(jié)點(diǎn)的前節(jié)點(diǎn)指向新節(jié)點(diǎn)
f.prev = newNode;
}
/**
* 在最后一個(gè)元素后面入隊(duì)
* @param e
*/
public void enqueueLast(String e) {
final Node l = last;
final Node newNode = new Node(l, e, null);
// 最后一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
last = newNode;
if (l == null)
// 第一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
first = newNode;
else
// 當(dāng)前節(jié)點(diǎn)的下節(jié)點(diǎn)指向新節(jié)點(diǎn)
l.next = newNode;
}
/**
* 從第一個(gè)節(jié)點(diǎn)出隊(duì)
* @return
*/
public String dequeueFirst() {
if (first == null) return null;
final Node f = first;
String element = f.item;
Node next = f.next;
f.item = null;
f.next = null;
// 第一個(gè)節(jié)點(diǎn)指向當(dāng)先節(jié)點(diǎn)的next節(jié)點(diǎn)
first = next;
if (next == null)
// 說(shuō)明隊(duì)列為空
last = null;
else
next.prev = null;
return element;
}
/**
* 從最后節(jié)點(diǎn)出隊(duì)
* @return
*/
public String dequeueLast() {
final Node l = last;
if (last == null) return null;
String element = l.item;
Node prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
return element;
}
// 輸出隊(duì)列全部?jī)?nèi)容
public void displayAll() {
while (first !=null){
System.out.print(first.item+" ");
first = first.next;
}
System.out.println("===============");
}
}
優(yōu)先隊(duì)列
優(yōu)先隊(duì)列為一種不必遵循隊(duì)列先進(jìn)先出(FIFO)特性的特殊隊(duì)列，優(yōu)先隊(duì)列跟普通隊(duì)列一樣都只有一個(gè)隊(duì)頭和一個(gè)隊(duì)尾并且也是從隊(duì)頭出隊(duì)，隊(duì)尾入隊(duì)，不過(guò)在優(yōu)先隊(duì)列中，每次入隊(duì)時(shí)，都會(huì)按照入隊(duì)數(shù)據(jù)項(xiàng)的關(guān)鍵值進(jìn)行排序(從大到小、從小到大)，這樣保證了關(guān)鍵字最小的或者最大的項(xiàng)始終在隊(duì)頭，出隊(duì)的時(shí)候優(yōu)先級(jí)最高的就最先出隊(duì)，這個(gè)就像我們醫(yī)院就醫(yī)一樣，急救的病人要比普通的病人先就診。一起來(lái)看看優(yōu)先隊(duì)列的出隊(duì)、入隊(duì)操作：
在示例中，我們規(guī)定數(shù)值越小優(yōu)先級(jí)越高。我們每執(zhí)行一次入隊(duì)操作時(shí)，小的元素都會(huì)靠近頭隊(duì)，在出隊(duì)的時(shí)候，元素小的也就先出隊(duì)。
優(yōu)先隊(duì)列的代碼實(shí)現(xiàn)
這里使用的數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列，用數(shù)組實(shí)現(xiàn)主要原因是更好理解優(yōu)先隊(duì)列的思想。一般都是使用堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，因?yàn)閿?shù)組實(shí)現(xiàn)在插入的時(shí)候?qū)?shù)據(jù)的排序代價(jià)比較大。
/**
* 優(yōu)先隊(duì)列
*/
public class PriorityQueue {
// 存放數(shù)據(jù)的數(shù)組
private Integer[] items;
// 容器的大小
private int size = 0;
// 第一個(gè)節(jié)點(diǎn)
private int head = 0;
// 構(gòu)造函數(shù)
public PriorityQueue(int size){
this.size = size;
items = new Integer[size];
}
/**
* 入隊(duì)操作
* @param data
* @return
*/
public int enqueue(Integer data){
int j;
if (head == 0){
items[head++] = data;
}
else {
for (j=head-1;j>=0;j--){
// 將小的數(shù)往后排
if (data > items[j]){
items[j+1] = items[j];
}else {
break;
}
}
items[j+1] = data;
head++;
}
return 1;
}
public Integer dequeue(){
return items[--head];
}
}
總結(jié)
- 隊(duì)列是一種遵循先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)
- 隊(duì)列可以使用數(shù)組和鏈表實(shí)現(xiàn)，數(shù)組實(shí)現(xiàn)叫作順序隊(duì)列，鏈表實(shí)現(xiàn)叫作鏈?zhǔn)疥?duì)列
- 循環(huán)隊(duì)列解決了順序隊(duì)列的數(shù)據(jù)遷移帶來(lái)的性能損耗的問題
- 雙端隊(duì)列是隊(duì)頭和隊(duì)尾都可以進(jìn)行入隊(duì)、出隊(duì)操作的隊(duì)列
- 優(yōu)先隊(duì)列是一種不必遵循先進(jìn)先出規(guī)則的隊(duì)列，任意元素加入時(shí)，都會(huì)講優(yōu)先級(jí)最高的放入到隊(duì)頭
