- 棧
- 可變長數組實作
- 連結清單實作
- 數組與連結清單的對比
- 隊列
下壓棧（簡稱棧）是一種基于後進後出（LIFO）政策的集合類型。這裡學習分别用數組和連結清單這兩種基礎資料結構來實作棧。
棧支援的基本操作有push,pop。
要用數組實作棧，可以聲明一個int型的标記，這個标記指向的位置即為棧頂，push操作時，将值放在資料中标記的位置，同時将标記+1，pop時，傳回數組在标記位置的值，同時标記-1。
但java中的數組在聲明的時候其長度就已經固定了，是以棧使用的空間隻能是這個數組最大容量的一部分。為了能容納更多的資料而聲明一個特别大的數組會非常浪費空間，那如何解決這個問題，達到既不會浪費數組空間也不會超出數組範圍呢？
可以采用動态調整數組大小的方式，在push操作導緻棧已滿時，重新建立一個數組，其容量為原數組的兩倍。同理在pop操作使數組的閑置空間達到一定程度時，重新建立一個容量更小的數組。但閑置的判斷标準不能為一半1/2，否則會造成在1/2的臨界點處push和pop操作時發生“抖動”，即頻繁地進行數組擴容、縮容操作，這會極大地降低棧的性能。是以通常的做法是在減少到數組容量的1/4時縮容為1/2。
實作可變長數組的代碼如下：
public class StackResizeArray<Item> {
private Item[] a; // array of items
private int n; // number of elements on stack
public StackResizeArray() {
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;
}
public void push(Item item) {
if (n == a.length)
resize(2 * a.length); // double size of array if necessary
a[n++] = item; // add item
}
public Item pop() {
if (isEmpty())
throw new NoSuchElementException("Stack underflow");
Item item = a[n - 1];
a[n - 1] = null; // to avoid loitering
n--;
// shrink size of array if necessary
if (n > 0 && n == a.length / 4)
resize(a.length / 2);
return item;
}
}
pop方法中，a[n - 1] = null将數組中已經出棧的位置設為null，是為了避免對象遊離，否則這個位置的對象雖然已經不在棧中，但還被數組引用着，導緻GC無法對其回收。
棧的另外一種實作方式是采用連結清單，連結清單是一種遞歸的資料結構，它或者為空，或者指向一個結點的引用，該結點含有一個泛型的元素和一個指向另一條連結清單的引用。
構成連結清單的基本結點可以為：
private static class Node<Item> {
public Item item;
public Node next;
}
其中泛型的item變量存放資料，同樣是Node類型的next變量用來指向下一個結點。将連結清單的頭部作為棧頂，push相當于在表頭插入元素，pop是從表頭删除元素。
代碼如下：
public class StackLinkedList<Item> {
private static class Node<Item> {
public Item item;
public Node next;
}
private Node<Item> first;
private int N;
private boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public void push(Item item) {
Node<Item> oldFirst = first;
first = new Node<Item>();
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;
}
}
數組與連結清單的差別決定了兩種棧實作的差別：
- 存取方式上，數組可以順序存取或者随機存取，而連結清單隻能順序存取；
- 存儲位置上，數組邏輯上相鄰的元素在實體存儲位置上也相鄰，而連結清單不一定；
- 存儲空間上，連結清單由于帶有指針域，存儲密度不如數組大；
- 按序号查找時，數組可以随機通路，需要的時間是常數，而連結清單不支援随機通路，需要的時間與資料規模成線性關系。
- 按值查找時，若數組無序，數組和連結清單時間複雜度均為O(n)，但是當數組有序時，可以采用折半查找将時間複雜度降為O(logn)；
- 插入和删除時，數組平均需要移動n/2個元素，而連結清單隻需修改指針即可；
- 空間配置設定方面： 雖然可變長數組可以擴充，但需要移動大量元素，導緻操作效率降低，而且如果記憶體中沒有更大塊連續存儲空間将導緻配置設定失敗； 連結清單存儲的節點空間隻在需要的時候申請配置設定，隻要記憶體中有空間就可以配置設定，操作比較靈活高效；
先進先出隊列（簡稱隊列）是一種基于先進先出(FIFO)政策的集合類型。這裡隻關注隊列的連結清單實作。與連結清單實作的棧類似，用結點包含泛型的item變量和next變量，前者存放資料，後者用來指向下一個結點。不同之處在于連結清單的頭部、尾部都會被操作，從連結清單的一端入隊(enqueue)，從另一端出隊(dequeue)
代碼：
public class Queue<Item> {
private static class Node<Item> {
public Item item;
public Node next;
}
private Node<Item> first;
private Node<Item> last;
private int N;
public void enqueue(Item item) {
Node<Item> oldLast = last;
last = new Node<Item>();
last.item = item;
if (isEmpty()) {
first = last;
} else {
oldLast.next = last;
}
N++;
}
public Item dequeue() {
if (isEmpty()) {
return null;
}
Item result = first.item;
first = first.next;
if (isEmpty()) {
last = null;
}
N--;
return result;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
}