棧到底是什么玩意

cpu中有棧段SS寄存器和棧指針SP寄存器，它們是用來指定當前使用的棧的物理地址。換句話說，要想讓cpu運行，必須得有棧。棧是什么?干嗎用的？本節將給大家一個交待。

還記得數據結構中的棧嗎？那是邏輯上的數據存取結構，是種如何用這種數據結構來存取數據的描述。在用戶進程空間中，堆是堆，棧是棧，但堆棧卻是人們常說的棧，和堆沒關系，所以，咱們后面為避免混淆，只說棧。

棧是線性表的一種，什么是線性表？如果提出這樣的問題，我想您可能不清楚什么是線性。線性就是具有線的性質，就像一條線一樣，連續性強，從一個方向到另一個方向。線上沒有面積的概念，不管是直線還是曲線，在線上任意位置只能容納一個數據對象。線性表簡而言之就是一個線性存儲單元，結構中每個元素都有一個前驅和一個后繼元素，且僅各有一個。這就是線性的體現：連續，且任意位置只有一個元素。棧也是這樣，不過不同的是，數據的存取都在一端進行，這一端稱為棧頂，另一端做為存儲單元的基址永遠不動，稱為棧底。這就是上學時，老師們常常說的后進先出，先放進去的數據要在最后才能取出，后放進去的數據最先被取出。

這里我就不用舉漢諾塔這樣經典的例子了，畢竟上學時都聽得太多了。我說個大家都認同的事實：大家肯定擠過公交車吧（坐過公交車的同學繼續看，土豪隨意^_^），尤其是早班車和末班車，車廂里人擠人，站都站不穩。先擠上車的乘客其實很倒霉的（有座兒不算^_^），因為他要在最后下車，在擁擠的車廂中折磨的時間最長。后擠上車的乘客在下車的時候還是蠻爽的，因為他會是第一個下車，是率先逃出惡劣環境的人。所以，擠公交車就是典型的后進先出。車廂就相當于棧，乘客就相當于棧中存取的元素，這個例子其實還算生動。

舉的例子雖然很常見，但這對于已經理解棧的同學來說，我像是在說廢話一樣沒新意。對于不理解棧的同學來說，可能是依然像說廢話一樣，說了也意會不到棧是什么。我非常理解這種心情，記得當初我在學網絡時，老師說只要在路由器上把三層（網絡層）IP協議（不是指令指針寄存器IP）禁用，四層（傳輸層）上的tcp或udp協議自然就不可用了。老師為了讓我們明白這種依賴關系，甚至不惜舉出這樣的例子：如果不想讓某人說話 ，最簡單的辦法就是給讓其睡著，而不是勸他保護安靜。這個例子非常淺顯易懂，但用例子來理解理論知識，依然讓我有點摸不著頭腦，這可不是比喻恰不恰當的事，知識是嚴謹的，不是比喻出來的。如果您現在也有這樣的體會，沒關系，以后會不斷接觸棧的，熟了自然就理解了，這只是時間問題。

初次學習數據結構時，不容易理解其本質，我當初在學習這門課時，感覺云里霧里的，似乎明白似乎又不懂，老師讓不懂的同學提問，我又不知道該怎樣描述問題，不知道哪里不懂。同樣的定義，同樣的文字描述，每個人理解的都不一樣。就像魚和小鳥，魚認為自己離開水就會死，水就是生命，小鳥也認為沒水會渴死，水也是生命。但魚和小鳥對水的理解能一樣嗎?趕緊回來，還是說咱們的正事。棧只是一種抽象概念，是一種虛擬出來的數據存取方法。其實現形式是不限的，只要滿足棧的定義就可以：

• λ首先得是線性結構，并且數據的存取在線性結構的一端進行。如果您愿意，可以用鏈表來實現，也可以用數組來實現，它們都是線性數據結構。
• λ其次需要維護一個指針，用它來指向線性結構的一端，數據存取都通過此指針。

前面又比喻又回憶的，說了這么多，棧能夠干什么呢？棧是一種很偉大的發明，可以解決很多難題：

• λ表達式計算，如中綴表達式和后綴表達式的轉換
• λ函數調用，無論是嵌套調用或遞歸調用，用來維護返回地址。
• λ深度優先搜索算法

