棧一種常見(jiàn)的特殊線性數(shù)據(jù)結(jié)構(gòu)，其特殊之處在于其操作順序，下面會(huì)詳細(xì)介紹，也正因?yàn)槠涮匦�，因此�？梢暂p松解決表達(dá)式求值、括號(hào)匹配、遞歸算法、回溯算法等等問(wèn)題。

01 、定義

棧的特殊性表現(xiàn)為操作受限，其一只允許在棧的一端進(jìn)行元素插入和刪除運(yùn)算，其二棧的運(yùn)算操作遵循后進(jìn)先出（Last In First Out，簡(jiǎn)稱(chēng)LIFO）的原則。

入棧 ：當(dāng)把元素插入到棧，這一行為叫做入棧，也稱(chēng)進(jìn)棧或壓棧；

出棧 ：當(dāng)把元素從棧中移除，這一行為叫做出棧，也稱(chēng)退棧；

棧頂 ：允許元素進(jìn)行插入和刪除操作的一端稱(chēng)為棧頂；

棧底 ：與棧頂對(duì)應(yīng)的另一個(gè)端稱(chēng)為棧底，并且不允許進(jìn)行元素操作；

空棧 ：當(dāng)棧中沒(méi)有元素時(shí)叫做空棧。

滿棧 ：當(dāng)棧是有限容量，并且容量已用完，則稱(chēng)為滿棧。

棧容量 ：當(dāng)棧是有限容量，棧容量表示棧可以容納的最大元素?cái)?shù)量。

棧大小 ：表示當(dāng)前棧中的元素?cái)?shù)量。

02 、分類(lèi)

棧是邏輯結(jié)構(gòu)，因此以存儲(chǔ)方式的不同可以分為順序棧和鏈棧。

順序棧就是使用連續(xù)的地址空間存儲(chǔ)所有棧元素，通常采用數(shù)組實(shí)現(xiàn)，因此導(dǎo)致棧的大小是固定的，不易擴(kuò)擴(kuò)容，容易浪費(fèi)空間同時(shí)還要注意元素溢出等問(wèn)題。

鏈棧顧名思義就是采用鏈?zhǔn)椒绞酱鎯?chǔ)，通常采用單向鏈表實(shí)現(xiàn)，因此鏈�？梢詿o(wú)限擴(kuò)容，按需使用，內(nèi)存利用高效，同時(shí)也不存在滿棧的情況。

03 、實(shí)現(xiàn)（順序棧）

我們借助數(shù)組來(lái)實(shí)現(xiàn)順序棧，其核心思想是把數(shù)組的起始位置作為棧底，把數(shù)組尾方向當(dāng)作棧頂。

我們知道數(shù)組對(duì)插入、刪除元素是不友好的，因?yàn)樯婕暗揭汛嬖谠�素移�?dòng)的問(wèn)題，但是如果直接在數(shù)組尾端插入、刪除元素還是很方便的，因?yàn)椴簧婕霸�素移�?dòng)問(wèn)題，我們正是利用這一特點(diǎn)，把數(shù)組起始位置做為棧底，而插入、刪除方便的數(shù)組尾端作為棧頂。

下面我們將一步一步實(shí)現(xiàn)一個(gè)泛型順序棧。

1、ADT定義

我們首先來(lái)定義順序棧的ADT。

ADT Stack{

數(shù)據(jù)對(duì)象：D 是一個(gè)非空的元素集合，D = {a1, a2, ..., an}，其中 ai 表示棧中的第i個(gè)元素，n是棧的長(zhǎng)度。

數(shù)據(jù)關(guān)系：D中的元素通過(guò)它們的索引（位置）進(jìn)行組織，索引是從0到n-1的整數(shù)，并且遵循元素只能在棧頂操作，元素后進(jìn)先出的原則。

基本操作：[

Init(n) ：初始化一個(gè)指定容量的空棧。

Capacity：返回棧容量。

Length：返回棧長(zhǎng)度。

Top：返回棧頂元素，當(dāng)為空棧則報(bào)異常。

IsEmpty()：返回是否為空棧。

IsFull()：返回是否為滿棧。

Push()：入棧即添加元素，當(dāng)為滿棧則報(bào)異常。

Pop()：出棧即返回棧頂元素并把其從棧中移除，當(dāng)為空棧則報(bào)異常。

]

}

定義好棧ADT，下面我們就可以開(kāi)始自己實(shí)現(xiàn)的棧。

2、初始化Init

初始化結(jié)構(gòu)主要做幾件事。

