队列也是一种线性结构。有着先进先出的特性。如图
很显然队列内部的存储结构也是线性表或者链表。好现在考虑线性表，假如用数组存，入队非常简单就是在数组的后面赋值就OK了，但是出队就出现问题了，比如A元素进队 在数组中是a[0]存的现在要出队的数据根据队列先进先出的特性,我们现在要取出a[0],可以很显然直接砍掉数组的前面的元素是不可能的如果调用Array.Copy或者写个算法循环移位的话就存在O(n)的时间复杂度，可是很显然仅仅是一个出队的操作，如果有O(n)的时间复杂度是不划算的所以我们采取了一种策略。
设置一个头索引front和一个尾索引rear。入队就让rear后移，出队就取出front 然后后移,可以这里又存在一个问题了如果front后移了front前面的空间不是浪费了么?所以这里我们又得采取一种策略那就是循环队列。简单点说rear到达MaxSize的时候 再前移就是回到了0 如图
这样简单点说只需要让front不断的后移动知道它移动到rear就全部出队了 队列就是空的了或者说设置一个count出队就+1出队就-1 count == 0队列就是空的看你怎么理解了
代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 栈队列
{
public class MyQueue<T>
{
//队列的最大长度一般不改变，而且固定
private readonly int MaxSize = 5;
//数组首元素索引
int front = 0;
//数组尾元素的下一个的索引
int rear = 0;
//书上是用 (rear - front + MaxSize)%MaxSize 这点我觉得不妥欢迎大家对这点留言讨论
private int count = 0;
//队列的长度
public int Count
{
//rear 和 front的比较要分情况
get {
//1.rear > front ___________front_________rear____;
//2.front > rear ________rear______front________-
//3.重合
//都是
//不用+1因为rear本身就指向的是尾巴元素的下一个元素(本来要加1的2-4的长度是4-2+1=3)
return count;
}
}
//我们把队列设置成动态增长的
T[] nums;
//初始化内部数组
public MyQueue()
{
nums = new T[MaxSize];
}
public MyQueue(T[] items):this()
{
//将每个元素压栈
foreach (T item in items)
{
EnQueue(item);
}
}
/// <summary>
/// 入队
/// </summary>
/// <param name="elem"></param>
public void EnQueue(T elem)
{
//rear如果和front重合了队列就满了
if (Count >= MaxSize)
{
throw new Exception("队列是满的");
}
nums[rear] = elem;
//为了保险怕rear超过MaxSize
rear = (rear + 1) % MaxSize;
count++;
}
/// <summary>
/// 出队并且返回对首元素
/// </summary>
/// <returns></returns>
public T DeQueue()
{
if (count <= 0)
{
throw new Exception("队列是空的");
}
T data = nums[front];
//重新设置队列起始位置,循环队列
front = (front + 1) % MaxSize;
count--;
return data;
}
/// <summary>
/// 返回队首的对象但是不将其移除
/// </summary>
/// <returns></returns>
public T Peek()
{
if (count <= 0)
{
throw new Exception("队列是空的");
}
return nums[front];
}
/// <summary>
/// 队列的显示
/// </summary>
/// <returns></returns>
public override string ToString()
{
StringBuilder sb = new StringBuilder();
int index = front;
int length = count;
//输出length次
while (length-->0)
{
sb.Append(nums[index++ % MaxSize]+" ");
}
return sb.ToString();
}
}
}
.net框架的源码也是使用的这种循环队列的方式
上篇的栈我没有用链表这次的队列 我也就用链表实现了一下队列 链式队列有个好处出队的时候砍下队头 只需要设置队列头节点的链式关系就OK了 不需要调Array.Copy或者循环移位链式队列代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 链式队列
{
class MyQueue<T>
{
//队列的最大长度
int MaxSize = 5;
//front是个哨兵元素他的.next即为队首值
QNode<T> front;
QNode<T> rear;
//队列的长度
int count;
public int Count
{
get { return count; }
}
public MyQueue()
{
//初始化头节点
rear = front = new QNode<T>();
}
public MyQueue(T[] nums)
: this()
{
foreach (T item in nums)
{
EnQueue(item);
}
}
/// <summary>
/// 入队
/// </summary>
/// <param name="elem"></param>
public void EnQueue(T elem)
{
if (Count >= MaxSize)
{
throw new Exception("队列是满的");
}
QNode<T> q = new QNode<T>();
q.data = elem;
if (front == null)
{
front = q;
rear = q;
return;
}
rear.next = q;
rear = q;
count++;
}
/// <summary>
/// 出队并返回队首元素
/// </summary>
/// <returns></returns>
public T DeQueue()
{
if (Count<= 0)
{
throw new Exception("栈是空的");
}
QNode<T> q = new QNode<T>();
//取得队首元素
q = front.next;
//获取队首元素的值
T data = q.data;
//重新设置链表关系 此时原来q的原来的引用front.next重新指向队首 q会被GC回收
front.next = q.next;
count--;
return data;
}
/// <summary>
/// 取出队列首元素，但是首元素不出队列
/// </summary>
/// <returns></returns>
public T Peek()
{
return front.next.data;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
QNode<T> q = front.next;
while (q != null)
{
sb.Append(q.data+" ");
q = q.next;
}
return sb.ToString();
}
}
}
测试代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 链式队列
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("请输入测试数组类似5 4 3");
string[] s = Console.ReadLine().Split(‘ ‘);
int[] nums = new int[s.Length];
for (int i = 0; i < s.Length; i++)
{
nums[i] = Convert.ToInt32(s[i]);
}
Console.WriteLine("将测试数组入队");
MyQueue<int> queue = new MyQueue<int>(nums);
Console.WriteLine("输出队列");
Console.WriteLine(queue.ToString());
Console.WriteLine("将首元素出队并显示");
Console.WriteLine(queue.Peek());
Console.WriteLine("将首元素移除并显示队列");
queue.DeQueue();
Console.WriteLine(queue.ToString());
Console.WriteLine("输出队列长度");
Console.WriteLine(queue.Count);
Console.WriteLine("再次入队999");
queue.EnQueue(999);
//queue.EnQueue(77);
Console.WriteLine("显示队列");
Console.WriteLine(queue.ToString());
Console.Read();
}
}
}
结果如图:
原文：http://blog.csdn.net/qzyf1992/article/details/20310811
