队列
队列(Queue)是插入操作限定在表的尾部而其它操作限定在表的头部进行的线性表。把进行插入操作的表尾称为队尾(Rear)，把进行其它操作的头部称为队头(Front)。当队列中没有数据元素时称为空队列(Empty Queue)。
队列通常记为： Q= (a1,a2,…,an)，Q是英文单词queue的第 1 个字母。a1为队头元素，an为队尾元素。这n个元素是按照a1,a2,…,an的次序依次入队的，出对的次序与入队相同，a1第一个出队，an最后一个出队。所以，对列的操作是按照先进先出(First In First Out)或后进后出( Last In Last Out)的原则进行的，因此，队列又称为FIFO表或LILO表。队列Q的操作示意图如图所示。
在实际生活中有许多类似于队列的例子。比如，排队取钱，先来的先取，后来的排在队尾。
队列的操作是线性表操作的一个子集。队列的操作主要包括在队尾插入元素、在队头删除元素、取队头元素和判断队列是否为空等。与栈一样，队列的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在物理存储结构层次上的。因此，把队列的操作作为逻辑结构的一部分，每个操作的具体实现只有在确定了队列的存储结构之后才能完成。队列的基本运算不是它的全部运算，而是一些常用的基本运算。
BCL 中的队列
C#2.0 以下版本提供了非泛型的Ｑueue类
C#2.0 提供了泛型Queue<T>类
方法
1，Enqueue()入队(放在队尾)
2，Dequeue()出队(移除队首元素，并返回被移除的元素)
3，Peek()取得队首的元素，不移除
4，Clear()清空元素
属性
5，Count获取队列中元素的个数
顺序队列
用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列(Sequence Queue)。类似于顺序栈，用一维数组来存放顺序队列中的数据元素。队头位置设在数组下标为 0 的端，用 front 表示；队尾位置设在数组的另一端，用 rear 表示。 front 和 rear 随着插入和删除而变化。当队列为空时， front=rear=-1。
图是顺序队列的两个指示器与队列中数据元素的关系图。
using System;
namespace MyQueueDS
{
class MainClass
{
public static void Main (string[] args)
{
MyQueue<int> queue = new MyQueue<int> ();
Console.WriteLine (queue.ToString ());
queue.Enqueue (1);
queue.Enqueue (2);
queue.Enqueue (3);
queue.Enqueue (4);
queue.Enqueue (5);
Console.WriteLine (queue.ToString ());
queue.Dequeue ();
Console.WriteLine (queue.ToString ());
Console.WriteLine (queue.Count);
queue.Clear ();
Console.WriteLine (queue.ToString ());
Console.WriteLine (queue.IsEmpty);
}
}
class MyQueue<T>:IMyQueue<T> {
//private T firstItem;
//private T lastItem;
private int count;
private T[] items = new T[10];
public void Enqueue(T item) {
if (count == items.Length) {
Console.WriteLine ("队列已满");
} else {
items [count] = item;
count++;
}
}
public void Dequeue() {
if (count == 0) {
Console.WriteLine ("队列是空的");
return;
}
for (int i = 1; i < items.Length; i++) {
items [i - 1] = items [i];
}
count--;
}
public T Peek() {
if (count == 0) {
Console.WriteLine ("队列是空的");
return default(T);
}
return items [0];
}
public void Clear() {
for (int i = 0; i < items.Length; i++) {
items [i] = default(T);
}
count = 0;
}
public int Count {
get {
return count;
}
}
public T this[int index] {
get {
return getElement (index);
}
}
public T getElement(int index) {
if (count == 0) {
Console.WriteLine ("队列是空的");
return default(T);
}
return items [index];
}
public bool IsEmpty {
get {
return count == 0;
}
}
public override string ToString ()
{
string str = "";
if (items.Length == 0) {
str = "队列是空的";
} else {
foreach(T item in items) {
str += item.ToString() + ",";
}
}
str = str.Remove (str.Length - 1);
return str;
}
}
interface IMyQueue<T> {
void Enqueue(T item);
void Dequeue();
T Peek();
void Clear();
int Count { get; }
T this[int index] { get; }
T getElement(int index);
bool IsEmpty { get; }
}
}
如果再有一个数据元素入队就会出现溢出。但事实上队列中并未满，还有空闲空间，把这种现象称为“假溢出”。这是由于队列“队尾入队头出”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列(Circular sequence Queue)。
循环顺序队列
循环队列如图所示。
代码实现思路：
把循环顺序队列看作是一个泛型类，类名叫CSeqStack<T>，“ C”是英文单词circular的第1个字母。CSeqStack<T>类实现了接口IQueue<T>。用数组来存储循环顺序队列中的元素，在CSeqStack<T>类中用字段data来表示。用字段maxsize表示循环顺序队列的容量，maxsize的值可以根据实际需要修改，这通过CSeqStack<T>类的构造器中的参数size来实现，循环顺序队列中的元素由data[0]开始依次顺序存放。字段front表示队头，front的范围是0到maxsize-1。字段rear表示队尾，rear的范围也是0到maxsize-1。如果循环顺序队列为空，front=rear=-1。当执行入队列操作时需要判断循环顺序队列是否已满，如果循环顺序队列已满，(rear + 1) % maxsize==front，循环顺序队列已满不能插入元素。所以，CSeqStack<T>类除了要实现接口IQueue<T>中的方法外，还需要实现判断循环顺序队列是否已满的成员方法。
链队列
队列的另外一种存储方式是链式存储，这样的队列称为链队列(Linked Queue)。同链栈一样，链队列通常用单链表来表示，它的实现是单链表的简化。所以，链队列的结点的结构与单链表一样，如图所示。由于链队列的操作只是在一端进行，为了操作方便，把队头设在链表的头部，并且不需要头结点。
public class Node<T>
{
private T data; //数据域
private Node<T> next; //引用域
//构造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
//构造器
public Node(Node<T> p)
{
next = p;
}
//构造器
public Node(T val)
{
data = val;
next = null;
}
//构造器
public Node()
{
data = default(T);
next = null;
}
//数据域属性
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}
//引用域属性
public Node<T> Next
{
get
{
return next;
}
set
{
next = value;
}
}
}
把链队列看作一个泛型类，类名为LinkQueue<T>。LinkQueue<T>类中有两个字段front和rear，表示队头指示器和队尾指示器。由于队列只能访问队头的数据元素，而链队列的队头指示器和队尾指示器又不能指示队列的元素个数，所以，与链栈一样，在LinkQueue<T>类增设一个字段num表示链队列中结点的个数。
using System;
namespace MyQueueDS
{
class MainClass
{
public static void Main (string[] args)
{
MyLinkQueue<int> queue = new MyLinkQueue<int> ();
Console.WriteLine (queue.ToString ());
queue.Enqueue (1);
queue.Enqueue (2);
queue.Enqueue (3);
queue.Enqueue (4);
queue.Enqueue (5);
queue.Enqueue (6);
Console.WriteLine (queue.ToString ());
queue.Dequeue ();
Console.WriteLine (queue.ToString ());
Console.WriteLine ("peek" + queue.Peek());
Console.WriteLine ("count:" + queue.Count);
queue.Clear ();
Console.WriteLine ("count:" + queue.Count);
Console.WriteLine (queue.ToString ());
Console.WriteLine (queue.IsEmpty);
}
}
class MyLinkQueue<T>:IMyQueue<T> {
private LinkNode<T> headNode;
public void Enqueue(T item) {
if (headNode == null) {
headNode = new LinkNode<T> ();
headNode.Data = item;
} else {
LinkNode<T> tempItem = headNode;
while (true) {
if (tempItem.Next != null) {
tempItem = tempItem.Next;
} else {
break;
}
}
LinkNode<T> newNode = new LinkNode<T> (item);
tempItem.Next = newNode;
}
}
public void Dequeue() {
if (headNode == null) {
Console.WriteLine ("队列是空的");
return;
}
if (headNode.Next == null) {
headNode = null;
} else {
headNode = headNode.Next;
}
}
public T Peek() {
if (headNode == null) {
Console.WriteLine ("队列是空的");
return default(T);
}
return headNode.Data;
}
public void Clear() {
if (headNode == null) {
Console.WriteLine ("队列是空的");
return;
}
headNode = null;
}
public int Count {
get {
int count = 1;
if (headNode == null) {
Console.WriteLine ("队列是空的");
count = 0;
} else {
LinkNode<T> tempItem = headNode;
while (true) {
if (tempItem.Next != null) {
tempItem = tempItem.Next;
count++;
} else {
break;
}
}
}
return count;
}
}
public T this[int index] {
get {
return getElement (index);
}
}
public T getElement(int index) {
int count = 0;
if (headNode == null) {
Console.WriteLine ("队列是空的");
} else {
LinkNode<T> tempItem = headNode;
while (true) {
if (tempItem.Next != null) {
tempItem = tempItem.Next;
count++;
if(count == index) {
return tempItem.Data;
}
} else {
break;
}
}
}
return default(T);
}
public bool IsEmpty {
get {
return headNode == null;
}
}
public override string ToString ()
{
string str = "";
if (headNode == null) {
return "队列是空的";
} else {
LinkNode<T> tempItem = headNode;
str += headNode.Data + ",";
while (true) {
if (tempItem.Next != null) {
tempItem = tempItem.Next;
str += tempItem.Data + ",";
} else {
break;
}
}
}
str = str.Remove (str.Length - 1);
return str;
}
}
class LinkNode<T> {
private T data;
private LinkNode<T> next;
public LinkNode(T value) {
data = value;
}
public LinkNode(T value, LinkNode<T> next) {
data = value;
this.next = next;
}
public LinkNode(LinkNode<T> next) {
this.next = next;
}
public LinkNode() {
data = default(T);
next = null;
}
public T Data {
get { return data; }
set { data = value; }
}
public LinkNode<T> Next {
get { return next; }
set { next = value; }
}
}
interface IMyQueue<T> {
void Enqueue(T item);
void Dequeue();
T Peek();
void Clear();
int Count { get; }
T this[int index] { get; }
T getElement(int index);
bool IsEmpty { get; }
}
}