• 初始化棧的容量；

• 初始化存放棧元素?cái)?shù)組；

• 初始化棧頂索引；

具體實(shí)現(xiàn)代碼如下：

//存放棧元素
private T[] _array;
//棧容量
private int _capacity;
//棧頂索引，為-1表示空棧
private int _top;
//初始化棧為指定容量
public MyselfArrayStack Init(int capacity)
{
    //初始化棧容量為capacity
    _capacity = capacity;
    //初始化指定長(zhǎng)度數(shù)組用于存放棧元素
    _array = new T[_capacity];
    //初始化為空棧
    _top = -1;
    //返回棧
    return this;
}

3、獲取棧容量 Capacity

這個(gè)比較簡(jiǎn)單直接把棧容量私有字段返回即可。

//棧容量
public int Capacity
{
    get
    {
        return _capacity;
    }
}

4、獲取棧長(zhǎng)度 Length

因?yàn)闂ｍ斔饕�表示�?shù)組下標(biāo)，因此可以通過(guò)棧頂索引加1轉(zhuǎn)為棧長(zhǎng)度，同時(shí)因?yàn)槲覀兌�義了空棧是棧頂索引為-1，因此此時(shí)棧長(zhǎng)等于[-1+1]為0，所以棧長(zhǎng)度即為[棧頂索引+1]。

//棧長(zhǎng)度
public int Length
{
    get
    {
        //棧長(zhǎng)度等于棧頂元素加1
        return _top + 1;
    }
}

5、獲取棧頂元素 Top

獲取棧頂元素可以通過(guò)棧頂索引私有字段從數(shù)組中直接獲取，同時(shí)要注意判斷棧是否為空棧，如果為空棧則報(bào)異常。具體代碼如下：

//獲取棧頂元素
public T Top
{
    get
    {
        if (IsEmpty())
        {
            //空棧，不可以進(jìn)行獲取棧頂元素操作
            throw new InvalidOperationException("空棧");
        }
        return _array[_top];
    }
}

6、獲取是否空棧 IsEmpty

是否空棧只需判斷棧頂索引是否為小于0即可。

//是否空棧
public bool IsEmpty()
{
    //棧頂索引小于0表示空棧
    return _top < 0;
}

7、獲取是否滿棧 IsFull

是否滿棧只需判斷棧頂索引是否與棧容量減1相等，代碼如下：

//是否滿棧
public bool IsFull()
{
    //棧頂索引等于容量大小表示滿棧
    return _top == _capacity - 1;
}

8、入棧 Push

入棧則是在把棧頂索引向數(shù)組后移動(dòng)一位后，再把新元素賦值到棧頂索引所對(duì)應(yīng)的元素上，同時(shí)還需要檢查是否為滿棧，如果是滿棧則報(bào)錯(cuò)，具體實(shí)現(xiàn)代碼如下：

//入棧
public void Push(T value)
{
    if (IsFull())
    {
        //棧頂索引大于等于容量大小減1，表明已經(jīng)滿棧，不可以進(jìn)行入棧操作
        throw new InvalidOperationException("滿棧");
    }
    //棧頂索引先向后移動(dòng)1位，然后再存放棧頂元素
    _array[++_top] = value;
}

9、出棧 Pop

出棧則是首先取出棧頂元素后，然后把棧頂索引向數(shù)組前移動(dòng)一位，最后返回取出的棧頂元素，同時(shí)還需要檢查是否為空棧，如果是空棧則報(bào)錯(cuò)，具體實(shí)現(xiàn)代碼如下：

//出棧
public T Pop()
{
    if (IsEmpty())
    {
        //棧頂索引小于1表示空棧，不可以進(jìn)行出棧操作
        throw new InvalidOperationException("空棧");
    }
    //返回棧頂元素后，棧頂索引向前移動(dòng)1位
    return _array[_top--];
}

04 、實(shí)現(xiàn)（鏈棧）

我們借助鏈表來(lái)實(shí)現(xiàn)鏈棧，其核心思想是把鏈表尾節(jié)點(diǎn)作為棧底，把鏈表首元節(jié)點(diǎn)當(dāng)作棧頂。

這是因?yàn)槿绻�我們想拿到鏈表的尾�?jié)點(diǎn)需要變量整個(gè)鏈表才可以拿到，但是要想獲取首元節(jié)點(diǎn)則可以通過(guò)頭指針直接獲取到（無(wú)頭節(jié)點(diǎn)鏈表），因此對(duì)于鏈表尾節(jié)點(diǎn)來(lái)說(shuō)操作時(shí)不友好的適合來(lái)做棧底，鏈表首元節(jié)點(diǎn)對(duì)操作友好適合做為棧頂。

