2.1 如何實現棧

【出自ALBB面試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

題目描述：

實現一個棧的數據結構，使其具有以下方法：壓棧、彈棧、取棧頂元素、判斷棧是否為空以及獲取棧中元素個數。

分析與解答：

棧的實現有兩種方法，分別為采用數組來實現和采用鏈表來實現。下面分別詳細介紹這兩種方法。

方法一：數組實現

在采用數組來實現棧的時候，棧空間是一段連續的空間。實現思路如下圖所示。

從上圖中可以看出，可以把數組的首元素當作棧底，同時記錄棧中元素的個數size，假設數組首地址為arr，壓棧的操作其實是把待壓棧的元素放到數組arr[size]中，然后執行size++操作；同理，彈棧操作其實是取數組arr[size-1]元素，然后執行size--操作。根據這個原理可以非常容易實現棧，實現代碼如下：

方法二：鏈表實現

在創建鏈表的時候經常采用一種從頭結點插入新結點的方法，可以采用這種方法來實現棧，最好使用帶頭結點的鏈表，這樣可以保證對每個結點的操作都是相同的，實現思路如下圖所示。

在上圖中，在進行壓棧操作時，首先需要創建新的結點，把待壓棧的元素放到新結點的數據域中，然后只需要（1）和（2）兩步就實現了壓棧操作（把新結點加到了鏈表首部）。同理，在彈棧的時候，只需要進行步驟（3）的操作就可以刪除鏈表的第一個元素，從而實現彈棧操作。實現代碼如下：

程序的運行結果為

兩種方法的對比：

采用數組實現棧的優點：一個元素值占用一個存儲空間；它的缺點：如果初始化申請的存儲空間太大，會造成空間的浪費，如果申請的存儲空間太小，后期會經常需要擴充存儲空間，擴充存儲空間是個費時的操作，這樣會造成性能的下降。

采用鏈表實現棧的優點：使用靈活方便，只有在需要的時候才會申請空間。它的缺點：除了要存儲元素外，還需要額外的存儲空間存儲指針信息。

算法性能分析：

這兩種方法壓棧與彈棧的時間復雜度都為O（1）。