XIAOSUO 记录个人学习的足迹

一、通过数组和首尾下标指针组成环形队列

　　私有部分成员如下：

public class Queue<T> : IEnumerable<T>, System.Collections.ICollection {
	private T[] _array; 
	private int _head;       //头引用
	private int _tail;       //尾引用
	private int _size;       //元素个数
	private int _version; 
	private const int _MinimumGrow = 4;       //队列能容纳元素的最低下限
	private const int _GrowFactor = 200;      //扩展因子，_GrowFactor/100的结果为扩展的倍数
	private const int _DefaultCapacity = 4;   //默认数据项容量
	static T[]  _emptyArray = new T[0];
	//................其他部分
｝

二、当空间不够时，根据扩张因子决定新缓冲区大小

当数据复制到新缓冲区，带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费。

//会涉及到数据项到新缓冲区的复杂开销
//在数据写入到新缓冲区后队列会被设置成0
//原有缓冲区会被丢失
private void SetCapacity(int capacity) {
	Object[] newarray = new Object[capacity];
	if (_size > 0) {
		if (_head < _tail) {
			Array.Copy(_array, _head, newarray, 0, _size);
		} else {
			Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
			Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
		}
	}

	_array = newarray;
	_head = 0;
	_tail = (_size == capacity) ? 0 : _size;        
	_version++;
}

注意：Array.Copy方法的调用过程。

三、入队和出队复杂度为O(1)

但是如果原空间不足时，会使用O(n)的开销来进行缓冲区之间的复制

//在对象不扩容的情况下,复杂度为O(n)
public virtual void Enqueue(Object obj) {
	if (_size == _array.Length) {
		int newcapacity = (int)((long)_array.Length * (long)_growFactor / 100);
		if (newcapacity < _array.Length + _MinimumGrow) {
			newcapacity = _array.Length + _MinimumGrow;
		}
		SetCapacity(newcapacity);
	}
	_array[_tail] = obj;
	_tail = (_tail + 1) % _array.Length;
	_size++;
	_version++;
}

public virtual Object Dequeue() {
	if (_size == 0)
		throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue"));
	Object removed = _array[_head];
	_array[_head] = null;
	_head = (_head + 1) % _array.Length;
	_size--;
	_version++;
	return removed;
}

public virtual Object Peek() {
	if (_size == 0)
		throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue"));
	return _array[_head];
}

四、数据查找开销为O(n)

public virtual bool Contains(Object obj) {
	int index = _head;
	int count = _size;

	while (count-- > 0) {
		if (obj == null) {
			if (_array[index] == null)
				return true;
		} else if (_array[index] != null && _array[index].Equals(obj)) {
			return true;
		}
		index = (index + 1) % _array.Length;
	}

	return false;
}