棧一種常見的特殊線性數(shù)據(jù)結構，其特殊之處在于其操作順序，下面會詳細介紹，也正因為其特性，因此�？梢暂p松解決表達式求值、括號匹配、遞歸算法、回溯算法等等問題。

01 、定義

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

入棧 ：當把元素插入到棧，這一行為叫做入棧，也稱進�；驂簵�；

出棧 ：當把元素從棧中移除，這一行為叫做出棧，也稱退棧；

棧頂 ：允許元素進行插入和刪除操作的一端稱為棧頂；

棧底 ：與棧頂對應的另一個端稱為棧底，并且不允許進行元素操作；

空棧 ：當棧中沒有元素時叫做空棧。

滿棧 ：當棧是有限容量，并且容量已用完，則稱為滿棧。

棧容量 ：當棧是有限容量，棧容量表示�？梢匀菁{的最大元素數(shù)量。

棧大小 ：表示當前棧中的元素數(shù)量。

02 、分類

棧是邏輯結構，因此以存儲方式的不同可以分為順序棧和鏈棧。

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

鏈棧顧名思義就是采用鏈式方式存儲，通常采用單向鏈表實現(xiàn)，因此鏈棧可以無限擴容，按需使用，內(nèi)存利用高效，同時也不存在滿棧的情況。

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

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

我們知道數(shù)組對插入、刪除元素是不友好的，因為涉及到已存在元素移動的問題，但是如果直接在數(shù)組尾端插入、刪除元素還是很方便的，因為不涉及元素移動問題，我們正是利用這一特點，把數(shù)組起始位置做為棧底，而插入、刪除方便的數(shù)組尾端作為棧頂。

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

1、ADT定義

我們首先來定義順序棧的ADT。

ADT Stack{

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

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

基本操作：[

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

Capacity：返回棧容量。

Length：返回棧長度。

Top：返回棧頂元素，當為空棧則報異常。

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

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

Push()：入棧即添加元素，當為滿棧則報異常。

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

]

}

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

2、初始化Init

初始化結構主要做幾件事。

• 初始化棧的容量；

• 初始化存放棧元素數(shù)組；

• 初始化棧頂索引；

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

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

3、獲取棧容量 Capacity

這個比較簡單直接把棧容量私有字段返回即可。

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

4、獲取棧長度 Length

因為棧頂索引表示數(shù)組下標，因此可以通過棧頂索引加1轉(zhuǎn)為棧長度，同時因為我們定義了空棧是棧頂索引為-1，因此此時棧長等于[-1+1]為0，所以棧長度即為[棧頂索引+1]。

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

5、獲取棧頂元素 Top

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

//獲取棧頂元素
public T Top
{
    get
    {
        if (IsEmpty())
        {
            //空棧，不可以進行獲取棧頂元素操作
            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ù)組后移動一位后，再把新元素賦值到棧頂索引所對應的元素上，同時還需要檢查是否為滿棧，如果是滿棧則報錯，具體實現(xiàn)代碼如下：

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

9、出棧 Pop

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

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

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

我們借助鏈表來實現(xiàn)鏈棧，其核心思想是把鏈表尾節(jié)點作為棧底，把鏈表首元節(jié)點當作棧頂。

這是因為如果我們想拿到鏈表的尾節(jié)點需要變量整個鏈表才可以拿到，但是要想獲取首元節(jié)點則可以通過頭指針直接獲取到（無頭節(jié)點鏈表），因此對于鏈表尾節(jié)點來說操作時不友好的適合來做棧底，鏈表首元節(jié)點對操作友好適合做為棧頂。

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

1、ADT定義

相對于順序棧的ADT來說，鏈棧的ADT少了兩個方法即獲取棧容量和是否滿棧，這也是鏈表特性帶來的好處。

2、初始化Init

初始化結構主要初始化棧頂節(jié)點為空和棧長度為0，具體實現(xiàn)如下：

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

3、獲取棧長度 Length

這個比較簡單直接把棧長度私有字段返回即可。

//棧長度
public int Length
{
    get
    {
        return _length;
    }
}

4、獲取棧頂元素 Top

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

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

5、獲取是否空棧 IsEmpty

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

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

6、入棧 Push

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

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

7、出棧 Pop

出棧則是首先取出棧頂節(jié)點對應的數(shù)據(jù)后，然后把棧頂節(jié)點指向原棧頂節(jié)點對應的下一個節(jié)點，同時棧長度減1，當然如果空棧則報錯，具體實現(xiàn)代碼如下：

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

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