手把手教你實現棧以及C#中Stack源碼分析

2021 年 9 月 22 日
筆記
算法

定義

棧又名堆棧，是一種操作受限的線性表，僅能在表尾進行插入和刪除操作。

它的特點是先進後出，就好比我們往桶裏面放盤子，放的時候都是從下往上一個一個放（入棧），取的時候只能從上往下一個一個取（出棧），這個比喻並非十分恰當，比如拿盤子的時候只是習慣從上面開始拿，也可以從中間拿，而棧的話是只能操作最上面的元素，這樣比喻只是為了便於了解。

剛開始接觸棧可能會有些疑問，我們已經有數組和鏈表了，為什麼還要棧這個操作受限制的數據結構呢？數組和鏈表雖然靈活，但是操作起來也更容易出錯，而棧因為操作受限，在特定場景中使用還是有優勢的。

當某個數據集合只涉及在一端插入和刪除數據，並且滿足先進後出的特性時，我們就應該首選「棧」這種數據結構。

棧的實現

棧的實現方式有兩種，一種是基於數組實現的順序棧，另一種是基於鏈表實現的鏈式棧。它的主要操作也就兩個，即入棧和出棧，難度並不大😏。

先了解一下入棧（Push）和出棧（Pop），如下圖

順序棧

基於數組實現，就面臨著數組大小固定、擴容成本大的問題，下面是使用C#實現出棧和入棧簡單功能代碼。

    // 基於數組實現的順序棧
    public class ArrayStack
    {
        private string[] items;  // 數組
        private int count;       // 棧中元素個數
        private int n;           //棧的大小

        // 初始化數組，申請一個大小為n的數組空間
        public ArrayStack(int n)
        {
            this.items = new string[n];
            this.n = n;
            this.count = 0;
        }

        // 入棧操作
        public bool Push(string item)
        {
            // 數組空間不夠了，直接返回false，入棧失敗。
            if (count == n) return false;
            // 將item放到下標為count的位置，並且count加一
            items[count] = item;
            ++count;
            return true;
        }

        // 出棧操作
        public string Pop()
        {
            // 棧為空，則直接返回null
            if (count == 0) return null;
            // 返回下標為count-1的數組元素，並且棧中元素個數count減一
            string tmp = items[count - 1];
            --count;
            return tmp;
        }
    }

上面代碼有一些很明顯的缺點，比如存儲的數據類型固定為string(C#中使用泛型可以很好的解決)，大小固定…這只是簡單的功能演示，後面分析C#中Stack源碼時這些問題都會被化解。

出棧和入棧的時間複雜度是多少呢？這個很好計算，因為出棧和入棧都只涉及棧頂的元素，所以是O(1)。

空間複雜度呢？還是O(1),因為這裡只額外使用了count和n兩個臨時變量。

💁‍♂ 空間複雜度是指除了原本的數據存儲空間外，算法運行還需要額外的存儲空間。例子中大小為n的數組是無法省略的，也就是說這n個空間是必須的，對複雜度不了解的可以點擊查看一文搞定算法複雜度分析。

鏈式棧

話不多說，上代碼

    // 鏈表實現棧
    public class LinkStack<T>
    {
        //棧頂指示器
        public Node<T> Top { get; set; }

        //棧中結點的個數
        public int NCount { get; set; }

        //初始化
        public LinkStack()
        {
            Top = null;
            NCount = 0;
        }

        //獲取棧的長度
        public int GetLength()
        {
            return NCount;
        }

        //判斷棧是否為空
        public bool IsEmpty()
        {
            if ((Top == null) && (0 == NCount))
            {
                return true;
            }
            return false;
        }

        //入棧
        public void Push(T item)
        {
            Node<T> p = new Node<T>(item);
            if (Top == null)
            {
                Top = p;
            }
            else
            {
                p.Next = Top;
                Top = p;
            }
            NCount++;
        }

        //出棧
        public T Pop()
        {
            if (IsEmpty())
            {
                return default(T);
            }
            Node<T> p = Top;
            Top = Top.Next;
            --NCount;
            return p.Data;
        }
    }

    //結點定義
    public class Node<T>
    {
        public T Data;

        public Node<T> Next;

        public Node(T item)
        {
            Data = item;
        }
    }

時間複雜度和空間複雜度均為O(1).

C#中Stack源碼分析

前面我們已經知道了順序棧和鏈式棧的優缺點，那麼C#語言中自帶的Stack是基於什麼實現的呢？

答案是順序棧。Stack是一個泛型類，裏面定義了一個泛型數組用以存儲數據

    private T[] _array;

既然是一個順序棧，為什麼在使用的過程中什麼不需要初始化數組大小，也不用擔心擴容問題呢？

當我們實例化Stack的時候，會調用它的構造函數，初始化數組大小為0.

    public Stack()
    {
        _array = _emptyArray;
        _size = 0;
        _version = 0;
    }

向數組中添加元素時，會檢測數組是否還有空閑容量，如果超出數組大小，將進行擴容

    public void Push(T item)
    {
        if (_size == _array.Length)
        {
            T[] array = new T[(_array.Length == 0) ? 4 : (2 * _array.Length)];
            Array.Copy(_array, 0, array, 0, _size);
            _array = array;
        }

        _array[_size++] = item;
        _version++;
    }

正是因為C#幫我們封裝好了，所以我們使用起來才感覺如此的方便。

Push()函數的時間複雜度是多少呢？當棧中有空閑空間時，可以直接添加，它的時間複雜度是O(1)。但當內存不夠需要擴容時，需要重新申請內存，進行數據搬移，所以時間複雜度就變成了O(n)，其平均時間複雜度也為O(1).

總結

Tags: 算法