數據結構學習之棧

開篇：上次我們學習了基本的數組結構。

今天，我們來學習另一個線性的數據結構，棧。

棧這種數據結構，無時無刻不在我們的身邊。是種極其重要的數據結構。

所以，什麼是棧呢？(不要廢話了，快說)

先來看我們生活中，比如我們經常操作的word文檔。

我們比如寫入四個字， (天氣真好)。

我們不想要了這句話，Ctrl+Z 回撤掉我們所打的。你會很自然發現，消失的順序會是，好->真->氣->天。

別急。 我們再來個例子。

比如那我們的函數調用，

電腦需要有個系統棧來記錄我們的函數調用。

public void A()
{
        B();
}

public void B()
{
        C();
}

public void C()
{
        //....
}

A為我們的主函數，當A調用B的時候，進入B函數時，會在A函數中斷的位置把函數地址信息壓入到系統棧里。

此時B函數又在用掉C函數，此時又會在B函數中斷的位置把函數地址信息壓入到系統棧里。

此時C執行完後，該怎麼辦呢。此時系統棧里會取出棧頂元素為返回的地址，為B，程式便正確的回到B處。

同樣的。B執行完,系統棧又會取出棧頂元素為返回的地址，為A，程式便正確的回到A處。

此時我們正完成了我們的函數調用。

如我們的圖所示:

所以。棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。

插入和刪除都在棧頂這一端操作。

包括我們的經常使用編程的Ide，會自動檢查括弧的匹配等等。都是基於棧的結構。

現在，我們基於我們上次的線性數組。來實現我們的自定義棧結構。

我們讓我們的結構實現我們的泛型IStack介面來實現。

分別有pop出棧，push入棧。判斷是否為空和清空操作等。

/// <summary>
    /// 棧
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IStack<T>
    {
        void Push(T value);
        T Pop();
        T Peek();
        bool IsEmpty();
        void Clear();
    }

    public class Stack<T> : IStack<T>
    {
        private Array<T> Data;
        public Stack(int capacity=20)
        {
            this.Data = new Array<T>(capacity);
        }

        public void Clear()
        {
            this.Data.SetEmpty();
        }

        public bool IsEmpty()
        {
            return this.Data.GetSize() == 0;
        }

        public T Peek()
        {
            return this.Data.Search(this.Data.GetSize());
        }

        public T Pop()
        {
            return this.Data.Delete(this.Data.GetSize());
        }

        public void Push(T value)
        {
            this.Data.Add(value);
        }
    }

由此可見。這是一個重要的數據結構。

屆時，我們來看看leetcode上的一道典型的鏈表題目。20題

題目是這樣的。

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。

有效字元串需滿足：

左括弧必須用相同類型的右括弧閉合。
左括弧必須以正確的順序閉合。
註意空字元串可被認為是有效字元串。

先給出代碼(C#)。

public class Solution {
    public bool IsValid(string str) {
        var stack = new Stack();
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == '[' || str[i] == '{' || str[i] == '(')
                    stack.Push(str[i]);
                else if(str[i] == ']' || str[i] == '}' || str[i] == ')')
                {
                    if (stack.Count == 0)
                        return false;
                    var top = (char)stack.Pop();
                    if (str[i] == ')' && top != '(')
                        return false;
                    if (str[i] == ']' && top != '[')
                        return false;
                    if (str[i] == '}' && top != '{')
                        return false;
                }
            }
            return stack.Count==0;
    }
}

使用的Stack類為我們的C#本身為我們提供的棧結構。
本題目是 [，(,,{ 三種括弧的匹配。
我們判斷。如果是這三種，我們就相應的入棧。當遇到他們所匹配的結尾括弧時，],),}時候。
便相應的出棧。如果不是他們對應的標簽。便是不符合要求的。當一一遍歷出棧後。
如果棧為空時。便說明便是符合要求的。

今天我們的棧就到這裡啦，下一次，我們來實現另一種線性結構,隊列。