數(shù)據(jù)結(jié)構(gòu)與算法--棧

我們可能都有這樣的經(jīng)歷：小時候交作業(yè)，放到老師的講臺上。先交的作業(yè)的肯定會在最底下，最后幾個交的同學(xué)可能就有點小動作了，總是喜歡把自己的作業(yè)塞到底下或者中間，因為最后交的作業(yè)必然位于最上面，也就是最顯眼的地方，老師批改時，拿出的第一份作業(yè)就是他的。這樣一摞作業(yè)，最后放的在最頂上，會被先拿走；先放的在最底下，最后才被拿走。像這類先進后出（LIFO即Last In First Out）的數(shù)據(jù)結(jié)構(gòu)稱為棧。

棧有個棧頂的說法，棧頂是允許數(shù)據(jù)操作的地方，一般的操作就是push和pop，分別叫做進棧和出棧。棧本身是一個線性表，所以也有順序存儲和鏈式存儲兩種結(jié)構(gòu)。

順序棧--數(shù)組實現(xiàn)

棧的順序存儲結(jié)構(gòu)可以用數(shù)組實現(xiàn)。那么數(shù)組的哪一頭作為棧頂呢？顯然數(shù)組的尾部作為棧頂比較好，因為在數(shù)組的尾部插入、移除數(shù)據(jù)都十分容易（時間復(fù)雜度為O(1)），而在數(shù)組頭部a[0]進行數(shù)據(jù)操作，將會有大量的元素移動...

push操作實際上就是在數(shù)組尾部（棧頂）添加元素，而pop則是把最新添加元素從數(shù)組尾部彈出。還可以定義一個peek方法，只是獲得棧頂?shù)脑?strong>而不彈出。至于代碼的實現(xiàn)，直接拿以前線性表順序存儲結(jié)構(gòu)的代碼稍微改改就行，比如add方法直接改成push就能用。

package Chap4;

import java.util.Iterator;


public class MyStack<Item> implements Iterable<Item> {

    // 初始化為長度為1，方便第一次push的時候可以訪問a[0]這個下標
    private Item[] a = (Item[]) new Object[1];

    private int N;

