原文:
最近晚上在家裡看，我買的，覺得這本書寫的比較淺顯易懂，而且“圖碼并茂”，趁着這次機會打算好好學習做做筆記，這樣也會印象深刻，這也是寫這一系列文章的原因。另外普林斯頓大學在
上也有這本書同步的公開課，還有另外一門課，這門課程的作者也是這本書的作者，兩門課都挺不錯的。
計算機程式離不開算法和資料結構，本文簡單介紹棧(Stack)和隊列(Queue)的實作，.NET中與之相關的資料結構，典型應用等，希望能加深自己對這兩個簡單資料結構的了解。
概念很簡單，棧 (Stack)是一種後進先出(last in first off，LIFO)的資料結構，而隊列(Queue)則是一種先進先出 (fisrt
in first out，FIFO)的結構，如下圖：
現在來看如何實作以上的兩個資料結構。在動手之前，這本書告訴我們，在設計API或者實體類的時候，應當圍繞場景編寫API規格說明書。
1.1 Stack的實作
棧是一種後進先出的資料結構，對于Stack 我們希望至少要對外提供以下幾個方法：
Stack<T>()
建立一個空的棧
void Push(T s)
往棧中添加一個新的元素
T Pop()
移除并傳回最近添加的元素
boolean IsEmpty()
棧是否為空
int Size()
棧中元素的個數
要實作這些功能，我們有兩中方法，數組和連結清單，先看連結清單實作：
棧的連結清單實作：
我們首先定義一個内部類來儲存每個連結清單的節點，該節點包括目前的值以及指向下一個的值，然後建立一個節點儲存位于棧頂的值以及記錄棧的元素個數;
現在來實作Push方法，即向棧頂壓入一個元素，首先儲存原先的位于棧頂的元素，然後建立一個新的棧頂元素，然後将該元素的下一個指向原先的棧頂元素。整個Pop過程如下:
實作代碼如下：
Pop方法也很簡單，首先儲存棧頂元素的值，然後将棧頂元素設定為下一個元素：
基于連結清單的Stack實作，在最壞的情況下隻需要常量的時間來進行Push和Pop操作。
棧的數組實作：
我們可以使用數組來存儲棧中的元素Push的時候，直接添加一個元素S[N]到數組中，Pop的時候直接傳回S[N-1].
首先，我們定義一個數組，然後在構造函數中給定初始化大小，Push方法實作如下，就是集合裡添加一個元素：
Pop方法：
在Push和Pop方法中，為了節省記憶體空間，我們會對數組進行整理。Push的時候，當元素的個數達到數組的Capacity的時候，我們開辟2倍于目前元素的新數組，然後将原數組中的元素拷貝到新數組中。Pop的時候，當元素的個數小于目前容量的1/4的時候，我們将原數組的大小容量減少1/2。
Resize方法基本就是數組複制：
當我們縮小數組的時候，采用的是判斷1/4的情況，這樣效率要比1/2要高，因為可以有效避免在1/2附件插入，删除，插入，删除，進而頻繁的擴大和縮小數組的情況。下圖展示了在插入和删除的情況下數組中的元素以及數組大小的變化情況：
分析：1. Pop和Push操作在最壞的情況下與元素個數成比例的N的時間，時間主要花費在擴大或者縮小數組的個數時，數組拷貝上。
2. 元素在記憶體中分布緊湊，密度高，便于利用記憶體的時間和空間局部性，便于CPU進行緩存，較LinkList記憶體占用小，效率高。
2.2 Queue的實作
Queue是一種先進先出的資料結構，和Stack一樣，他也有連結清單和數組兩種實作，了解了Stack的實作後，Queue的實作就比較簡單了。
建立一個空的隊列
void Enqueue(T s)
往隊列中添加一個新的元素
T Dequeue()
移除隊列中最早添加的元素
隊列是否為空
隊列中元素的個數
首先看連結清單的實作：
Dequeue方法就是傳回連結清單中的第一個元素，這個和Stack中的Pop方法相似：
Enqueue和Stack的Push方法不同，他是在連結清單的末尾增加新的元素：
同樣地，現在再來看如何使用數組來實作Queue，首先我們使用數組來儲存資料，并定義變量head和tail來記錄Queue的首尾元素。
和Stack的實作方式不同，在Queue中，我們定義了head和tail來記錄頭元素和尾元素。當enqueue的時候，tial加1，将元素放在尾部，當dequeue的時候，head減1，并傳回。
在.NET中有Stack和Queue泛型類，使用Reflector工具可以檢視其具體實作。先看Stack的實作，下面是截取的部分代碼，僅列出了Push，Pop方法，其他的方法希望大家自己使用Reflector檢視：
可以看到.NET中的Stack的實作和我們之前寫的差不多，也是使用數組來實作的。.NET中Stack的初始容量為4，在Push方法中，可以看到當元素個數達到數組長度時，擴充2倍容量，然後将原數組拷貝到新的數組中。Pop方法和我們之前實作的基本上相同，下面是具體代碼，隻截取了部分：
下面再看看Queue的實作：
可以看到.NET中Queue的實作也是基于數組的，定義了head和tail，當長度達到數組的容量的時候，使用了SetCapacity方法來進行擴容和拷貝。
Stack這種資料結構用途很廣泛，比如編譯器中的詞法分析器、Java虛拟機、軟體中的撤銷操作、浏覽器中的回退操作，編譯器中的函數調用實作等等。
4.1 線程堆 (Thread Stack)
是操作系型系統配置設定的一塊記憶體區域。通常CPU上有一個特殊的稱之為堆指針的寄存器 (stack pointer)
。在程式初始化時，該指針指向棧頂，棧頂的位址最大。CPU有特殊的指令可以将值Push到線程堆上，以及将值Pop出堆棧。每一次Push操作都将值存放到堆指針指向的地方，并将堆指針遞減。每一次Pop都将堆指針指向的值從堆中移除，然後堆指針遞增，堆是向下增長的。Push到線程堆，以及從線程堆中Pop的值都存放到CPU的寄存器中。
當發起函數調用的時候，CPU使用特殊的指令将目前的指令指針(instruction
pointer)，如目前執行的代碼的位址壓入到堆上。然後CPU通過設定指令指針到函數調用的位址來跳轉到被調用的函數去執行。當函數傳回值時，舊的指令指針從堆中Pop出來，然後從該指令位址之後繼續執行。
當進入到被調用的函數中時，堆指針減小來在堆上為函數中的局部變量配置設定更多的空間。如果函數中有一個32位的變量配置設定到了堆中，當函數傳回時，堆指針就傳回到之前的函數調用處，配置設定的空間就會被釋放。
如果函數有參數，這些參數會在函數調用之前就被配置設定在堆上，函數中的代碼可以從目前堆往上通路到這些參數。
線程堆是一塊有一定限制的記憶體空間，如果調用了過多的嵌套函數，或者局部變量配置設定了過多的記憶體空間，就會産生堆棧溢出的錯誤。
下圖簡單顯示了線程堆的變化情況。
4.2 算術表達式的求值
Stack使用的一個最經典的例子就是算術表達式的求值了，這其中還包括字首表達式和字尾表達式的求值。發明了使用，一個儲存操作值，一個儲存操作符的方法來實作表達式的求值，具體步驟如下：
1) 當輸入的是值的時候Push到屬于值的棧中。
2) 當輸入的是運算符的時候，Push到運算符的棧中。
3) 當遇到左括号的時候，忽略
4) 當遇到右括号的時候，Pop一個運算符，Pop兩個值，然後将計算結果Push到值的棧中。
下面是在C#中的一個簡單的括号表達式的求值：
運作結果如下：
下圖示範了操作棧和資料棧的變化。
在編譯器技術中，字首表達式，字尾表達式的求值都會用到堆。
4.3 Object-C中以及OpenGL中的圖形繪制
在Object-C以及OpenGL中都存在”繪圖上下文”，有時候我們對局部對象的繪圖不希望影響到全局的設定，是以需要儲存上一次的繪圖狀态。下面是Object-C中繪制一個圓形的典型代碼：
可以看到，在drawGreenCircle方法中，在設定填充顔色之前，我們Push儲存了繪圖上下文的資訊，然後在設定目前操作的一些環境變量，繪制圖形，繪制完成之後，我們Pop出之前儲存的繪圖上下文資訊，進而不影響後面的繪圖。
4.4 一些其他場景
有一個場景是利用stack
處理多餘無效的請求，比如使用者長按鍵盤，或者在很短的時間内連續按某一個功能鍵，我們需要過濾到這些無效的請求。一個通常的做法是将所有的請求都壓入到堆中，然後要處理的時候Pop出來一個，這個就是最新的一次請求。
Queue的應用
在現實生活中Queue的應用也很廣泛，最廣泛的就是排隊了，”先來後到” First come first service
，以及Queue這個單詞就有排隊的意思。
還有，比如我們的播放器上的播放清單，我們的資料流對象，異步的資料傳輸結構(檔案IO，管道通訊，套接字等)
還有一些解決對共享資源的沖突通路，比如列印機的列印隊列等。消息隊列等。交通狀況模拟，呼叫中心使用者等待的時間的模拟等等。
本文簡單介紹了Stack和Queue的原理及實作，并介紹了一些應用。
最後一點點感悟就是不要為了使用資料結構而使用資料結構。舉個例子，之前看到過一個的問題，剛學過Stack可能會想，這個簡單啊，直接将字元串挨個的Push進去，然後Pop出來就可以了，完美的解決方案。但是，這是不是最有效地呢，其實有更有效地方法，那就是以中間為對折，然後左右兩邊替換。
![在DOS下運作不了ipconfig指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)