知識星球來自：Hollis（微訊號：hollischuang）
全文字數： 3000
閱讀時間： 6分鐘
我是一個棧，先來跟你介紹一下我的家族，我的家族是一個很古老的家族，家族成員很多，外界稱呼我們這個家族為資料結構。我們是計算機世界中儲存和組織資料的。資料結構家族在計算機世界中是至關重要的，因為我們家族功能的強大，現代程式語言及其API中都有我們家族成員的身影。
我的家族是一個龐大的家族。家族中也有幾大分支，比如說樹、圖、堆、散串列等。各個分支都有不同的能力，所以很多人選擇適當的資料結構是一項很重要的工作。我們家族和演演算法家族是世交，基本上所有重要場合兩家都會一起出現。
我叫棧，我的爸爸叫陣列，我的媽媽叫連結串列，我的雙胞胎弟弟叫佇列。我們這個家庭是整個資料結構家族中比較重要的家庭。
和你說過了，我們資料結構家族是計算機世界中儲存和組織資料的。我的家族之所以這麼強大，就是因為我們要應付各種需求，提供不同的資料儲存方式。我的四個家庭成員分別可以解決不同的資料存取需求。
說起我的爸爸——陣列，他是資料結構家族的族長，人們都說他是資料結構大家族的根基。很多程式語言都內建陣列。
陣列爸爸是個很富有的人，他有很多土地。每當有人找他來儲存資料的時候，他都會預先劃分出一塊連續的土地（連續的記憶體），然後把別人交給他的資料按順序儲存在這些連續的土地中，當別人來取這些資料的時候，需要提供給陣列要取哪塊土地中的資料（陣列的位置索引），然後陣列就可以直接去那塊土地中把資料取出來，交給需要讀取這個資料的人。並不是所有資料陣列都能幫忙儲存的，父親只會幫別人儲存相同型別的資料。
陣列資料結構是由相同型別的元素（element）的集合所組成的資料結構，分配一塊連續的記憶體來儲存。利用元素的索引（index）可以計算出該元素對應的儲存地址。
我的家族的所有人都支援幾個基本的操作：插入、刪除、讀取。
因為陣列爸爸在儲存資料的時候，是按照順序儲存的，他儲存資料的土地是一塊一塊相連的。那麼，他的特點就是定址讀取資料比較容易，但是插入和刪除比較困難。這個其實比較好理解。讀取容易的原因是隻要你告訴陣列你要從哪塊土地讀取資料，他就會直接去那塊土地中把資料取出來給你。插入和刪除比較麻煩，主要是因為這些儲存資料的空間都是連著的，比如編號為0-1-2-3-4這五塊土地中都儲存了資料，但是現在你要往1中插入一塊資料，那就意味著從1開始，後面的所有土地中的資料都要往後移一個位置。這是很大的工作量啊。
人們都說，男女搭配，幹活不累。由於陣列爸爸有定址容易，插入和刪除困難的問題，他在找老婆的時候特意找了一個和自己互補的姑娘——連結串列。連結串列媽媽的特點正好是定址困難，插入和刪除容易。
在幫助別人儲存資料這件事上，連結串列的方式和陣列有很大不同。陣列是提前劃分了一大片連續的土地，用來儲存資料。但是連結串列不是這麼做的，因為連結串列媽媽家裡並沒有陣列爸爸家裡那麼富有。他的資料儲存並不是連續的，能這麼做的原因是媽媽儲存資料的土地中有兩塊區域，一塊用來儲存資料，一塊用來記錄下一個資料儲存在哪塊土地中（指標）。這樣，別人找他儲存資料的時候，她就要根據指示先找到下一塊空餘的土地，然後把資料儲存在裡面。連結串列這樣的資料儲存方式可以把一些碎片空間利用起來。
連結串列是一種線性表，但是並不會按線性的順序儲存資料，而是在每一個節點裡儲存著下一個節點的指標。
透過上面的這種儲存資料的方式，連結串列在插入和刪除資料的時候比較容易，比如編號為0-1-2-3-4這五塊土地中都儲存了資料，但是現在你要往1中插入一塊資料，那麼只需要依次更改0號土地和1號土地中記錄下一塊土地地址的值就行了。對於其他的資料儲存沒有任何影響。但是，如果你想從資料中取出一塊資料那可就麻煩了，因為這意味著連結串列媽媽要幫你從第一塊土地開始挨個幫你找。一直找到你要的資料為止。
棧，也就是我，一個英俊瀟灑的資料結構。我和佇列是一堆孿生兄弟。我們兩個都可以用陣列和連結串列來實現。雖然是雙胞胎，但是我們兩個都是有性格的，我們要求別人儲存資料和取出資料的順序要按照我們的規矩來。
我的原則是：先進後出（棧）
弟弟的原則是：先進先出（佇列）
我給你舉個例子你就明白了，我和弟弟每個人都有一個管子，用來幫你們儲存資料，當然這個管子可能是用陣列爸爸是實現的也可能是連結串列媽媽實現的。我們握住管子的兩頭，我的這個管子只能透過管子左面的口子放入東西，也只能從左面的口子取出東西。右面的口子是不開的。而弟弟佇列呢，他的管子的左面的口子放東西，管子的右面的口子取東西。
上面說過了，棧和佇列都是可以透過陣列或者連結串列實現的。當然了，父母創造孩子，天經地義嘛。那麼，先來看看我是如何實現的。作為一種資料結構，我介面有isEmpty()、size()、push()、pop()、peek()以及迭代。
先來看看如何透過陣列實現棧：
public class Stack- implements Iterable
- {
private Item[] a; // 陣列表示棧，棧頂在最大的下標。
private int n; // 棧內元素的個數
/**
* 初始化一個空棧
*/
public Stack() {
a = (Item[]) new Object[2];
n = 0;
}
/**
* 判斷棧內是否有元素
*/
public boolean isEmpty() {
return n == 0;
}
/**
* 傳回棧內元素個數
*/
public int size() {
return n;
}
// 改變棧的大小
private void resize(int capacity) {
assert capacity >= n;
// 註意不能直接建立泛型陣列
Item[] temp = (Item[]) new Object[capacity];
for (int i = 0; i < n; i++) {
temp[i] = a[i];
}
a = temp;
// 也可以選擇下麵這種方式改變陣列大小
// a = java.util.Arrays.copyOf(a, capacity);
}
/**
* 壓入元素
*/
public void push(Item item) {
//先判斷n的大小，如果棧滿則改變棧的大小
if (n == a.length) resize(2*a.length);
a[n++] = item;
}
/**
* 彈出並傳回元素
*/
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = a[n-1];
a[n-1] = null; //防止物件遊離
n--;
// 如果有必要則調整棧的大小
if (n > 0 && n == a.length/4) resize(a.length/2);
return item;
}
/**
* 傳回但不彈出棧頂元素
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return a[n-1];
}
/**
* 傳回一個可以進行先進後出迭代的迭代器
*/
public Iterator- iterator() {
return new ReverseArrayIterator();
}
// 用內部類實現迭代器介面，實現從棧頂往棧底的先進後出迭代，沒有實現remove()方法。
private class ReverseArrayIterator implements Iterator- {
private int i;
public ReverseArrayIterator() {
i = n-1;
}
public boolean hasNext() {
return i >= 0;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i--];
}
}
/**
* 測試
*/
public static void main(String[] args) {
Stack stack = new Stack();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) stack.push(item);
else if (!stack.isEmpty()) StdOut.print(stack.pop() + " ");
}
StdOut.println("(" + stack.size() + " left on stack)");
}
}
再來看看如何使用連結串列實現棧：
public class Stack- implements Iterable
- {
private Node- first; //棧頂節點
private int N; // 棧內元素數量
// 輔助類Node，用於形成連結串列
private static class Node- {
private Item item;
private Node- next;
}
/**
* 初始化棧
*/
public Stack() {
first = null;
N = 0;
}
/**
* 判斷棧是否為空
*/
public boolean isEmpty() {
return first == null;
//return N == 0;
}
/**
* 傳回棧內元素數量
*/
public int size() {
return N;
}
/**
* 壓入元素
*/
public void push(Item item) {
Node- oldfirst = first;
first = new Node- ();
first.item = item;
first.next = oldfirst;
N++;
}
/**
* 彈出元素
*/
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // 需彈出的元素
first = first.next; // 刪除頭節點
N--;
return item;
}
/**
* 傳回但不彈出元素
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
/**
* 從棧頂到棧底列印元素
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
/**
* 實現Iterable介面
*/
public Iterator- iterator() {
return new ListIterator- (first);
}
// 實現Iterator介面用於迭代，沒有實現remove方法
private class ListIterator- implements Iterator
- {
private Node- current;
//初始化時，current指向棧頂
public ListIterator(Node- first)
{
current = first;
}
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
/**
* 測試
*/
public static void main(String[] args) {
Stack s = new Stack();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) s.push(item);
else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
}
StdOut.println("(" + s.size() + " left on stack)");
}
}
同樣作為資料結構的弟弟，也有些介面需要實現：isEmpty()、size()、enqueue()、dequeue()、peek()以及迭代。佇列和棧不同的是，入列和出列是在兩個地方，所以需要維護兩個變數來表示隊頭和隊尾。
使用陣列實現佇列：
public class Queue- implements Iterable
- {
private Item[] q;
private int N; // 佇列中元素的數量
private int first; // 隊頭元素的下標
private int last; // 隊尾元素的後一個位置的下標，也就是元素入列時可以放置的位置
/**
* 初始化佇列，此時頭尾下標重合
*/
public Queue() {
q = (Item[]) new Object[2];
N = 0;
first = 0;
last = 0;
}
/**
* 依舊用N判斷佇列是否為空
*/
public boolean isEmpty() {
return N == 0;
}
/**
* 佇列中元素數量
*/
public int size() {
return N;
}
// 調整陣列大小
private void resize(int max) {
assert max >= N;
Item[] temp = (Item[]) new Object[max];
//註意這裡：把N個元素放入總大小為max的佇列（max>=N）
//因為迴圈使用陣列，從first開始的第i個元素可能儲存在了first
//前面（即last在first前面）。
for (int i = 0; i < N; i++) {
temp[i] = q[(first + i) % q.length];
}
q = temp;
//把小佇列按順序複製到大佇列後重置隊頭和隊尾
first = 0;
last = N;
}
/**
* 元素入列
*/
public void enqueue(Item item) {
if (N == q.length) resize(2*q.length);
q[last++] = item; // 元素入列
if (last == q.length) last = 0; // 如果last超出陣列下標，把last置零，迴圈利用陣列
N++;
}
/**
* 元素出列
*/
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = q[first];
q[first] = null; // 防止物件遊離
N--;
first++;
if (first == q.length) first = 0; // 迴圈利用陣列，下一個隊頭在下標為0的地方
if (N > 0 && N == q.length/4) resize(q.length/2);
return item;
}
/**
* 傳回隊頭元素但不出列
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return q[first];
}
/**
* 實現Iterable介面
*/
public Iterator- iterator() {
return new ArrayIterator();
}
//實現迭代器
private class ArrayIterator implements Iterator- {
//維護一個i用於迭代
private int i = 0;
public boolean hasNext() { return i < N; }
public void remove() { throw new UnsupportedOperationException(); }
//直接利用first進行遍歷，註意可能存在陣列的迴圈利用
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = q[(i + first) % q.length];
i++;
return item;
}
}
/**
* 測試
*/
public static void main(String[] args) {
Queue q = new Queue ();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) q.enqueue(item);
else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
}
StdOut.println("(" + q.size() + " left on queue)");
}
}
使用連結串列實現佇列：
public class Queue<Item> implements Iterable<Item> {
private Node- first; // 隊頭節點
private Node- last; // 隊尾節點（註意和上面的last區分，last並不是隊尾元素的下標）
private int N; // 佇列元素的數量
// 輔助類Node
private static class Node<Item> {
private Item item;
private Node- next;
}
/**
* 初始化佇列
*/
public Queue() {
first = null;
last = null;
N = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
/**
* 傳回但不刪除頭元素
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
/**
* 元素入列
*/
public void enqueue(Item item) {
//記錄尾節點
Node- oldlast = last;
//建立新的尾節點
last = new Node- ();
last.item = item;
last.next = null;
//如果佇列是空的，將first置為last，因為這時候佇列中只有一個元素
if (isEmpty()) first = last;
//否則執行正常的在尾節點插入新節點的操作
else oldlast.next = last;
N++;
}
/**
*元素出列
*/
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
//隊頭元素出列
Item item = first.item;
first = first.next;
N--;
//如果這時候佇列為空，表示原來只有一個元素，這時候也將last置為null
if (isEmpty()) last = null;
return item;
}
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
public Iterator- iterator()
{
return new ListIterator- (first);
}
// 實現迭代
private class ListIterator<Item> implements Iterator<Item> {
private Node- current;
//要實現迭代，我們只需要維護一個節點，併在開始的時候將它置為first
public ListIterator(Node- first)
{
current = first;
}
public boolean hasNext() { return current != null;}
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
/**
* 測試
*/
public static void main(String[] args) {
Queue q = new Queue();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) q.enqueue(item);
else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
}
StdOut.println("(" + q.size() + " left on queue)");
}
}
我是一個棧，我的雙胞胎弟弟叫佇列。我的爸爸是陣列，我的媽媽是連結串列。 你們可以使用陣列和連結串列來實現棧和佇列。
好了，今天關於我和我的家族的故事就先給你介紹到這裡了。偷偷告訴你一個秘密，其實我和弟弟之間是可以互相轉換的。也就是說可以使用棧來實現佇列，同樣也可以使用佇列來實現棧。關於這個小秘密，我下次再給你介紹哦。
PS：本文參考了部分網路文章，由於公眾號限制無法新增連結，請至原文檢視參考資料。–
●編號666，輸入編號直達本文
●輸入m獲取文章目錄
演演算法與資料結構
更多推薦《18個技術類公眾微信》
涵蓋：程式人生、演演算法與資料結構、駭客技術與網路安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。
