一、定義

堆疊是計算機科學中抽象的資料結構，是一種基於先進後出的集合型別。如下圖所示，郵件放置在桌面時，使用的就是棧。當新的郵件來到時將它們放置在最上面。當需要閱讀時會一封一封地從上到下拿出來。

棧的操作

public class Stack<Item> implements Iterable<Item> {    Stack();  // create an empty stack    void push(Item item);  // add an item    Item pop();  // remove the most recently added item    boolean isEmpty();  // is the stack empty?    int size();  // number of items in the stack}

堆疊可以用陣列和連結串列兩種方式實現，為一個堆疊預先分配大小固定的空間並非難事，所以較流行的做法是Stack結構下含有一個數組，如果空間緊張，可以用連結串列代替。

棧的陣列實現在github.com網站wangrl2016/coding/algs4/StackArray.java檔案中。

其中push和pop兩個函式的核心程式碼

public void push(Item item) {    a[n++] = item;}public Item pop() {    Item item = a[n - 1];    a[n - 1] = null;    n--;    return item;}

棧的連結串列實現在github.com網站wangrl2016/coding/algs4/Stack.java檔案中。

其中push和pop兩個函式的核心程式碼

public void push(Item item) {    Node<Item> old = first;    first = new Node<>();    first.item = item;    first.next = old;    n++;}public Item pop() {    Item item = first.item;     // save item to return    first = first.next;     // delete first node    n--;    return item;            // return the saved item}