一、棧的概念和結構

棧其實就是一種特殊的順序表，其只允許在一端進出，就是棧的數據的插入和刪除只能在一端進行，進行數據的插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的元素遵循先進后出LIFO（Last InFirst Out）的原則。

?壓棧：棧的插入操作叫做進棧/壓棧/入棧，入棧的位置也是在棧頂。

?出棧：棧的刪除操作叫做出棧。出棧也是在棧頂。

那么我們的棧是要如何進行實現呢？

我們實現棧的話有兩種：鏈表和數組。

如果是使用鏈表的話，那么我們要是以頭為棧頂，那么我們進行頭插的話，就需要先考慮鏈表是否為空的情況，然后我們的頭插的結構也是比較麻煩，每次都需要進行節點的申請。

還有就是進行出棧的時候也比較麻煩。

如果我們使用數組，直接使用數組的尾部為棧頂，那么我們的壓棧和出棧都可以直接進行，時間復雜度為O(1)。

不過鏈表和數組都是可以實現的，不過如果使用鏈表進行實現的話，我們就推薦使用鏈表的頭為棧頂，然后數組的話我們建議使用數組的尾部為棧頂。這樣可以使得壓棧和出棧的時間復雜度都為O(1)。

二、棧的實現

1、棧的定義

我們上面提到了，我們實現棧，我們底層使用數組來實現，那么其定義和我們前面學習的順序表基本是一樣的，但是就是我們的棧是有一個限制的，就是其只能在一端進行出入。

棧的定義如下：

其實 arr就是我們存儲數據的數組，然后top表示當前我們的棧有多少個元素，capacity就表示我們當前的棧最大的容量。
我們定義好后，那么我們對這個棧進行一個初始化：

因為棧的銷毀這里也不做多的解釋了。

棧的銷毀：

下面我們實現棧的壓棧：

我們棧的特點就是其只有一端可以進行壓棧和出棧的操作，我們前面說到，我們使用數組來實現的話，那么我們是在數組的尾部進行壓棧和出棧，那么我們該如何進行壓棧呢？

我們在定義棧的時候，我們有一個成員top其是記錄當前我們的棧中的有效成員個數的，那么我們的數組是可以通過下標進行插入數據的，不過要注意的是，我們的棧如果此時為空，而且其表示棧的容量的成員也是空的時候，那么我們就需要進行空間申請的，還有就是棧如果滿了，那么我們此時也需要進行空間的申請。不過我們發現我們的棧為空和棧滿的時候有個共同點，就是我們的top和capacity是i相等的。所以我們再入棧操作的時候，一開始需要先進行判斷當前棧的空間是否足夠，不夠的話我們要進行擴容，然后我們擴容一般是二倍增容。還有一個特殊情況就是剛開始的時候，我們的容量還是0，那么我們此時進行二倍增容是行不通的，所以我們也特殊處理一下。

代碼如下：

?上面我們實現了壓棧，那么我們接下來就實現棧的另外一個功能：出棧

我們要出棧，那么我們的棧就要不為空才行，所以我們可以先寫一個函數判斷棧是否為空，然后通過這個函數我們就可以進行出棧，要注意的是我們的棧，出棧也是要在棧頂這一端，所以也是在數組的末尾端，那么我們的top進行--操作就可以了，那么就可以使得我們的棧的有效元素個數減-，而且是棧頂的第一個元素。

壓棧：

?我們棧有時候只是需要取棧頂的元素，并不需要出棧，那么我們也可以寫一個函數來實現，我們的取棧頂元素是很簡單的，就是訪問數組一樣，我們就訪問下標為top-1的元素即可。

然后我們也可以獲取當前棧的實際有效元素個數：

可以看到我們的棧的兩個大的功能還是很好實現的，和我們前面的順序表大致一樣，就是其要控制的是，其入棧和出棧的端要一致。