1. 棧的概念和結構

之前幾篇我們分別講解了順序表和單鏈表的內容，今天我們又來學習一個新的關于數據結構的內

容--- 棧 。

棧：棧也屬于線性表 ,?但它是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操

作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出

LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

棧底層結構選型:

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插

入數據的代價比較小。

2. 棧,順序表,單鏈表之間的關聯

棧、順序表和鏈表都是數據結構領域中重要的概念，它們之間存在著緊密的聯系，也有著明顯的區

別：

?
2.1 聯系:

- 底層實現關聯：棧可以使用順序表（數組）或者鏈表作為底層的數據存儲結構來實現。

- 基于順序表實現棧：在以順序表為基礎實現棧時，通常使用數組來存儲棧中的元素，用一個變量

（如?top?）來記錄棧頂的位置。入棧操作就是在數組末尾添加元素（當空間足夠時），并更

新?top??；出棧操作則是移除數組末尾元素，并更新?top??。這種實現方式利用了順序表在尾端插入

和刪除元素的高效性（時間復雜度為O(1)）。

- 基于鏈表實現棧：當用鏈表實現棧時，一般將鏈表的頭節點作為棧頂。入棧操作通過在鏈表頭部

插入新節點來完成，出棧操作則是刪除鏈表頭部節點。這是因為在鏈表頭部進行插入和刪除操作的

時間復雜度也是O(1) ，符合棧的操作特性。

- 棧底層結構選型:

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插

入數據的代價比較小。

- 數據存儲特性：從數據存儲的角度來看，順序表、鏈表和棧都是用于組織和存儲數據的方式。順

序表和鏈表是更基礎的數據結構，提供了不同的存儲和訪問數據的方式；而棧是一種具有特定操作

約束（后進先出）的數據結構，它可以借助順序表或鏈表來實現其功能。

?2.2 區別:

- 數據結構定義:

- 棧：是一種抽象數據類型，它定義了一組特定的操作，主要包括入棧、出棧和獲取棧頂元素等，

重點在于操作的規則（后進先出），而不是具體的存儲方式。

- 順序表：是一種線性數據結構，它使用連續的內存空間來存儲數據元素，元素之間的邏輯順序和

物理順序是一致的。用戶可以通過下標快速訪問表中的任意元素，支持在任意位置插入和刪除元素

（但在非末尾位置操作的時間復雜度較高 ）。

- 鏈表：也是一種線性數據結構，它通過指針將各個數據節點鏈接起來，節點在內存中的存儲位置

不一定連續。鏈表的優勢在于插入和刪除操作較為靈活高效（時間復雜度為O(1) ，前提是已知待

操作節點的前驅節點 ），但訪問特定位置的元素需要從頭節點開始遍歷，時間復雜度為O(n) 。

- 操作特性:

- 棧：操作受限，只能在棧頂進行插入和刪除操作，遵循后進先出原則，主要用于解決具有特定順

序要求的問題，比如函數調用、表達式求值等。

- 順序表：操作相對靈活，可以在任意位置進行插入、刪除和訪問操作。但在插入和刪除元素時，

如果涉及到大量元素的移動（比如在表頭插入元素 ），時間復雜度較高，為O(n) ；訪問元素的時

間復雜度為O(1) 。

- 鏈表：插入和刪除操作在已知前驅節點的情況下時間復雜度低，為O(1) ，但訪問元素需要順序遍

歷鏈表，時間復雜度為O(n) ，不支持隨機訪問。

- 內存使用:

- 順序表：需要預先分配一定大小的連續內存空間，如果數據量預估不準確，可能會導致內存浪費

（分配過大）或溢出（分配過小 ）。

- 鏈表：采用動態內存分配，按需分配節點空間，不會造成內存的浪費，但每個節點除了存儲數據

外，還需要額外存儲指針，會占用一定的內存空間。

- 棧：根據其實現方式的不同，內存使用特點也有所不同。基于順序表實現的棧，存在與順序表類

似的內存分配問題；基于鏈表實現的棧，內存分配較為靈活，類似于鏈表的內存使用方式。

以上便是棧的概念內容以及它和順序表和單鏈表之間的關系。下一篇文章小編將詳細講解關于棧的

內容的實現。