到現在為止，我們說的只是數據結構中的棧，這是邏輯上的，最終我想表達的是內存中的棧，這是物理上的。把數據結構中的棧的概念用物理硬件來實現，這就是我們要說的棧。它同數據段、代碼段一樣，是個內存中的區域。也就是棧段寄存器SS和棧指針SP所指向的內存區域。我們常聽說的棧溢出，指的就是這個內存區域無法容納數據了。

硬件是如何實現這個棧的呢?還是那句話，首先得滿足棧的概念，具備棧的特性，即使是硬件也不能例外，必須滿足上面提到的這兩個條件：一個是線性結構，一個是在棧頂對數據存取。因為它畢竟造的是棧，不具備這些就不叫棧了。

線性結構這個簡單，內存就是，直接用物理內存存取最方便了，咱們要做的，就是給棧指定一片內存區域就成了，區域的起始地址做為棧基址，存入棧基址寄存器SS中，另一端是動態變化的，用棧指針寄存器SP來指定。棧在使用過程中是向下擴展的，所以棧頂地址肯定是小于棧底地址。

棧既然是一片內存區域，訪問內存就要用“段基址：段內偏移地址”的形式，所以棧中的內存地址也是用“段基址SS的值*16+棧指針SP（段內偏移地址）形成的20位地址”訪問到的。由于是硬件實現的棧，故硬件提供了相應的方法來存取棧，即push和pop指令。push指令負責把數據壓入棧，pop指令功能相反，將其從棧中取出。不過我剛才說的不全面，棧的出口和入口都是棧頂，push把數據壓向哪里，它得知道棧頂在哪里才行。pop指令也一樣，它得知道哪里是棧頂才能從棧中取出正確的數據。這正是棧指針寄存器SP的作用，此寄存器中的值是段內偏移地址，是棧頂相對于棧底的偏移量。

棧頂（SP指針）是棧的出口和入口，它指向的內存中存儲的始終是最新的數據。push和pop就是操作這個指針所指向的內存。由于棧是從高地址向低地址發展，所以棧頂、棧指針指向的地址會越來越低。push壓入數據的過程是：先將SP減去字長，目的是避免將棧頂的數據破壞，所得的差再存入SP，棧頂在此被更新，這樣棧頂就指向了棧中下一個存儲單元的位置。再將數據壓入SP（新的棧頂）指向的新的內存地址。pop指令相反，既然是在棧中彈出數據，棧指針寄存器SP的值應該是增大一個數據單位。由于要彈出的數據就在當前棧頂，所以在彈出數據后，才將SP加上字長，所得的和再存入SP，從而更新了棧頂。這樣SP就指向了上一個存儲單元的位置。

上面提到的字長，是指cpu的字長，即一次可處理的數據的長度。在實模式下的字長是16。

物理內存中的棧如圖:

?

注意啦，如圖所示，雖然棧是向下發展，但棧也是內存，訪問內存依然是從低地址往高地址，假如當前棧頂是0x1233E，棧頂數據占2字節的話，其范圍是0x1233E~0x1233F。個人覺得，這個硬件中的棧讓人感到神秘，主要有兩方面原因：

一方面是棧指針不是自己維護，這不像咱們在高級語言中自己創建的棧那樣，指針的一舉一動都是自己在操作。不直接受控的東西往往讓人心存憂慮和有點小恐慌。其實即使是這里的硬件棧，咱們也可以自己維護指針，如push ax可以這樣代替：

mov bp,sp sub bp, 2 mov [bp],ax

bp默認的段寄存器就是SS，用bp的時候直接操作的便是棧。bp就相當于棧指針啦，自己維護畢竟太麻煩，有直接省事的干嗎不用呢^_^。

另一方面，棧就是一片內存區域，只不過“經常”操作這片內存的指令不是mov，而是push、pop，這兩條指令無非是自動維護存取數據的位置（SP寄存器的值）而已，大家用mov來操作這片內存，不是也得要給出存取地址嗎。這樣看來，它和普通的數據段沒什么不同，不要覺得它比金字塔還神秘啦。

一定要注意，push和pop操作是要成對出現的，這樣才能維護棧平衡。否則，光push，不pop，有進沒出，這棧很快就溢出啦。切記，一個push要對應一個pop，每鍵入一個pop指令，一定要清楚它對應的是哪個push。

棧就先說這么多，不摸索實際東西的話還是不能真正掌握和理解，本書強調實踐，紙上談兵可來不了真知識。

好啦，官人常來玩哦

總結

以上是生活随笔為你收集整理的一步步编写操作系统 13 栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。