C#中Stack类的使用及一部分成员函数的源码分析
C#中Stack<T>类的使用及部分成员函数的源码分析
Stack<T>类 Stack<T> 作为数组来实现。 Stack<T> 的容量是 Stack<T> 可以包含的元素数。 当向 Stack<T> 中添加元素时，将通过重新分配内部数组来根据需要自动增大容量。 可通过调用 TrimExcess 来减少容量。 如果 Count 小于堆栈的容量，则 Push 的运算复杂度是 O(1)。 如果需要增加容量以容纳新元素，则 Push 的运算复杂度成为 O(n)，其中 n 为 Count。 Pop 的运算复杂度为 O(1)。 Stack<T> 接受 null 作为引用类型的有效值并且允许有重复的元素。 命名控件：System.Collections.Generic 程序集：System(在System.dll中) 语法：public class Stack<T>:IEnumerable<T>, ICollection, IEnumerable List<T>实现了IList<T>、 ICollection<T>、IEnumerable<T>、IList、ICollection、IEnumerable接口 因此可以看出与List1T>相比： Stack<T>没有继承ICollection<T>接口，因为这个接口定义的Add()和Remove()方法不能用于栈； Stack<T>没有继承IList<T>接口，所以不能使用索引器访问栈。 所以队列只允许在栈的顶部添加元素，删除元素。 常用的Stack<T>类的成员： Count : 返回栈中元素的个数。 Push(): 在栈顶添加一个元素。 Pop() : 从栈顶删除一个元素。如果栈是空，就会抛出异常InvalidOperationException异常。 Peek(): 返回栈顶的元素，但不删除它。 Contains(): 确定某个元素是否在栈中，如果是，返回true。 /******************************************************************************************************************************/ 常用Stack1T>类的成员函数的源码如下： public bool Contains(T item) { int index = this._size; EqualityComparer<T> comparer = EqualityComparer<T>.Default; while (index-- > 0) { if (item == null) { if (this._array[index] == null) { return true; } } else if ((this._array[index] != null) && comparer.Equals(this._array[index], item)) { return true; } } return false; } public T Peek() { if (this._size == 0) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); } return this._array[this._size - 1]; } public T Pop() { if (this._size == 0) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); } this._version++; T local = this._array[--this._size]; this._array[this._size] = default(T); return local; } public void Push(T item) { if (this._size == this._array.Length) { T[] destinationArray = new T[(this._array.Length == 0) ? 4 : (2 * this._array.Length)]; Array.Copy(this._array, 0, destinationArray, 0, this._size); this._array = destinationArray; } this._array[this._size++] = item; this._version++; } /*****************************************************************************************************************************************/ 下面的代码示例演示了 Stack 泛型类的几种方法。 此代码示例创建具有默认容量的字符串堆栈，并使用 Push 方法将五个字符串压入堆栈。 枚举堆栈的元素，这不会更改该堆栈的状态。 使用 Pop 方法将第一个字符串弹出堆栈。 使用 Peek 方法查看此堆栈中的下一个项，然后使用 Pop 方法将其弹出。 使用 ToArray 方法创建数组并将堆栈元素复制到其中，然后将数组传递给具有 IEnumerable 的 Stack 构造函数，以元素的反向顺序创建堆栈副本。 将显示副本的元素。 创建大小为堆栈大小两倍的数组，并使用 CopyTo 方法从数组的中间开始复制数组元素。 再次使用 Stack 构造函数以元素的反向顺序创建堆栈副本；这样，三个空元素就位于堆栈的底部。 使用 Contains 方法显示字符串“four”在第一个堆栈副本中，然后使用 Clear 方法清除该副本，并由 Count 属性显示此堆栈为空。 using System; using System.Collections.Generic; class Example { public static void Main() { Stack<string> numbers = new Stack<string>(); numbers.Push("one"); numbers.Push("two"); numbers.Push("three"); numbers.Push("four"); numbers.Push("five"); // A stack can be enumerated without disturbing its contents. foreach( string number in numbers ) { Console.WriteLine(number); } Console.WriteLine("\nPopping '{0}'", numbers.Pop()); Console.WriteLine("Peek at next item to destack: {0}", numbers.Peek()); Console.WriteLine("Popping '{0}'", numbers.Pop()); // Create a copy of the stack, using the ToArray method and the // constructor that accepts an IEnumerable. Stack stack2 = new Stack(numbers.ToArray()); Console.WriteLine("\nContents of the first copy:"); foreach( string number in stack2 ) { Console.WriteLine(number); } // Create an array twice the size of the stack and copy the // elements of the stack, starting at the middle of the // array. string[] array2 = new string[numbers.Count * 2]; numbers.CopyTo(array2, numbers.Count); // Create a second stack, using the constructor that accepts an // IEnumerable(Of T). Stack stack3 = new Stack(array2); Console.WriteLine("\nContents of the second copy, with duplicates and nulls:"); foreach( string number in stack3 ) { Console.WriteLine(number); } Console.WriteLine("\nstack2.Contains(\"four\") = {0}",stack2.Contains("four")); Console.WriteLine("\nstack2.Clear()"); stack2.Clear(); Console.WriteLine("\nstack2.Count = {0}", stack2.Count); } } /* This code example produces the following output: five four three two one Popping 'five' Peek at next item to destack: four Popping 'four' Contents of the first copy: one two three Contents of the second copy, with duplicates and nulls: one two three stack2.Contains("four") = False stack2.Clear() stack2.Count = 0 */
Stack<T>类 Stack<T> 作为数组来实现。 Stack<T> 的容量是 Stack<T> 可以包含的元素数。 当向 Stack<T> 中添加元素时，将通过重新分配内部数组来根据需要自动增大容量。 可通过调用 TrimExcess 来减少容量。 如果 Count 小于堆栈的容量，则 Push 的运算复杂度是 O(1)。 如果需要增加容量以容纳新元素，则 Push 的运算复杂度成为 O(n)，其中 n 为 Count。 Pop 的运算复杂度为 O(1)。 Stack<T> 接受 null 作为引用类型的有效值并且允许有重复的元素。 命名控件：System.Collections.Generic 程序集：System(在System.dll中) 语法：public class Stack<T>:IEnumerable<T>, ICollection, IEnumerable List<T>实现了IList<T>、 ICollection<T>、IEnumerable<T>、IList、ICollection、IEnumerable接口 因此可以看出与List1T>相比： Stack<T>没有继承ICollection<T>接口，因为这个接口定义的Add()和Remove()方法不能用于栈； Stack<T>没有继承IList<T>接口，所以不能使用索引器访问栈。 所以队列只允许在栈的顶部添加元素，删除元素。 常用的Stack<T>类的成员： Count : 返回栈中元素的个数。 Push(): 在栈顶添加一个元素。 Pop() : 从栈顶删除一个元素。如果栈是空，就会抛出异常InvalidOperationException异常。 Peek(): 返回栈顶的元素，但不删除它。 Contains(): 确定某个元素是否在栈中，如果是，返回true。 /******************************************************************************************************************************/ 常用Stack1T>类的成员函数的源码如下： public bool Contains(T item) { int index = this._size; EqualityComparer<T> comparer = EqualityComparer<T>.Default; while (index-- > 0) { if (item == null) { if (this._array[index] == null) { return true; } } else if ((this._array[index] != null) && comparer.Equals(this._array[index], item)) { return true; } } return false; } public T Peek() { if (this._size == 0) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); } return this._array[this._size - 1]; } public T Pop() { if (this._size == 0) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); } this._version++; T local = this._array[--this._size]; this._array[this._size] = default(T); return local; } public void Push(T item) { if (this._size == this._array.Length) { T[] destinationArray = new T[(this._array.Length == 0) ? 4 : (2 * this._array.Length)]; Array.Copy(this._array, 0, destinationArray, 0, this._size); this._array = destinationArray; } this._array[this._size++] = item; this._version++; } /*****************************************************************************************************************************************/ 下面的代码示例演示了 Stack 泛型类的几种方法。 此代码示例创建具有默认容量的字符串堆栈，并使用 Push 方法将五个字符串压入堆栈。 枚举堆栈的元素，这不会更改该堆栈的状态。 使用 Pop 方法将第一个字符串弹出堆栈。 使用 Peek 方法查看此堆栈中的下一个项，然后使用 Pop 方法将其弹出。 使用 ToArray 方法创建数组并将堆栈元素复制到其中，然后将数组传递给具有 IEnumerable 的 Stack 构造函数，以元素的反向顺序创建堆栈副本。 将显示副本的元素。 创建大小为堆栈大小两倍的数组，并使用 CopyTo 方法从数组的中间开始复制数组元素。 再次使用 Stack 构造函数以元素的反向顺序创建堆栈副本；这样，三个空元素就位于堆栈的底部。 使用 Contains 方法显示字符串“four”在第一个堆栈副本中，然后使用 Clear 方法清除该副本，并由 Count 属性显示此堆栈为空。 using System; using System.Collections.Generic; class Example { public static void Main() { Stack<string> numbers = new Stack<string>(); numbers.Push("one"); numbers.Push("two"); numbers.Push("three"); numbers.Push("four"); numbers.Push("five"); // A stack can be enumerated without disturbing its contents. foreach( string number in numbers ) { Console.WriteLine(number); } Console.WriteLine("\nPopping '{0}'", numbers.Pop()); Console.WriteLine("Peek at next item to destack: {0}", numbers.Peek()); Console.WriteLine("Popping '{0}'", numbers.Pop()); // Create a copy of the stack, using the ToArray method and the // constructor that accepts an IEnumerable. Stack stack2 = new Stack(numbers.ToArray()); Console.WriteLine("\nContents of the first copy:"); foreach( string number in stack2 ) { Console.WriteLine(number); } // Create an array twice the size of the stack and copy the // elements of the stack, starting at the middle of the // array. string[] array2 = new string[numbers.Count * 2]; numbers.CopyTo(array2, numbers.Count); // Create a second stack, using the constructor that accepts an // IEnumerable(Of T). Stack stack3 = new Stack(array2); Console.WriteLine("\nContents of the second copy, with duplicates and nulls:"); foreach( string number in stack3 ) { Console.WriteLine(number); } Console.WriteLine("\nstack2.Contains(\"four\") = {0}",stack2.Contains("four")); Console.WriteLine("\nstack2.Clear()"); stack2.Clear(); Console.WriteLine("\nstack2.Count = {0}", stack2.Count); } } /* This code example produces the following output: five four three two one Popping 'five' Peek at next item to destack: four Popping 'four' Contents of the first copy: one two three Contents of the second copy, with duplicates and nulls: one two three stack2.Contains("four") = False stack2.Clear() stack2.Count = 0 */
版权声明：本文为博主原创文章，未经博主允许不得转载。