C#的開發，什麼時候用到了棧的先進後出機制？

01-06

印象中在操作系統中學完堆棧之後，在實際的C#開發中涉及到堆棧的也就是值類型的變數存儲在棧上，其他的就沒什麼了。如果說漏了的請指正。
但是，即使是值類型的變數存儲在棧上，依然沒有體會到棧的FILO機制呢？

兩個「棧」，一個是代碼調用時的所謂「棧」，一個是數據結構的棧，雖然兩者概念上有關聯之處，但不要把兩個東西混在一起說，你現在的這個思考方式就是亂了。同理，還有系統里的「堆」和數據結構的「堆」，雖然都叫heap，但是這兩個東西的關係比兩個「棧」的關係還要弱。

至於什麼時候用數據結構的棧，找本數據結構的書就會告訴你使用場景了。

由於是剛畢業時做的，代碼不好找了，大致思路如下：

甲圖：用戶執行了四個任意的動作，向棧中壓入A1~A4，然後標誌位指向A4。

乙圖：用戶執行撤銷，標誌位指向A3（此時A4不會被彈出）。

丙圖：用戶執行了第二次撤銷，標誌位指向A2。

丁圖：用戶執行了重做，標誌位指回A3。

戊圖：用戶此時執行了任意一個操作，此時會將A3以上的動作全部按照「先入後出」的原則進行出棧，同時壓入新的A4，同時標誌位指向新的A4。其實並不是嚴格的先入後出的棧，不過思路是一樣的。

------以上內容為20141229補充------

說到先進後出，我以前做過一個Web界面上的「撤銷-重做」功能。記錄每一步操作，壓入一個棧里，然後等執行撤銷時，就是先入後出了。

其實題主最在意的是「體會到LIFO順序」這點而已吧？

那樣的話好辦啊：

using System;

namespace Test { public class Program { static void Foo(int depth, int max) { Console.WriteLine("Calling Foo(depth={0}, max={1})", depth, max); if (depth &< max) Foo(depth + 1, max); Console.WriteLine("Returning from Foo(depth={0}, max={1})", depth, max); } static void RecurseToDepth(int max) { Foo(0, max); } static void Main(string[] args) { RecurseToDepth(5); } } }

運行結果：

Calling Foo(depth=0, max=5) Calling Foo(depth=1, max=5) Calling Foo(depth=2, max=5) Calling Foo(depth=3, max=5) Calling Foo(depth=4, max=5) Calling Foo(depth=5, max=5) Returning from Foo(depth=5, max=5) Returning from Foo(depth=4, max=5) Returning from Foo(depth=3, max=5) Returning from Foo(depth=2, max=5) Returning from Foo(depth=1, max=5) Returning from Foo(depth=0, max=5)

很明顯的LIFO ^_^

如果你是一個高效生產程序員，不需要考慮那麼多的。。編譯器和CLR會幫你做優化的親。

系統棧是用來做函數調用的。舉個例子，如果main調用A，A調用B；B最後被調用，B最先退出，A先被調用，A後退出；這不就是FILO嗎？

分析一下簡單的遞歸函數，比如遞歸求階乘之類的，可能更容易看。

最近參與編寫了一款用Unity製作的手游（所以索性採用了C#），與《Lightbot》玩法基本一致。在編寫到「函數調用」這一塊的時候，考慮到了採用堆棧的方法。

簡單界面如下：

遊戲的玩法其實很簡單，把左上角的指令放置到右邊的「函數面板上」。如你所見。有「主要函數」，「函數1（F1）」「函數2（F2）」。

既然利用了堆棧，堆棧格式上必不可少幾個方法如下：

此堆棧的設計其實也蠻簡單的，把函數部分都弄成委託數組（保存相對應的指令數組）每次POP,PUSH的都是一個委託數組，既實現了可以在Main Push F1，在F1裡面Push F2，等等之類的做法。

等等，這時候出現了一個問題，如果F1 PUSH F1 跑起來會怎麼樣呢？這個不屬於堆棧了。在此就不討論了。

我的這個答案可能比較片面，但是也是最近的項目中運用到堆棧的方法，所以拿來分享。

先進後出機制

Windows 8 應用界面視圖遵循先進後出，類似的還有Android的Activity

本質上來講，每次調用函數都是一次入棧出棧：

1. 每一個call都是一次入棧（把當前代碼位置入棧，然後jump到另一個代碼的位置）

2. 每次return都是一次出棧（把最近一次入棧的代碼位置取出，並跳轉回這個位置）

另外，可以參考遞歸轉迭代的實現（其實就是用棧記錄之前由函數調用記錄的狀態）：

一個先序遍歷樹並列印節點的代碼本來是這樣的：

function printNode(TreeNode node){

print(node.value);

printNode(node.leftChild);

prinitNode(node.rightChild);

}

轉換後：

function printNode(TreeNode node){

Stack stack = new Stack();

stack.push(node);

while (!stack.isEmpty()) {

TreeNode n = stack.pop();

print(n.value);

if (n.right != null) {

stack.push(n.rightChild);

}

if (n.left != null) {

stack.push(n.leftChild);

}

代碼只是個示意，需要改改才能運行哈。

引用類型變數也存在棧上面，變數指向的實體存在堆上面

給你一個具體的場景，比如，你要做個像Word一樣的編輯器，你需要實現撤消的功能。一般是弄個命令模式，把每次的操作push到一個堆棧裡面，撤消的時候直接pop就可以了,這樣是LIFO了

每一次函數調用產生的一個整體（包括返回位置，局部變數等）是棧的一項，對於這些整體而言，是滿足FILO的。但是如果拆開來看，把每個變數都看作一項的話，確實就不滿足棧的性質了。

用「非遞歸」方式實現「通常由遞歸實現的演算法」的時候(比如尋路)，很多就是自己做一個棧，目的一般是防止棧溢出

n2 = n1 + (n1 = n2) * 0;

計算器