第5章 棧與隊列
以列表組織數據是很自然的方式。之前我們使用Array與ArrayList將數據作為列表組織。雖然這些數據結構幫助我們將數據以一種適合處理的格式組織，但沒有一種結構提供了一種真實的抽象來實際地設計與實現問題的解決方案。
棧與隊列是兩種面向列表數據結構，其提供了易於理解的抽象。棧中的數據添加與移除都是由列表的一端進行，而隊列中的數據由列表的一端添加並由列表的另一端移除。棧在編程語言的實現中廣泛使用，從表達式評估到函數調用等一切問題。隊列用於處理操作系統進程的優先級調用及模擬顯示世界中事件的發生，如銀行的收銀台及大樓中的電梯操作。
C#提供了兩個類來使用這兩個數據結構：Stack類與Queue類。我們將討論怎樣使用這些類然後看一下本章中一些實際的例子。
棧，棧的實現與STACK類
棧是最常使用的數據結構，就像我們剛剛提到的那樣。我們將棧定義為一個項目的列表，其僅可以由列表的尾部訪問，這個尾部我們稱為棧的頂部。一個棧的標准模式就像一個自助餐廳的一摞餐盤。盤子總是由一摞的頂部被取走，當洗碗工或服務生把盤子放回時，仍然是放回頂部。棧是一種被稱作後進先出（LIFO）的數據結構。
棧操作
棧的兩個最主要操作是向棧添加項與由棧中移除項。Push操作向棧中添加一個項，Pop操作由棧中移除一個項。圖5.1展示了這些操作。
另一個在棧上完成的主要操作是查看頂部元素。Pop操作雖返回頂部元素，但是此操作也將這個元素由棧頂部移除。我們僅是要在不移除其的情況下來查看頂部的元素。在C#中這個操作名為Peek，在其他語言或實現中這個名稱可能不同（如為Top）。
Push，Pop與Peek是使用棧時我們進行的主要操作；同時，還有許多其它的方法及屬性需要我們學習並嘗試操作。由一個棧中一次移除所有項是很有用的。通過調用Clear操作可以將一個棧完全清空。隨時可以獲取到棧中項的數目也是很有用的。通過調用Count屬性可以實現這個目的。許多操作都通過一個返回true或false的StackEmpty方法來判斷棧的狀態，我們也可以使用Count屬性實現同樣的目的。
.NET Framework中的Stack類實現了以上提到的這些以及更多的屬性與方法，但是在我們學習使用Stack之前，先來了解一下如果沒有Stack類，我們怎樣實現一個棧。
一個棧類的實現
一個棧的實現需要使用底層的數據結構來存儲數據。我們將選擇ArrayList因為這樣做我們就無需為當新項被入棧時調整列表的大小而發愁。
由於C#擁有極好的面向對象編程的特性，我們將這個棧實現為一個類，稱作CStack。這個類中我們將實現一個構造函數，上面提到的那些方法以及Count這個屬性以展示怎樣在C#中完成這個工作。
首先讓我們實現這個類中需要的私有數據成員。
這個類中最主要的變量是一個用來存儲棧項目的ArrayList對象。我們需要跟蹤的僅有的另一個數據是棧的頂部，我們將用一個簡單的整型變量來用作索引。這個變量在一個CStack對象初始化時被設置為-1，每當一個項目被壓入棧，這個變量將增1。
構造函數除了將索引變量初始化-1外不再做其它工作。第一個要實現的方法是Push，其代碼調用ArrayList的Add方法將要添加的值傳遞給ArrayList。Pop方法完成3個工作：首先調用RemoveAt方法取得棧頂部元素（並由ArrayList中移除），將索引值減1，最後，返回出棧的對象。
Peek方法的實現可以通過Item索引器並使用索引變量作為參數獲取所需的值。Clear方法簡單調用了ArrayList類中等價的方法。Count屬性被實現為一個只讀屬性，因為我們不希望不小心更改了棧中項的數目。
如下是完成的代碼：
class CStack
{
private int p_index;
private ArrayList list;
public CStack()
{
list = new ArrayList();
p_index = -1;
}
public int count
{
get { return list.Count; }
}
public void push(object item)
{
list.Add(item);
p_index++;
}
public object pop()
{
object obj = list[p_index];
list.RemoveAt(p_index);
p_index--;
return obj;
}
public void clear()
{
list.Clear();
p_index = -1;
}
public object peek()
{
return list[p_index];
}
}
接下來讓我們使用這段代碼完成一個使用棧解決問題的程序。
回文是一種正向與反向拼寫都相同的字符串。如：”dad”,”madam”與”sees”都是回文，而像”hello”就不是回文。一種檢查字符串是否為回文的方式就是使用棧。一般的算法是逐個字符的讀取字符串並在讀取時將每個字符如棧。這起到了一個將字符串字符反向保存的效果。下一步是將每一個字符出棧，同時由原始字符串開始處比較相應的字符。如果在任何位置兩個字符不相同，字符串就不是一個回文，程序就可以停止。如果比較可以從頭進行到尾，這個字符串就是一個回文。
如下是程序，只列出Main函數，因為我們已定義了CStack類：
static void Main(string[] args)
{
CStack alist = new CStack();
string ch;
string word = "sees";
bool isPalindrome = true;
for (int x = 0; x < word.Length; x++)
alist.push(word.Substring(x, 1));
int pos = 0;
while (alist.count > 0)
{
ch = alist.pop().ToString();
if (ch != word.Substring(pos, 1))
{
isPalindrome = false;
break;
}
pos++;
}
if (isPalindrome)
Console.WriteLine(word + " is a palindrome.");
else
Console.WriteLine(word + " is not a palindrome.");
Console.Read();
}
Stack類
Stack類是一個表現為LIFO的實現ICollection接口的集合類/棧。.NET Framework中的棧類被實現為一個循環緩沖器，其允許如棧的項所需的空間可以被動態分配。
Stack類中包含了用於入棧，出棧及獲取棧頂值的方法。同樣提供了獲取棧中元素數目的屬性，清空棧中值的方法，以及將棧轉換為數組的方法。首先我們來研究一下Stack類的構造函數。
Stack類構造函數
有三種方式來初始化一個Stack對象。默認構造函數初始化一個空的棧並將Capacity屬性初始化為10。默認構造函數以如下方式調用：
Stack myStack = new Stack();
一個泛型棧以如下方式初始化：
Stack<string> myStack = new Stack<string>();
每當棧中的元素數達到棧最大容量，容量會被加倍。
Stack的第二個構造函數允許你由另一個集合對象創建一個棧對象。例如，你可以向構造函數傳遞一個數組，一個棧將由已存在數組元素來創建：
string[] names = newstring[]{"Raymond","David", "Mike"};
Stack nameStack = new Stack(names);
執行Pop方法將首先由棧中移除”Mike”。
你也可以在初始化一個棧對象的同時指定棧的初始容量。當你可以提前知道要在棧中存儲多少個元素時這個構造函數就可以發揮作用。如果以這種方式來構建你的棧你可以使你的程序更高效。如果你的棧有20個元素並且已經達到最大容量，添加一個新元素將會觸發20+1次操作，因為每一個元素都需要被移動來適應新的元素。
在初始化棧同時指定初始大小的代碼如下：
Stack myStack = new Stack(25);
棧的主要操作
在棧上執行的主要操作為Push與Pop。使用Push方法將數據入棧。使用Pop方法完成數據出棧操作。讓我們在使用棧計算簡單的算術表達式這個問題環境中學習這些方法。
表達式求值程序使用兩個棧，其中一個用於操作數，另一個用於運算符。一個算術表達式存儲於被作為字符串存儲。通過使用for循環讀取表達式中的每個字符，我們將字符串分析為單獨的符號。如果符號是一個數字，將其放入數字棧。如果符號是一個運算符，將其放入運算符棧。因為我們執行中綴表達式，在執行一個操作之前我們需要等待兩個操作數入棧完成。在這一時刻，我們將兩個操作數前後出棧並執行指定的算術運算。結果被重新入棧來作為下一次計算的第一個表達式。這個過程持續到我們對所有的數字完成入棧與出棧操作。
如下是代碼：
using System;
using System.Collections;
using System.Text.RegularExpressions;
namespace csstack
{
class Class1
{
static void Main(string[] args)
{
Stack nums = new Stack();
Stack ops = new Stack();
string expression = "5 + 10 + 15 + 20";
Calculate(nums, ops, expression);
Console.WriteLine(nums.Pop());
Conso
