一、简介
作为一个程序员,算法是一个永远都绕不过去的话题,虽然在大学里参加过ACM的比赛,没记错的话,浙江赛区倒数第二,后来不知怎么的,就不在Care他了,但是现在后悔了,非常的后悔!!!如果当时好好学算法的话,现在去理解一些高深的框架可能会很easy,现在随着C#基础和Web技能的提升,发现哪里都用到算法,但是,很无奈.所以,从今天开始,要重新对自己定位,不能做一个工具的使用者.起码要做到知其所以然.好了,废话不多说,算法之旅,算是正式开始了.希望这个过程能贯穿我的整个职业生涯.甚至整个人生.
二、队列
关于队列,不多说,只要做了一两年程序员,对他肯定不陌生,可以说哪里都有他.关于他的概念也很简单.类似于我们生活中的排队打饭,当然先排队的肯定先打到饭.专业术语叫做先进先出.下面用基于object数组的C#实现,代码如下:
/// <summary>
/// 自定义队列
/// </summary>
public class Queue
{
private object[] _array;
/// <summary>
/// 队列头
/// </summary>
private int _head;
/// <summary>
/// 队列尾
/// </summary>
private int _tail;
/// <summary>
/// 当前数组的长度
/// </summary>
private int _size;
/// <summary>
/// 使用默认构造函数时,给定队列默认的长度4
/// </summary>
public Queue() : this(4)
{
}
/// <summary>
/// 初始化指定容量的队列
/// </summary>
/// <param name="capacity"></param>
public Queue(int capacity)
{
if (capacity < 0)
{
throw new Exception("初始容量不能小于0");
}
_array = new object[capacity];
_head = 0;
_tail = 0;
_size = 0;
}
/// <summary>
/// 入队
/// </summary>
public virtual void Enqueue(object obj)
{
_array[_tail] = obj;
_tail = _tail + 1;
_size++;
}
/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
public virtual object Dequeue()
{
if (Count == 0)
{
throw new InvalidOperationException("当前队列为空,无法执行Dequeue操作");
}
object result = _array[_head];
_array[_head] = null;
_head = _head + 1;
_size--;
return result;
}
/// <summary>
/// 当前队列的长度
/// </summary>
public int Count { get { return _size; } }
}
控制台调用代码如下:
class Program
{
static void Main(string[] args)
{
var q = new Queue();
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
q.Enqueue(4);
Console.WriteLine("出队:{0},{1},{2},{3}", q.Dequeue(), q.Dequeue(), q.Dequeue(), q.Dequeue());
Console.ReadKey();
}
}
先进先出,但是有问题,上面给定初始长度为4,所以全局数组的长度为4,当你调用Equeue方法5次,数组会报溢出错误,所以,如果当前队列的长度等于我们给它的初始值时,必须进行一个数组的Copy操作,将当前数组拷贝到一个容量更大的数组中去,这里MS采用的算法时,每次乘以2的递增.修改代码如下:
/// <summary>
/// 自定义队列
/// </summary>
public class Queue
{
private object[] _array;
/// <summary>
/// 队列头
/// </summary>
private int _head;
/// <summary>
/// 队列尾
/// </summary>
private int _tail;
/// <summary>
/// 当前数组的长度
/// </summary>
private int _size;
/// <summary>
/// 使用默认构造函数时,给定队列默认的长度32
/// </summary>
public Queue() : this(4)
{
}
/// <summary>
/// 初始化指定容量的队列
/// </summary>
/// <param name="capacity"></param>
public Queue(int capacity)
{
if (capacity < 0)
{
throw new Exception("初始容量不能小于0");
}
_array = new object[capacity];
_head = 0;
_tail = 0;
_size = 0;
}
/// <summary>
/// 入队
/// </summary>
public virtual void Enqueue(object obj)
{
if (_array.Length == _size)
{
int capacity = _array.Length * 2;
SetCapacity(capacity);
}
_array[_tail] = obj;
_tail = _tail + 1;
_size++;
}
/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
public virtual object Dequeue()
{
if (Count == 0)
{
throw new InvalidOperationException("当前队列为空,无法执行Dequeue操作");
}
object result = _array[_head];
_array[_head] = null;
_head = _head + 1;
_size--;
return result;
}
/// <summary>
/// 当前队列的长度
/// </summary>
public int Count { get { return _size; } }
/// <summary>
/// 重新设定原始数组的容量
/// </summary>
private void SetCapacity(int capacity)
{
var newArray = new object[capacity];
Array.Copy(_array,newArray, _array.Length);
_array = newArray;
_head = 0;
_tail = _size;
}
}
ok,现在每次都会以原数组*2的长度扩展原始数组,但是还是有问题,如果这中间存在出队,实际的_size会减一,但是数组实际的长度还是为原来的,区别就是出队的那个元素的位置会被设置为null,会存在以下bug:
var q = new Queue();
q.Enqueue(1);
q.Dequeue();
q.Enqueue(2);
q.Enqueue(3);
q.Enqueue(4);
q.Enqueue(5);
Console.WriteLine("出队:{0},{1},{2},{3}", q.Dequeue(), q.Dequeue(), q.Dequeue(), q.Dequeue());
Console.ReadKey();
出队,导致_size-1,但是原始数组的长度还是为4,千万不要说,Dequeue的时候,让第一个元素的内存释放数组长度变为3,这是不可能的,至少我不知道.所以,这里还需要对算法进行改进.好了,到这里我就做不下去了,看了MS的实现,估计是对数组对了特殊的内存处理,没有办法处理出队后第一个元素为null,但是它还是会算到计算长度里面去,如果引入新的变量去计算实际的长度,不用说,m目测会有内存浪费!mmp.如果你们有好的办法,请告知.