與前面提到的 "數據結構" 相同，隊列中的數據也呈 線性排列 。雖然與 "棧" 有些相似，但隊列中添加和刪除數據的操作分別是在 兩端 進行的，就和隊列這個名字一樣，把它想象成排成一隊的人更容易理解。在隊列中，處理總是從第一名開始往後進行，而新來的人只能排在隊尾。 隊列是什麼？ 如上就是隊列的概念圖， ...
與前面提到的數據結構相同，隊列中的數據也呈線性排列。雖然與棧有些相似，但隊列中添加和刪除數據的操作分別是在兩端進行的，就和隊列這個名字一樣，把它想象成排成一隊的人更容易理解。在隊列中，處理總是從第一名開始往後進行，而新來的人只能排在隊尾。
隊列是什麼？
如上就是隊列的概念圖，現在隊列中只有數據 Blue。往隊列中添加數據時，數據被加在最上面。
然後，隊列中添加了數據 Green。往隊列中添加數據的操作叫作入隊。
緊接著，數據 Red 也入隊了。
從隊列中取出（刪除）數據時，是從最下麵，也就是最早入隊的數據開始的，即 Blue。從隊列中刪除數據的操作叫作出隊。
如果再進行一次出隊操作，取出的就是 Green 了。
像隊列這種最先進去的數據最先被取來，即先進先出的結構，我們稱為 First In First Out，簡稱 FIFO。
與棧類似，隊列中可以操作數據的位置也有一定的限制。在棧中，數據的添加和刪除都在同一端進行，而在隊列中則分別是在兩端進行的。隊列也不能直接訪問位於中間的數據，必須通過出隊操作將目標數據變成首位後才能訪問。
介紹完隊列的基本知識後，接下來舉一個例子，比如生活中常見的排隊買票。
如何理解隊列？
隊列這個概念非常好理解，你可以把它想象成排隊買票，先來的先買，後來的人只能站末尾，不允許插隊，先進者先出，這就是典型的隊列。
上一篇講到棧只支持兩個基本操作：入棧和出棧。隊列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個：入隊，放一個數據到隊列尾部；出隊，從隊列頭部取一個元素。
所以，隊列跟棧一樣，也是一種操作受限的線性表數據結構，隊列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎的數據結構，隊列的應用也非常廣泛，特別是一些具有某些額外特性的隊列，比如迴圈隊列、阻塞隊列、併發隊列。
隊列的實現
看到這裡，相信你已經對隊列有了初步的理解，隊列主要包含兩個操作，入隊和出隊。光理解還不夠，我們還要動手去實現隊列，接下來讓我們來看一看如何用代碼實現一個隊列。
跟棧一樣，隊列可以用數組來實現，也可以用鏈表來實現。用數組實現的棧叫作順序棧，用鏈表實現的棧叫作鏈式棧。同樣，用數組實現的隊列叫作順序隊列，用鏈表實現的隊列叫作鏈式隊列。
首先來看下用數組實現的隊列是怎麼樣的，其實現如下圖所示：
那麼我先用 Java 語言來實現下順序隊列，代碼如下：
/**
* 基於數組實現的順序隊列
*
* @author wupx
* @date 2020/02/13
*/
public class ArrayQueue {
private String[] items;
/**
* 數組大小
*/
private int n = 0;
/**
* 隊頭下標
*/
private int head = 0;
/**
* 隊尾下標
*/
private int tail = 0;
/**
* 申請一個大小為 capacity 的數組
*
* @param capacity
*/
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
/**
* 入隊
*
* @param item
* @return
*/
public boolean enqueue(String item) {
// 如果 tail == n 表示隊列已經滿了
if (tail == n) {
return false;
}
items[tail] = item;
++tail;
return true;
}
/**
* 出隊
*
* @return
*/
public String dequeue() {
// 如果 head == tail 表示隊列為空
if (head == tail) {
return null;
}
String ret = items[head];
++head;
return ret;
}
}另外一種就是鏈式隊列，它的實現如下圖所示：
再用鏈表去實現隊列，代碼如下：
/**
* 基於鏈表實現的鏈式隊列
*
* @author wupx
* @date 2020/02/13
*/
public class LinkedListQueue {
/**
* 隊頭
*/
private Node head = null;
/**
* 隊尾
*/
private Node tail = null;
/**
* 入隊
*
* @param value
*/
public void enqueue(String value) {
if (tail == null) {
Node newNode = new Node(value, null);
head = newNode;
tail = newNode;
} else {
tail.next = new Node(value, null);
tail = tail.next;
}
}
/**
* 出隊
*
* @return
*/
public String dequeue() {
if (head == null) {
return null;
}
String value = head.data;
head = head.next;
if (head == null) {
tail = null;
}
return value;
}
public void printAll() {
Node p = head;
while (p != null) {
System.out.print(p.data + " ");
p = p.next;
}
System.out.println();
}
private static class Node {
private String data;
private Node next;
public Node(String data, Node next) {
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
}
}到此，我們就分別實現了基於數組和鏈表的隊列，大家可以自己實現下。
隊列還有很多擴展，比如迴圈隊列、阻塞隊列、併發隊列等，將在以後的文章中進行介紹。
總結
這篇主要講了一種跟棧很相似的數據結構-隊列，也是一種線性邏輯結構。
隊列遵循先進先出（FIFO）的原則，主要的兩個操作是入隊和出隊。隊列既可以用數組來實現，也可以用鏈表來實現。用數組實現的叫順序隊列，用鏈表實現的叫鏈式隊列。
參考
《我的第一本演算法書》