下面我們將一步一步實(shí)現(xiàn)一個(gè)泛型鏈棧。

1、ADT定義

相對(duì)于順序棧的ADT來(lái)說(shuō)，鏈棧的ADT少了兩個(gè)方法即獲取棧容量和是否滿棧，這也是鏈表特性帶來(lái)的好處。

2、初始化Init

初始化結(jié)構(gòu)主要初始化棧頂節(jié)點(diǎn)為空和棧長(zhǎng)度為0，具體實(shí)現(xiàn)如下：

public class MyselfStackNode
{
    //數(shù)據(jù)域
    public T Data;
    //指針域，即下一個(gè)節(jié)點(diǎn)
    public MyselfStackNode Next;
    public MyselfStackNode(T data)
    {
        Data = data;
        Next = null;
    }
}
public class MyselfStackLinkedList
{
    //棧頂節(jié)點(diǎn)即首元節(jié)點(diǎn)
    private MyselfStackNode _top;
    //棧長(zhǎng)度
    private int _length;
    //初始化棧
    public MyselfStackLinkedList Init()
    {
        //初始化棧頂節(jié)點(diǎn)為空
        _top = null;
        //初始化棧長(zhǎng)度為0
        _length = 0;
        //返回棧
        return this;
    }
}

3、獲取棧長(zhǎng)度 Length

這個(gè)比較簡(jiǎn)單直接把棧長(zhǎng)度私有字段返回即可。

//棧長(zhǎng)度
public int Length
{
    get
    {
        return _length;
    }
}

4、獲取棧頂元素 Top

獲取棧頂元素可以通過(guò)棧頂節(jié)點(diǎn)直接獲取，但是要注意判斷棧是否為空棧，如果為空棧則報(bào)異常。具體代碼如下：

//獲取棧頂元素
public T Top
{
    get
    {
        if (IsEmpty())
        {
            //空棧，不可以進(jìn)行獲取棧頂元素操作
            throw new InvalidOperationException("空棧");
        }
        //返回首元節(jié)點(diǎn)數(shù)據(jù)域
        return _top.Data;
    }
}

5、獲取是否空棧 IsEmpty

是否空棧只需判斷棧頂節(jié)點(diǎn)是否為空即可。

//是否空棧
public bool IsEmpty()
{
    //棧頂節(jié)點(diǎn)為null表示空棧
    return _top == null;
}

6、入棧 Push

入棧則是首先創(chuàng)建一個(gè)新節(jié)點(diǎn)，然后把原棧頂節(jié)點(diǎn)賦值給新節(jié)點(diǎn)的指針域，最后把新節(jié)點(diǎn)變更為棧頂節(jié)點(diǎn)，同時(shí)棧長(zhǎng)加1，具體實(shí)現(xiàn)代碼如下：

//入棧
public void Push(T value)
{
    //創(chuàng)建新的棧頂節(jié)點(diǎn)
    var node = new MyselfStackNode(value);
    //將老的棧頂節(jié)點(diǎn)賦值給新節(jié)點(diǎn)的指針域
    node.Next = _top;
    //把棧頂節(jié)點(diǎn)變更為新創(chuàng)建的節(jié)點(diǎn)
    _top = node;
    //棧長(zhǎng)度加1
    _length++;
}

7、出棧 Pop

出棧則是首先取出棧頂節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)后，然后把棧頂節(jié)點(diǎn)指向原棧頂節(jié)點(diǎn)對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)，同時(shí)棧長(zhǎng)度減1，當(dāng)然如果空棧則報(bào)錯(cuò)，具體實(shí)現(xiàn)代碼如下：

//出棧
public T Pop()
{
    if (IsEmpty())
    {
        //空棧，不可以進(jìn)行出棧操作
        throw new InvalidOperationException("空棧");
    }
    //獲取棧頂節(jié)點(diǎn)數(shù)據(jù)
    var data = _top.Data;
    //把棧頂節(jié)點(diǎn)變更為原棧頂節(jié)點(diǎn)對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)
    _top = _top.Next;
    //棧長(zhǎng)度減1
    _length--;
    //返回棧頂數(shù)據(jù)
    return data;
}

注 ：測(cè)試方法代碼以及示例源碼都已經(jīng)上傳至代碼庫(kù)，有興趣的可以看看。 https://gitee.com/hugogoos/Planner