# 順序棧與鏈?zhǔn)綏５膱D解與實現(xiàn)

• 棧是一種特殊的線性表，它與線性表的區(qū)別體現(xiàn)在增刪操作上
• 棧的特點是先進后出，后進先出，也就是說棧的數(shù)據(jù)操作只能發(fā)生在末端，而不允許在中間節(jié)點進行操作

• 如上圖所示，對棧的增刪操作都只能在末端也就是棧頂操作，
• 棧既然是線性表那么就存在表頭和表尾，不過在棧結(jié)構(gòu)中，對其都進行限制改造，表尾用來輸入數(shù)據(jù)也叫做棧頂（top）,相應(yīng)的 表頭就是棧底（bottom），棧頂和棧頂是兩個指針用來表示這個棧
• 與線性表類似，棧也是又順序表示和鏈?zhǔn)奖硎?，分別稱作順序棧和鏈棧

棧的基本操作

• 如何通過棧這個后進先出的線性表，來實現(xiàn)增刪查呢？
• 初始時，棧內(nèi)沒有數(shù)據(jù)，即空棧。此時棧頂就是棧底。
• 當(dāng)存入數(shù)據(jù)時，最先放入的數(shù)據(jù)會進入棧底。接著加入的數(shù)據(jù)都會放入到棧頂?shù)奈恢谩?/li>
• 如果要刪除數(shù)據(jù)，也只能通過訪問棧頂?shù)臄?shù)據(jù)并刪除。對于棧的新增操作，通常也叫作 push或壓棧。
• 對于棧的刪除操作，通常也叫作 pop或出棧。對于壓棧和出棧，我們分別基于順序棧和鏈棧來分析

順序棧

• 順序棧即就是順序存儲元素的，通常順序棧我們可以通過數(shù)組來實現(xiàn)，將數(shù)組的首元素放在棧底，最后一個元素放在棧頂，之后指定一個 top 指針指向棧頂元素的位置
• 當(dāng)棧中只有一個元素是，此時 top=0 ，一般以 top 是否為 -1 來判定是否為空棧，當(dāng)定義了棧的最大容量時，則棧頂 top 必須小于最大容量值
• 下面我們通過 Java 代碼實現(xiàn)一個順序棧,非常簡單如下：

/**
 * @url: i-code.online
 * @author: 云棲簡碼
 * @time: 2020/12/8 16:48
 */
public class Stack<T> {

    private Object[] stack;
    private int stackSize;
    private int top = -1;

    public Stack(int size){
        stackSize = size;
        stack = new Object[size];
    }

    public void push(T value){
        if (top < stackSize-1){
            top++;
            stack[top] = value;
            return;
        }
        throw new ArrayIndexOutOfBoundsException(top +"越界");
    }

    public T pop(){
        if (top > -1){
            top--;
           return (T) stack[top+1];
        }
        throw new ArrayIndexOutOfBoundsException(top +"越界");
    }

    public boolean empty(){
        return top == -1;
    }

}

• 當(dāng)需要新增數(shù)據(jù)元素，即入棧操作時，就需要將新插入元素放在棧頂，并將棧頂指針增加 1。如下圖所示：

  
  
  數(shù)據(jù)結(jié)構(gòu) (1).png
• 刪除數(shù)據(jù)元素，即出棧操作，只需要 top-1 就可以了。

對于查找操作，棧沒有額外的改變，跟線性表一樣，它也需要遍歷整個棧來完成基于某些條件的數(shù)值查找,上述代碼中并未去實現(xiàn)該功能

鏈棧

• 關(guān)于鏈?zhǔn)綏?，就是用鏈表的方式對棧的表示。通常，可以把棧頂放在單鏈表的頭部，如下圖所示。由于鏈棧的后進先出，原來的頭指針就顯得毫無作用了。因此，對于鏈棧來說，是不需要頭指針的。相反，它需要增加指向棧頂?shù)?code>top 指針，這是壓棧和出棧操作的重要支持。

數(shù)據(jù)結(jié)構(gòu) (2).png

• 對于鏈表我們添加都是在其后追加，但是對于鏈棧，新增數(shù)據(jù)的壓棧操作需要額外處理的，就是棧的 top 指針。如下圖所示，插入新的數(shù)據(jù)放在頭部，則需要讓新的結(jié)點指向原棧頂，即 top 指針指向的對象，再讓 top 指針指向新的結(jié)點。

數(shù)據(jù)結(jié)構(gòu) (3).png

• 在鏈?zhǔn)綏Ｖ羞M行刪除操作時，只能在棧頂進行操作。因此，將棧頂?shù)?top 指針指向棧頂元素的 next 指針即可完成刪除。對于鏈?zhǔn)綏碚f，新增刪除數(shù)據(jù)元素沒有任何循環(huán)操作，其時間復(fù)雜度均為 O(1)。
• 通過代碼簡單實現(xiàn)棧的操作，如下：

