栈与队列Stack&Queue

栈与队列

线性表插入和删除操作不受限制在任意位置进行
栈和队列是两种特殊的线性表。他们的数据元素之间具有顺序的逻辑关系，都采用顺序结构和链式结构存储

栈的插入和删除操作只允许在线性表的尾端(栈顶Top)进行
队列插入操作限定在线性表的尾部而其它操作限定在表的头部进行

栈的特点为后进先出，队列先进先出

栈

表尾称为栈顶（Top）,另一端称为栈底（Bottom），当栈中没有数据元素时叫空栈（Empty Stack）
方法：

Push（）入栈 //添加数据
Pop（）出栈 //删除数据，返回被删除的数据
Peek（）//取得栈顶的元素，不删除
ToArray() //方法创建数组并将堆栈元素复制到其中
Contains() //方法判断一个元素是否在栈中
Clear（）//清空所有数据
Count //取得栈中元素的个数

接口定义：

public interface IStack{
int Count{get;}//求栈中元素个数
int GetLength();//求栈的长度
bool IsEmpty();//判断栈是否为空
void Clear();//清空操作
void Push(T item);//入栈操作
T Pop();//出栈操作
T Peek();//取栈顶元素
}

栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构
用连续的存储空间来存储栈中的数据元素(使用数组)，这样的栈称为顺序栈(Sequence Stack)
类似于顺序表，用一维数组来存放顺序栈中的数据元素
栈顶指示器 top 设在数组下标为 0 的端，top随着插入和删除而变化，当栈为空时，top=-1

栈的另外一种存储方式是链式存储，这样的栈称为链栈(Linked Stack)
由于链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点

示例

// Stack<T> staA = new Stack<T>();
Stack<string> staA = new Stack<string>();            
staA.Push("one");            
staA.Push("two");            
staA.Push("three");            
staA.Push("four");            
staA.Push("five");            
foreach (string a in staA)//遍历元素，将之变成string类型            
{                
  Console.WriteLine(a);            
}             
//peek是把栈顶元素弹出（取出），但不删除            
Console.WriteLine("取出的元素是：{0}", staA.Peek());            
//pop是把栈顶的元素弹出（取出），并将其删除            
Console.WriteLine("删除的栈顶元素是：{0}",staA .Pop ());             
//此时再输出一次栈的元素，会发现five被删除了            
foreach (string b in staA)            
{                
  Console.ForegroundColor = ConsoleColor.Blue;                
  Console.WriteLine(b);            
}             
//ToArray从栈底到栈顶将一个栈复制到另一个栈中            
Stack<string> staB = new Stack<string>(staA.ToArray());            
foreach (string c in staB)            
{                
  Console.ForegroundColor = ConsoleColor.Cyan;                
  Console.WriteLine(c);            
}             
Console.WriteLine(" ");            
Console.ForegroundColor = ConsoleColor.DarkRed;            
//contains方法，判断一个元素是否在栈中            
Console.WriteLine("six是否在栈中？");            
Console.WriteLine(staA .Contains ("six"));

队列

插入操作的表尾称为队尾(Rear)，把进行其它操作的头部称为队头(Front)。当队列中没有数据元素时称为空队列(EmptyQueue)
方法：

Enqueue() 入队（放在队尾）
Dequeue() 出队（移除队首元素，并返回被移除的元素）
Peek() 取得队首的元素，不移除
Clear() 清空元素

接口定义：

public interface IQueue<T>{
int Count{get;}//取得队列长度的属性
int GetLength();//求队列的长度
bool IsEmpty();//判断队列是否为空
void Clear();//清空队列
void Enqueue(T item);//入队
T Dequque();//出队
T Peek();//取队头元素
}

用连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列(SequenceQueue)
类似于顺序栈，用一维数组来存放顺序队列中的数据元素。队头位置设在数组下标为 0 的端，用 front 表示；队尾位置设在数组的另一端，用rear 表示
front 和 rear 随着插入和删除而变化。当队列为空时， front=rear=-1

队列的另外一种存储方式是链式存储，这样的队列称为链队列(LinkedQueue)
由于链队列的操作只是在一端进行，为了操作方便，把队头设在链表的头部，并且不需要头结点