[翻译]C#数据结构与算法 – 第五章栈与队列（Part 2）


		队列，Queue类及一个队列类的实现 
    队列是这样一种数据结构，数据由列表的尾部进入，并由列表的头部被移除。队列用于按项的出现顺序来存储它们。队列是先进先出（FIFO）数据结构的一个代表。队列常用于提交给操作系统的命令的处理或提交给一个打印池任务的处理，另外模拟程序使用队列模型模拟排队等候的顾客。 
队列操作 
与队列相关的两个主要操作是向队列中添加一个项目与由队列中移除一个项目。向队列中添加项的操作被称作入队（Enqueue），由队列移除一个项的操作被称作出队（Dequeue）。入队操作向队列的尾部添加一个项，出队操作由队列的头部移除一个项。图5.2展示了这些操作。 
 
    另一个在队列上执行的主要操作是查看头部的项目。Peek方法，类似Stack类中的同名方法，用于查看起始位置的项目。这个方法仅返回这个项目而不是将其由队列中移除。 
    Queue类中有许多其它属性可以用来辅助我们的编程。然而，在我们讨论它们之前，让我们看一下怎样实现一个队列类。 
实现一个队列 
    使用ArrayList来实现一个队列类几乎是不用多想的，正如我们栈类的实现。由于其内置的特性，ArrayList是实现这些类型数据结构的一个极佳选择。当我们需要向队列插入一个项，ArrayList的Add方法将元素放置在列表中下一个空闲位置。当我们需要由队列中移除开始位置的项时，ArrayList将列表中剩余项目依次向前移动一个位置。我们不需要维护一个占位标志，其可能导致代码中出现隐蔽的错误。 
    下面这个队列类的实现包含了EnQueue，DeQueue，ClearQueue（清空队列），Peek方法与Count属性以及一个默认的构造函数： 
public class CQueue 
{ 
private ArrayList pqueue; 
 
public CQueue() 
{ 
pqueue = new ArrayList(); 
} 
 
public void EnQueue(object item) 
{ 
pqueue.Add(item); 
} 
 
public void DeQueue() 
{ 
pqueue.RemoveAt(0); 
} 
 
public object Peek() 
{ 
return pqueue[0]; 
} 
 
public void ClearQueue() 
{ 
pqueue.Clear(); 
} 
 
public int Count() 
{ 
return pqueue.Count; 
} 
} 
Queue类：一个示例程序 
之前我们已经介绍了Queue类中的主要方法，并在实现一个自己的队列类的过程中学习了它们。我们在使用队列作为基础数据结构的一个特殊的编程问题中进一步探寻这些方法。首先，我们需要提几个Queue对象的基本属性。 
    当一个新的Queue对象被初始化，这个队列的默认容量为32。通过定义，当队列被填满，其大小将以2倍方式增长。这意味着当一个队列初始容量被填满，其容量将变为64.而且这个数字没有限制。当你初始化一个队列时，你可以指定一个不同的初始容量。如下所示： 
Queue myQueue = new Queue(100); 
这个语句将队列的容量设置为100。你也可以更改增长的倍数，其作为第二个参数传入构造函数，如下： 
Queue myQueue = new Queue(32, 3); 
    这行语句在默认初始容量的基础上指定了一个3倍的增长速度。即使这种情况下需要的容量与默认初始容量相同你也需要手工指定，因为此时类构造器寻找一个与默认构造函数是不同签名的函数。 
一个泛型的队列的初始化方式如下： 
Queue<int> numbers = new Queue<int>(); 
    正如之前提到的，队列常用来模拟人们排队的情况。一种场景是我们可以用队列模拟位于Elks Lodge的年度单身午夜舞会。男士女士各排成一队进入聚会地。舞台非常小同一时间仅可以供3对男女。由于舞台空间所限，当有空存在时，由男女各自的队列中请出第一个组成一对舞伴。当这一对被由队列中取出后，排在后一位男士与女士移动到队列的最前列。 
    当这个动作发生时，程序将显示这一对舞伴已经接下来队列中最前面的人。如果没有一对完整的舞伴，队列中下一个人将被宣布。如果队列中没有剩余的人，将宣布这种情况。 
    首先，让我们看一下我们用来模拟的数据： 
F Jennifer Ingram M Frank Opitz M Terrill Beckerman M Mike Dahly F Beata Lovelace M Raymond Williams F Shirley Yaw M Don Gundolf F Bernica Tackett M David Durr M Mike McMillan F Nikki Feldman 
我们使用一个数据结构来表示每一个舞者，两个简单的String类的方法（Chars与Substring）被用构建一个舞者。如下是程序： 
using System; 
using System.Collections; 
using System.IO; 
 
namespace csqueue 
{ 
public struct Dancer 
{ 
public string name; 
public

补充：软件开发 , C# ,