/**
 * @url: i-code.online
 * @author: 云棲簡碼
 * @time: 2020/12/8 20:57
 */
public class LinkedList<E> {


    private Node<E> top = new Node<>(null,null);


    public void push(E e){
        Node<E> node = new Node<>(e,top.next);
        top.next = node;
    }

    public E pop(){
        if (top.next == null){
            throw new NoSuchElementException();
        }
        final Node<E> next = top.next;
        top.next = next.next;
        return next.item;
    }



    private static class Node<E>{
        E item;
        Node<E> next;

        public Node(E item, Node<E> next){
            this.item = item;
            this.next = next;
        }
    }

}

對于查找操作，相對鏈表而言，鏈棧沒有額外的改變，它也需要遍歷整個棧來完成基于某些條件的數(shù)值查找。

• 不管是順序棧還是鏈棧，數(shù)據(jù)的新增、刪除、查找與線性表的操作原理極為相似，時間復(fù)雜度完全一樣，都依賴當(dāng)前位置的指針來進行數(shù)據(jù)對象的操作。區(qū)別僅僅在于新增和刪除的對象，只能是棧頂?shù)臄?shù)據(jù)結(jié)點。

棧的案例

• 我們可以通過一個案例來看棧的具體使用，這里選取 leetcode 上的案例來練習(xí)，如下

有效括號

• 給定一個只包括 '('，')'，'{'，'}'，'['，']'的字符串，判斷字符串是否有效。有效字符串需滿足：左括號必須與相同類型的右括號匹配，左括號必須以正確的順序匹配。例如，{ [ ( ) ( ) ] }是合法的，而{ ( [ ) ] }是非法的。
• 這個問題很適合采用棧來處理。原因是，在匹配括號是否合法時，左括號是從左到右依次出現(xiàn)，而右括號則需要按照“后進先出”的順序依次與左括號匹配。因此，實現(xiàn)方案就是通過棧的進出來完成。
• 具體的實現(xiàn)思路，我們可以遍歷字符串從左起，當(dāng)遇到左括號時進行壓榨操作，而到遇到右括號時則繼續(xù)出棧，判斷出棧的括號是否與當(dāng)前的右括號是一對，如果不是則非法，如果一致則繼續(xù)遍歷直到結(jié)束
• 代碼如下：

public boolean isValid(String s) {
        Stack stack = new Stack();
        for(int i =0;i<s.length();i++){
            char curr = s.charAt(i);
            if (isLeft(curr)) {
                stack.push(curr);
            }else {
                if (stack.empty())
                    return false;
                if (!isPair(curr,(char)stack.pop())){
                    return false;
                }
            }
        }
        if (stack.empty()){
            return true;
        }else {
            return false;
        }

    }

    public boolean isPair(char curr,char expt){
        if ((expt == '[' && curr == ']') || (expt == '{' && curr == '}') || (expt == '(' && curr == ')'))
            return true;
        return false;
    }

    public boolean isLeft(char c){
        if (c == '{' || c == '[' || c == '(')
            return true;
        return false;
    }

總結(jié)

• 棧繼承了線性表特性，是一個特殊的線性表
• 棧只允許數(shù)據(jù)從棧頂進出，即棧的特性先進后出
• 不管是順序棧還是鏈?zhǔn)綏＃鼈儗τ跀?shù)據(jù)的新增操作和刪除操作的時間復(fù)雜度都是O(1)。而在查找操作中，棧和線性表一樣只能通過全局遍歷的方式進行，也就是需要O(n) 的時間復(fù)雜度
• 當(dāng)我們面臨頻繁增刪節(jié)點，同時數(shù)據(jù)順序有后來居上的特點時棧就是個不錯的選擇。例如，瀏覽器的前進和后退，括號匹配等問題

<a name="vki7l"></a>

推薦閱讀

• 《Java并發(fā)編程-線程基礎(chǔ)》
• 《總算把線程六種狀態(tài)的轉(zhuǎn)換說清楚了！》
• 《[高頻面試]解釋線程池的各個參數(shù)含義》
• 《知道線程池的四種拒絕策略嗎?》
• 《java中常見的六種線程池詳解》
• 《基于synchronized的鎖的深度解析》??推薦
• 《JAVA中常見的阻塞隊列詳解》
• 《優(yōu)雅關(guān)閉線程池的方案》

<br />

本文由AnonyStar 發(fā)布,可轉(zhuǎn)載但需聲明原文出處。
更多文章關(guān)注筆者博客 ：云棲簡碼 i-code.online