[翻译]C#数据结构与算法 – 第五章栈与队列（Part 1）
第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
补充：软件开发 , C# ,
