快捷導(dǎo)航

親自教你實現(xiàn)棧及C#中Stack源碼分析

更新時間：2021年09月23日 08:53:28 作者：天份&

大家都知道棧的實現(xiàn)方式有兩種，一種是基于數(shù)組實現(xiàn)的順序棧，另一種是基于鏈表實現(xiàn)的鏈式棧。這篇文章主要介紹了手把手教你實現(xiàn)棧以及C#中Stack源碼分析,需要的朋友可以參考下

定義

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

它的特點是先進后出，就好比我們往桶里面放盤子，放的時候都是從下往上一個一個放（入棧），取的時候只能從上往下一個一個?。ǔ鰲＃@個比喻并非十分恰當(dāng)，比如拿盤子的時候只是習(xí)慣從上面開始拿，也可以從中間拿，而棧的話是只能操作最上面的元素，這樣比喻只是為了便于了解。

剛開始接觸?？赡軙行┮蓡枺覀円呀?jīng)有數(shù)組和鏈表了，為什么還要棧這個操作受限制的數(shù)據(jù)結(jié)構(gòu)呢？數(shù)組和鏈表雖然靈活，但是操作起來也更容易出錯，而棧因為操作受限，在特定場景中使用還是有優(yōu)勢的。

當(dāng)某個數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足先進后出的特性時，我們就應(yīng)該首選“?！边@種數(shù)據(jù)結(jié)構(gòu)。

棧的實現(xiàn)

棧的實現(xiàn)方式有兩種，一種是基于數(shù)組實現(xiàn)的順序棧，另一種是基于鏈表實現(xiàn)的鏈式棧。它的主要操作也就兩個，即入棧和出棧，難度并不大😏。

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

順序棧

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

 // 基于數(shù)組實現(xiàn)的順序棧
    public class ArrayStack
    {
        private string[] items;  // 數(shù)組
        private int count;       // 棧中元素個數(shù)
        private int n;           //棧的大小

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

        // 入棧操作
        public bool Push(string item)
        {
            // 數(shù)組空間不夠了，直接返回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的數(shù)組元素，并且棧中元素個數(shù)count減一
            string tmp = items[count - 1];
            --count;
            return tmp;
        }
    }

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

出棧和入棧的時間復(fù)雜度是多少呢？這個很好計算，因為出棧和入棧都只涉及棧頂?shù)脑?，所以是O(1)。

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

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

鏈式棧

話不多說，上代碼

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

        //棧中結(jié)點的個數(shù)
        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;
        }
    }

    //結(jié)點定義
    public class Node<T>
    {
        public T Data;

        public Node<T> Next;

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

時間復(fù)雜度和空間復(fù)雜度均為O(1).

C#中Stack源碼分析

前面我們已經(jīng)知道了順序棧和鏈式棧的優(yōu)缺點，那么C#語言中自帶的Stack是基于什么實現(xiàn)的呢？

答案是順序棧。Stack是一個泛型類，里面定義了一個泛型數(shù)組用以存儲數(shù)據(jù)

private T[] _array;

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

當(dāng)我們實例化Stack的時候，會調(diào)用它的構(gòu)造函數(shù)，初始化數(shù)組大小為0.

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

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

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()函數(shù)的時間復(fù)雜度是多少呢？當(dāng)棧中有空閑空間時，可以直接添加，它的時間復(fù)雜度是O(1)。但當(dāng)內(nèi)存不夠需要擴容時，需要重新申請內(nèi)存，進行數(shù)據(jù)搬移，所以時間復(fù)雜度就變成了O(n)，其平均時間復(fù)雜度也為O(1).