一、简介
作为一个程序员,算法是一个永远都绕不过去的话题,虽然在大学里参加过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.如果你们有好的办法,请告知.
