XIAOSUO 记录个人学习的足迹

一、采用数组保存数据

部分私有成员如下：

public class Stack<T> : IEnumerable<T>, System.Collections.ICollection {
	private T[] _array;    　　　　　　　　　　 //stack数据项保存的数组
	private int _size;     　　　　　　　　　　 //数据项的实际个数
	private int _version;   　　　　　　　　　　//数据项被修改过的次数,主要用户枚举过程中对于数据的修改
	private const int _defaultCapacity = 4;　 //初始stack大小 
	static T[] _emptyArray = new T[0];
	//................其他部分
｝

二、当数据空间不够时，扩大1倍空间

同List​类，带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费（可以使用TrimExcess来缩紧）。
三、数据Push/Pop的复杂度均为O(1)

//只有当数据项的个数小于数据实际长度的0.9倍时,系统才会收索数组
//在收索过程中会创建新的缓冲区数据,涉及到_size个数据项的复制,以及可能会引起cc启动的开销
public void TrimExcess() {
	int threshold = (int)(((double)_array.Length) * 0.9); 
	if( _size < threshold ) {
		T[] newarray = new T[_size]; 
		Array.Copy(_array, 0, newarray, 0, _size); 
		_array = newarray;
		_version++; 
	}
}

public T Peek() { 
	if (_size==0)
		ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); 
	return _array[_size-1];
}

public T Pop() { 
	if (_size == 0)
		ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); 
	_version++;
	T item = _array[--_size];
	_array[_size] = default(T);     //更快的释放内存
	return item; 
}

//在原有数据项不扩容的情况下,时间复杂度为O(1),否则会涉及到_size次数据复制
public void Push(T item) {
	if (_size == _array.Length) {
		T[] newArray = new T[(_array.Length == 0) ? _defaultCapacity : 2*_array.Length];
		Array.Copy(_array, 0, newArray, 0, _size); 
		_array = newArray;
	} 
	_array[_size++] = item; 
	_version++;
} 

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

//判断数据是否在栈中,复杂度O(n)
public bool Contains(T item) {
	int count = _size; 

	EqualityComparer<T> c = EqualityComparer<T>.Default; 
	while (count-- > 0) { 
		if (((Object) item) == null) {
			if (((Object) _array[count]) == null) 
				return true;
		}
		else if (_array[count] != null && c.Equals(_array[count], item) ) {
			return true; 
		}
	} 
	return false; 
}

栈在.NET Framework中实现比较简单，所以没有过多的文字描述，直接看源码应该都能看懂。