    public MyStack(Item... items) {
        for (int i = 0; i < items.length; i++) {
            push(items[i]);
        }
    }


    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];

        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        // 將容量大于N的數(shù)組傳給a
        a = temp;
    }

    public void push(Item item) {
        if (N == a.length) {
            resize(a.length * 2);
        }
        a[N++] = item;
    }

    public Item pop() {
        Item item = a[--N];
        // 自減去后現(xiàn)在N為N-1
        a[N] = null;
        if (N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

    public Item peek() {
        return a[N - 1];
    }

    // N=0但是a.length不為0，可以再次add
    public void clear() {
        for (int i = 0; i < N; i++) {
            a[i] = null;
        }
        N = 0;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReveredIterator();
    }

    private class ReveredIterator implements Iterator<Item> {

        private int i = N;
        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public Item next() {
            return a[--i];
        }
    }

    @Override
    public String toString() {
        Iterator<Item> it = iterator();
        if (!it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");

        while (true) {
            Item item = it.next();
            sb.append(item);
            if (!it.hasNext()) {
                return sb.append("]").toString();
            }
            sb.append(", ");
        }
    }

    public static void main(String[] args) {
        MyStack<String> a = new MyStack<>();
        a.push("I");
        a.push("have");
        a.push("a");
        a.push("dream.");
        System.out.println(a);
        a.pop(); // dream.
        a.push("pig.");
        System.out.println(a.peek());
        System.out.println(a);
        // 變成空棧
        a.clear();
        System.out.println(a.size()); // 0
    }
}

鏈棧--鏈表實現(xiàn)

棧當然可以用鏈表實現(xiàn)。由于單鏈表有一個first指針始終指向鏈表的第一個結(jié)點。我們很容易想到將其用為棧頂指針。這樣鏈表的頭部就是棧頂。

直接使用以前寫過的單鏈表代碼，去掉last尾指針就好。

package Chap4;

import java.util.Iterator;

public class MyStack2<Item> implements Iterable<Item> {

    private class Node {
        Item data;
        Node next;
    }

    // 指向第一個節(jié)點
    private Node first;
    private int N;

    public MyStack2(Item... items) {
        for (Item item : items) {
            push(item);
        }
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    // 表頭插入元素
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.data = item;
        first.next = oldfirst;

        N++;
    }

    // 刪除表頭元素
    public Item pop() {
        Item item = first.data;
        Node next = first.next;
        // 這兩行有助于垃圾回收
        first.data = null;
        first.next = null;
        first = next;
        N--;
        return item;
    }

    public Item peek() {
        return first.data;
    }

    public void clear() {
        while (first != null) {
            Node next = first.next;
            // 下面兩行幫助垃圾回收
            first.next = null;
            first.data = null;
            first = next;
        }
        N = 0;
    }

    @Override
    public String toString() {
        Iterator<Item> it = iterator();

        if (!it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (true) {
            Item item = it.next();
            sb.append(item);
            if (!it.hasNext()) {
                return sb.append("]").toString();
            }

            sb.append(", ");
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private Node current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public Item next() {
                Item item = current.data;
                current = current.next;
                return item;
            }
        };
    }

    public static void main(String[] args) {
        MyStack2<String> a = new MyStack2<>("I", "have", "a", "dream.");
        System.out.println(a);
        a.pop();
        a.push("pig.");
        System.out.println(a.peek());
        a.clear();
        System.out.println(a.isEmpty());
    }
}

比較順序棧和鏈棧，操作數(shù)據(jù)的時間復(fù)雜度都是O(1)。由于順序棧的實現(xiàn)采用了適應(yīng)容量的手段，所以我們也不用擔心數(shù)據(jù)量過大導(dǎo)致上溢。但是每次resize調(diào)整容量，每次都會增大一倍空間，當數(shù)據(jù)量較大時，這會是個很大的數(shù)字！如果我們拿捏不準數(shù)據(jù)具體有多少，浪費內(nèi)存空間幾乎時避免不了的。但鏈棧不用擔心這個問題，它是新添加一個結(jié)點，才開辟一份內(nèi)存，但是由于每個結(jié)點都含有指針域Node，這也會增大一部分內(nèi)存開銷。所以在這兩種實現(xiàn)結(jié)構(gòu)如何選擇，主要看待處理的數(shù)據(jù)量。一般來說，如果數(shù)據(jù)不可預(yù)測且量比較大，使用鏈棧更好，如果數(shù)據(jù)在可控范圍內(nèi)且量不大，使用順序棧也許好一些。

兩棧共享空間

使用resize方法調(diào)整容量的手段可謂有利有弊?？偟膩碚f還是利大于弊的。浪費些內(nèi)存總比有時候溢出好啊。如果規(guī)定了容量為500，那么就怎么也存不進第501個元素，很蛋疼。如果不使用resize手段，有沒有其他方法呢？可使用一個數(shù)組存放兩個棧的內(nèi)容，中間未使用的區(qū)域兩個棧中任一個都可以自由使用，這稱為兩棧共享空間。這要求我們兩個棧的數(shù)據(jù)類型一致（肯定嘛，放在同一個數(shù)組里當然得一致）。示意圖如下

使用兩個指針分別表示兩棧的棧頂，top1為棧1的棧頂，位于數(shù)組的左半部分；top2為棧2的棧頂，在數(shù)組的右半部分。

空棧的情況：

• 棧1空，則top1在數(shù)組頭部以前，為-1，隨著元素的添加，top1向后挪動，值遞增。
• 棧2空，則top2在數(shù)組尾部之后，為a.length，隨著元素的添加，top2向左挪動，值遞減。
• 兩棧都空，top1為-1，top2為a.length。

滿棧的情況：

• 普通情況：top1和top2相鄰（相遇），即滿足top1 + 1 == top2。想象一下，此時兩棧之間已經(jīng)沒有共享空間了。無法再添加元素。

• 棧1滿，棧2空。top1 = a.length - 1而top2 = a.length同樣滿足普通情況下的等式條件。
• 棧2滿，棧1空。top1 = -1而top2 = 0同樣滿足普通情況下的等式。

綜上滿棧的時候使用條件top1 + 1 == top2判斷即可。

先上代碼

package Chap4;

public class SharedStack<Item> {

    private Item[] a;
    // 棧頂
    private int top1;
    private int top2;

    public SharedStack(int maxsize) {
        if (maxsize <= 0) {
            maxsize = 512;
        }

        a = (Item[]) new Object[maxsize];
        top1 = -1;
        top2 = a.length;
    }

    public SharedStack() {
        this(512);
    }

    public boolean isEmpty(int stackNumber) {
        if (stackNumber == 1) {
            return top1 == -1;
        } else if (stackNumber == 2) {
            return top2 == a.length;
        }
        return true;
    }

    public int size(int stackNumber) {
        if (stackNumber == 1) {
            return top1 + 1;
        } else if (stackNumber == 2) {
            return a.length - top2;
        }
        return 0;
    }

    public void push(int stackNumber, Item item) {
        // 棧已滿的狀態(tài)，不能再添加
        // 先判斷這句，下面的就能正確處理了
        if (top1 + 1 == top2) {
            throw new RuntimeException("棧已滿！");
        } else if (stackNumber == 1) {
            a[++top1] = item;
        } else if (stackNumber == 2) {
            a[--top2] = item;
        }
    }

    // 選擇彈出哪個棧的數(shù)據(jù)
    public Item pop(int stackNumber) {
        Item item = null;
        if (stackNumber == 1) {
            // 棧1空了
            if (top1 == -1) {
                throw new RuntimeException("棧1已空！");
            } else {
                item = a[top1--];
            }
        } else if (stackNumber == 2) {
            // 棧2空了
            if (top2 == a.length) {
                throw new RuntimeException("棧2已空！");
            } else {
                item = a[top2++];
            }
        }
        return item;
    }

    public String displayStack(int stackNumber) {
        if (stackNumber == 1) {
            if (top1 == -1) {
                return "[]";
            }
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int j = top1; j >= 0; j--) {
                sb.append(a[j]);
                if (j == 0) {
                    return sb.append("]").toString();
                } else {
                    sb.append(", ");
                }
            }
        } else if (stackNumber == 2) {
            if (top2 == a.length) {
                return "[]";
            }
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int j = top2; j < a.length; j++) {
                sb.append(a[j]);
                if (j == a.length - 1) {
                    return sb.append("]").toString();
                } else {
                    sb.append(", ");
                }
            }
        }
        return null;
    }

    public void clear(int stackNumber) {
        if (stackNumber == 1) {
            for (int j = top1; j >=0 ; j--) {
                a[j] = null;
            }
            top1 = -1;
        } else if (stackNumber == 2) {
            for (int j = top2; j < a.length; j++) {
                a[j] = null;
            }
            top2 = a.length;
        }
    }

    public void clearAll() {
        for (int i = 0; i < a.length; i++) {
            a[i] = null;
        }
        top1 = -1;
        top2 = a.length;
    }

    public static void main(String[] args) {
        SharedStack<String> a = new SharedStack<>();
        a.push(1, "a");
        a.push(1, "b");
        a.push(1, "c");
        a.push(1, "d");
        a.push(2, "4");
        a.push(2, "3");
        a.push(2, "2");
        a.push(2, "1");
        a.pop(2); // 1
        a.pop(1); // d
        System.out.println(a.size(2)); // 3
        System.out.println(a.size(1)); // 3
        System.out.println(a.displayStack(1)); // [c, b, a]
        System.out.println(a.displayStack(2)); // [2, 3, 4]
        a.clear(1);
        a.push(1,"a");
        System.out.println(a.displayStack(1)); // [a]
        a.clearAll();
        System.out.println(a.size(2)); // 0
    }
}

主要思想都是利用傳入的stackNumber參數(shù)選擇一個棧進行操作。clearAll則清空所有棧到初始化狀態(tài)。

push方法，注意是++top1和--top2，一開始這兩個指針并沒有指向數(shù)組（位于數(shù)組之外的兩端），所以要先自增。而pop方法中使用top1--和top2++后自增是因為top1和top2指向的就是將要被彈出棧的元素。再就是注意push方法剛開始要先判斷是否滿棧，之后進行下面的操作時才不會出錯。pop方法也要在自增自減的之前，判斷是否已是空棧。

特別注意棧長度的計算，由于使用了棧頂指針，而通過棧頂指針計算棧的長度十分簡單，就不必單獨創(chuàng)建兩個變量來存放棧的長度了。對于棧1，顯然top1 + 1正是棧的長度這對于top1 == -1表示棧空時同樣適用；對于棧2，a.length - top2正是棧的長度，這對于top2 == a.length?？諘r同樣適用。

可以看到兩棧共享空間還是有總?cè)萘?/strong>的限制，如果棧1和棧2同時增長，很快就會達到容量從而不能再添加元素到任何一個棧。但是光看一個棧，它的容量確實是動態(tài)變化的，只要還有共享空間可以使用。由此可見，兩棧共享空間的結(jié)構(gòu)最適合于一個棧增長另一個?？s短的情況，這樣容量還能暫時穩(wěn)定在一個范圍內(nèi)。