最近在学习算法基础，本篇文章作为一个记录，也算是一次实践和总结。（顺便也深入C#运行时学习一下）
目录
1. 栈是什么
栈是一种特殊的线性表（数据逻辑结构中的一种，定义是其组成元素之间具有线性关系的一种线性结构），其插入和删除操作只能在一端进行。
1 个人理解： 2 是一种最基本的数据结构，数据结构方面必须夯实的基础知识
特征（也可以说是应用场景）：
后进先出（队列则为先进先出）
2. Stack 自定义实现
Github： https://github.com/HadesKing/DataStructureAndAlgorithms
代码路径：BasicDataStructure\src\LD.BasicDataStructures\Stacks
Stack实现方式有两种：顺序存储和链式存储（顺序栈和链式栈）
为了便于使用，我对栈进行了抽象，形成了一个接口IStack
1 // Copyright (c) 刘迪. All rights reserved. 2 // 3 // Author: 刘迪 4 // Create Time: 2021-04-30 5 // 6 // Modifier: xxx 7 // Modifier time: xxx 8 // Description: xxx 9 // 10 // Modifier: xxx 11 // Modifier time: xxx 12 // Description: xxx 13 // 14 // 15 // 16 17 using System; 18 19 namespace LD.BasicDataStructures.Stacks 20 { 21 /// <summary> 22 /// 栈的接口 23 /// </summary> 24 /// <typeparam name="T">type of data element</typeparam> 25 /// <remarks> 26 /// 主要用于定义栈的公共操作 27 /// </remarks> 28 public interface IStack<T> 29 { 30 /// <summary> 31 /// Gets the number of elements contained in the Stack. 32 /// </summary> 33 Int32 Count { get; } 34 35 /// <summary> 36 /// Verify that it is empty. 37 /// </summary> 38 /// <returns> 39 /// <c>true</c> Is empty. 40 /// <c>false</c> Not is empty. 41 /// </returns> 42 bool IsEmpty(); 43 44 /// <summary> 45 /// Add a data element to the stack. 46 /// </summary> 47 /// <param name="element">value of data element</param> 48 /// <returns> 49 /// <c>true</c> The operation was successful. 50 /// <c>false</c> The operation failed. 51 /// </returns> 52 bool Push(T element); 53 54 /// <summary> 55 /// Pop up a data element from the stack.If there is no data element in the stack, it returns null. 56 /// </summary> 57 /// <returns> 58 /// Data element being popped.If there is no data element in the stack, it returns null. 59 /// </returns> 60 T Pop(); 61 62 /// <summary> 63 /// Get a data element from the stack.If the stack is empty, return null. 64 /// </summary> 65 /// <returns> 66 /// Data element.If the stack is empty, return null 67 /// </returns> 68 T Get(); 69 70 } 71 }
顺序栈的实现
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 // Copyright (c) 刘迪. All rights reserved. 8 // 9 // Author: 刘迪 10 // Create Time: 2021-05-01 11 // 12 // Modifier: xxx 13 // Modifier time: xxx 14 // Description: xxx 15 // 16 // Modifier: xxx 17 // Modifier time: xxx 18 // Description: xxx 19 // 20 // 21 // 22 23 namespace LD.BasicDataStructures.Stacks 24 { 25 /// <summary> 26 /// Implementation of sequential stack 27 /// </summary> 28 /// <typeparam name="T">Type of data</typeparam> 29 public sealed class SequentialStack<T> : IStack<SequentialNode<T>> 30 { 31 private SequentialNode<T>[] m_sequentialNodes = null; 32 private Int32 m_dataElementNumber = 0; 33 34 /// <summary> 35 /// 构造函数 36 /// </summary> 37 public SequentialStack() : this(10) 38 { 39 } 40 41 /// <summary> 42 /// 构造函数 43 /// </summary> 44 /// <param name="capacity">Stack capacity</param> 45 public SequentialStack(UInt32 capacity) 46 { 47 m_sequentialNodes = new SequentialNode<T>[capacity]; 48 } 49 50 /// <summary> 51 /// Gets the number of elements contained in the Stack. 52 /// </summary> 53 public Int32 Count => m_dataElementNumber; 54 55 /// <summary> 56 /// Verify that it is empty. 57 /// </summary> 58 /// <returns> 59 /// <c>true</c> Is empty. 60 /// <c>false</c> Not is empty. 61 /// </returns> 62 public bool IsEmpty() 63 { 64 return m_dataElementNumber == 0; 65 } 66 67 /// <summary> 68 /// Add a data element to the stack. 69 /// </summary> 70 /// <param name="element">value of data element</param> 71 /// <returns> 72 /// <c>true</c> The operation was successful. 73 /// <c>false</c> The operation failed. 74 /// </returns> 75 public bool Push(SequentialNode<T> element) 76 { 77 bool result = false; 78 if (null != element) 79 { 80 if (m_dataElementNumber != m_sequentialNodes.Length) 81 { 82 m_sequentialNodes[m_dataElementNumber] = element; 83 m_dataElementNumber++; 84 result = true; 85 } 86 else 87 { 88 //扩容 89 var tmp = m_sequentialNodes; 90 m_sequentialNodes = new SequentialNode<T>[2 * m_dataElementNumber]; 91 tmp.CopyTo(m_sequentialNodes, 0); 92 result = Push(element); 93 } 94 } 95 96 return result; 97 } 98 99 /// <summary> 100 /// Pop up a data element from the stack. 101 /// If there is no data element in the stack, it returns null. 102 /// </summary> 103 /// <returns> 104 /// Data element being popped.If there is no data element in the stack, it returns null. 105 /// </returns> 106 public SequentialNode<T> Pop() 107 { 108 if (0 != m_dataElementNumber) 109 { 110 m_dataElementNumber--; 111 return m_sequentialNodes[m_dataElementNumber]; 112 } 113 114 return null; 115 } 116 117 /// <summary> 118 /// Get a data element from the stack.If the stack is empty, return null. 119 /// </summary> 120 /// <returns> 121 /// Data element.If the stack is empty, return null 122 /// </returns> 123 public SequentialNode<T> Get() 124 { 125 if (0 != m_dataElementNumber) 126 { 127 return m_sequentialNodes[m_dataElementNumber - 1]; 128 } 129 130 return null; 131 } 132 133 } 134 }
链式栈的实现
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 // Copyright (c) 刘迪. All rights reserved. 8 // 9 // Author: 刘迪 10 // Create Time: 2021-05-01 11 // 12 // Modifier: xxx 13 // Modifier time: xxx 14 // Description: xxx 15 // 16 // Modifier: xxx 17 // Modifier time: xxx 18 // Description: xxx 19 // 20 // 21 // 22 23 namespace LD.BasicDataStructures.Stacks 24 { 25 /// <summary> 26 /// Implementation of chain storage stack 27 /// </summary> 28 /// <typeparam name="T">Type of data</typeparam> 29 public sealed class LinkedStack<T> : IStack<SinglyLinkedNode<T>> 30 { 31 32 private SinglyLinkedNode<T> m_topNode = null; 33 private Int32 m_count = 0; 34 35 /// <summary> 36 /// Gets the number of elements contained in the Stack. 37 /// </summary> 38 public Int32 Count => m_count; 39 40 public LinkedStack() 41 { 42 43 } 44 45 /// <summary> 46 /// Verify that it is empty. 47 /// </summary> 48 /// <returns> 49 /// <c>true</c> Is empty. 50 /// <c>false</c> Not is empty. 51 /// </returns> 52 public bool IsEmpty() 53 { 54 return null == m_topNode; 55 } 56 57 /// <summary> 58 /// Add a data element to the stack. 59 /// </summary> 60 /// <param name="element">value of data element</param> 61 /// <returns> 62 /// <c>true</c> The operation was successful. 63 /// <c>false</c> The operation failed. 64 /// </returns> 65 public bool Push(SinglyLinkedNode<T> element) 66 { 67 bool result = false; 68 if (null != element) 69 { 70 if (null == m_topNode) 71 { 72 m_topNode = element; 73 } 74 else 75 { 76 var tmpNode = m_topNode; 77 element.Next = tmpNode; 78 m_topNode = element; 79 } 80 81 m_count++; 82 result = true; 83 } 84 85 return result; 86 } 87 88 /// <summary> 89 /// Pop up a data element from the stack.If there is no data element in the stack, it returns null. 90 /// </summary> 91 /// <returns> 92 /// Data element being popped.If there is no data element in the stack, it returns null. 93 /// </returns> 94 public SinglyLinkedNode<T> Pop() 95 { 96 SinglyLinkedNode<T> returnNode = null; 97 if (null != m_topNode) 98 { 99 returnNode = m_topNode; 100 m_topNode = returnNode.Next; 101 m_count--; 102 } 103 104 return returnNode; 105 } 106 107 /// <summary> 108 /// Get a data element from the stack.If the stack is empty, return null. 109 /// </summary> 110 /// <returns> 111 /// Data element.If the stack is empty, return null 112 /// </returns> 113 public SinglyLinkedNode<T> Get() 114 { 115 return m_topNode; 116 } 117 118 } 119 }
3. Stack C# 官方实现
Github： https://github.com/dotnet/runtime
Stack 文件路径：src\libraries\System.Collections\src\System\Collections\Generic\Stack.cs
1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 4 /*============================================================================= 5 ** 6 ** 7 ** Purpose: An array implementation of a generic stack. 8 ** 9 ** 10 =============================================================================*/ 11 12 using System.Diagnostics; 13 using System.Diagnostics.CodeAnalysis; 14 using System.Runtime.CompilerServices; 15 16 namespace System.Collections.Generic 17 { 18 // A simple stack of objects. Internally it is implemented as an array, 19 // so Push can be O(n). Pop is O(1). 20 21 [DebuggerTypeProxy(typeof(StackDebugView<>))] 22 [DebuggerDisplay("Count = {Count}")] 23 [Serializable] 24 [System.Runtime.CompilerServices.TypeForwardedFrom("System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")] 25 public class Stack<T> : IEnumerable<T>, 26 System.Collections.ICollection, 27 IReadOnlyCollection<T> 28 { 29 private T[] _array; // Storage for stack elements. Do not rename (binary serialization) 30 private int _size; // Number of items in the stack. Do not rename (binary serialization) 31 private int _version; // Used to keep enumerator in sync w/ collection. Do not rename (binary serialization) 32 33 private const int DefaultCapacity = 4; 34 35 public Stack() 36 { 37 _array = Array.Empty<T>(); 38 } 39 40 // Create a stack with a specific initial capacity. The initial capacity 41 // must be a non-negative number. 42 public Stack(int capacity) 43 { 44 if (capacity < 0) 45 throw new ArgumentOutOfRangeException(nameof(capacity), capacity, SR.ArgumentOutOfRange_NeedNonNegNum); 46 _array = new T[capacity]; 47 } 48 49 // Fills a Stack with the contents of a particular collection. The items are 50 // pushed onto the stack in the same order they are read by the enumerator. 51 public Stack(IEnumerable<T> collection) 52 { 53 if (collection == null) 54 throw new ArgumentNullException(nameof(collection)); 55 _array = EnumerableHelpers.ToArray(collection, out _size); 56 } 57 58 public int Count 59 { 60 get { return _size; } 61 } 62 63 bool ICollection.IsSynchronized 64 { 65 get { return false; } 66 } 67 68 object ICollection.SyncRoot => this; 69 70 // Removes all Objects from the Stack. 71 public void Clear() 72 { 73 if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) 74 { 75 Array.Clear(_array, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references. 76 } 77 _size = 0; 78 _version++; 79 } 80 81 public bool Contains(T item) 82 { 83 // Compare items using the default equality comparer 84 85 // PERF: Internally Array.LastIndexOf calls 86 // EqualityComparer<T>.Default.LastIndexOf, which 87 // is specialized for different types. This 88 // boosts performance since instead of making a 89 // virtual method call each iteration of the loop, 90 // via EqualityComparer<T>.Default.Equals, we 91 // only make one virtual call to EqualityComparer.LastIndexOf. 92 93 return _size != 0 && Array.LastIndexOf(_array, item, _size - 1) != -1; 94 } 95 96 // Copies the stack into an array. 97 public void CopyTo(T[] array, int arrayIndex) 98 { 99 if (array == null) 100 { 101 throw new ArgumentNullException(nameof(array)); 102 } 103 104 if (arrayIndex < 0 || arrayIndex > array.Length) 105 { 106 throw new ArgumentOutOfRangeException(nameof(arrayIndex), arrayIndex, SR.ArgumentOutOfRange_Index); 107 } 108 109 if (array.Length - arrayIndex < _size) 110 { 111 throw new ArgumentException(SR.Argument_InvalidOffLen); 112 } 113 114 Debug.Assert(array != _array); 115 int srcIndex = 0; 116 int dstIndex = arrayIndex + _size; 117 while (srcIndex < _size) 118 { 119 array[--dstIndex] = _array[srcIndex++]; 120 } 121 } 122 123 void ICollection.CopyTo(Array array, int arrayIndex) 124 { 125 if (array == null) 126 { 127 throw new ArgumentNullException(nameof(array)); 128 } 129 130 if (array.Rank != 1) 131 { 132 throw new ArgumentException(SR.Arg_RankMultiDimNotSupported, nameof(array)); 133 } 134 135 if (array.GetLowerBound(0) != 0) 136 { 137 throw new ArgumentException(SR.Arg_NonZeroLowerBound, nameof(array)); 138 } 139 140 if (arrayIndex < 0 || arrayIndex > array.Length) 141 { 142 throw new ArgumentOutOfRangeException(nameof(arrayIndex), arrayIndex, SR.ArgumentOutOfRange_Index); 143 } 144 145 if (array.Length - arrayIndex < _size) 146 { 147 throw new ArgumentException(SR.Argument_InvalidOffLen); 148 } 149 150 try 151 { 152 Array.Copy(_array, 0, array, arrayIndex, _size); 153 Array.Reverse(array, arrayIndex, _size); 154 } 155 catch (ArrayTypeMismatchException) 156 { 157 throw new ArgumentException(SR.Argument_InvalidArrayType, nameof(array)); 158 } 159 } 160 161 // Returns an IEnumerator for this Stack. 162 public Enumerator GetEnumerator() 163 { 164 return new Enumerator(this); 165 } 166 167 /// <internalonly/> 168 IEnumerator<T> IEnumerable<T>.GetEnumerator() 169 { 170 return new Enumerator(this); 171 } 172 173 IEnumerator IEnumerable.GetEnumerator() 174 { 175 return new Enumerator(this); 176 } 177 178 public void TrimExcess() 179 { 180 int threshold = (int)(_array.Length * 0.9); 181 if (_size < threshold) 182 { 183 Array.Resize(ref _array, _size); 184 _version++; 185 } 186 } 187 188 // Returns the top object on the stack without removing it. If the stack 189 // is empty, Peek throws an InvalidOperationException. 190 public T Peek() 191 { 192 int size = _size - 1; 193 T[] array = _array; 194 195 if ((uint)size >= (uint)array.Length) 196 { 197 ThrowForEmptyStack(); 198 } 199 200 return array[size]; 201 } 202 203 public bool TryPeek([MaybeNullWhen(false)] out T result) 204 { 205 int size = _size - 1; 206 T[] array = _array; 207 208 if ((uint)size >= (uint)array.Length) 209 { 210 result = default!; 211 return false; 212 } 213 result = array[size]; 214 return true; 215 } 216 217 // Pops an item from the top of the stack. If the stack is empty, Pop 218 // throws an InvalidOperationException. 219 public T Pop() 220 { 221 int size = _size - 1; 222 T[] array = _array; 223 224 // if (_size == 0) is equivalent to if (size == -1), and this case 225 // is covered with (uint)size, thus allowing bounds check elimination 226 // https://github.com/dotnet/coreclr/pull/9773 227 if ((uint)size >= (uint)array.Length) 228 { 229 ThrowForEmptyStack(); 230 } 231 232 _version++; 233 _size = size; 234 T item = array[size]; 235 if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) 236 { 237 array[size] = default!; // Free memory quicker. 238 } 239 return item; 240 } 241 242 public bool TryPop([MaybeNullWhen(false)] out T result) 243 { 244 int size = _size - 1; 245 T[] array = _array; 246 247 if ((uint)size >= (uint)array.Length) 248 { 249 result = default!; 250 return false; 251 } 252 253 _version++; 254 _size = size; 255 result = array[size]; 256 if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) 257 { 258 array[size] = default!; 259 } 260 return true; 261 } 262 263 // Pushes an item to the top of the stack. 264 public void Push(T item) 265 { 266 int size = _size; 267 T[] array = _array; 268 269 if ((uint)size < (uint)array.Length) 270 { 271 array[size] = item; 272 _version++; 273 _size = size + 1; 274 } 275 else 276 { 277 PushWithResize(item); 278 } 279 } 280 281 // Non-inline from Stack.Push to improve its code quality as uncommon path 282 [MethodImpl(MethodImplOptions.NoInlining)] 283 private void PushWithResize(T item) 284 { 285 Debug.Assert(_size == _array.Length); 286 Grow(_size + 1); 287 _array[_size] = item; 288 _version++; 289 _size++; 290 } 291 292 /// <summary> 293 /// Ensures that the capacity of this Stack is at least the specified <paramref name="capacity"/>. 294 /// If the current capacity of the Stack is less than specified <paramref name="capacity"/>, 295 /// the capacity is increased by continuously twice current capacity until it is at least the specified <paramref name="capacity"/>. 296 /// </summary> 297 /// <param name="capacity">The minimum capacity to ensure.</param> 298 public int EnsureCapacity(int capacity) 299 { 300 if (capacity < 0) 301 { 302 throw new ArgumentOutOfRangeException(nameof(capacity), capacity, SR.ArgumentOutOfRange_NeedNonNegNum); 303 } 304 305 if (_array.Length < capacity) 306 { 307 Grow(capacity); 308 _version++; 309 } 310 311 return _array.Length; 312 } 313 314 private void Grow(int capacity) 315 { 316 Debug.Assert(_array.Length < capacity); 317 318 int newcapacity = _array.Length == 0 ? DefaultCapacity : 2 * _array.Length; 319 320 // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. 321 // Note that this check works even when _items.Length overflowed thanks to the (uint) cast. 322 if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength; 323 324 // If computed capacity is still less than specified, set to the original argument. 325 // Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize. 326 if (newcapacity < capacity) newcapacity = capacity; 327 328 Array.Resize(ref _array, newcapacity); 329 } 330 331 // Copies the Stack to an array, in the same order Pop would return the items. 332 public T[] ToArray() 333 { 334 if (_size == 0) 335 return Array.Empty<T>(); 336 337 T[] objArray = new T[_size]; 338 int i = 0; 339 while (i < _size) 340 { 341 objArray[i] = _array[_size - i - 1]; 342 i++; 343 } 344 return objArray; 345 } 346 347 private void ThrowForEmptyStack() 348 { 349 Debug.Assert(_size == 0); 350 throw new InvalidOperationException(SR.InvalidOperation_EmptyStack); 351 } 352 353 public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator 354 { 355 private readonly Stack<T> _stack; 356 private readonly int _version; 357 private int _index; 358 private T? _currentElement; 359 360 internal Enumerator(Stack<T> stack) 361 { 362 _stack = stack; 363 _version = stack._version; 364 _index = -2; 365 _currentElement = default; 366 } 367 368 public void Dispose() 369 { 370 _index = -1; 371 } 372 373 public bool MoveNext() 374 { 375 bool retval; 376 if (_version != _stack._version) throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion); 377 if (_index == -2) 378 { // First call to enumerator. 379 _index = _stack._size - 1; 380 retval = (_index >= 0); 381 if (retval) 382 _currentElement = _stack._array[_index]; 383 return retval; 384 } 385 if (_index == -1) 386 { // End of enumeration. 387 return false; 388 } 389 390 retval = (--_index >= 0); 391 if (retval) 392 _currentElement = _stack._array[_index]; 393 else 394 _currentElement = default; 395 return retval; 396 } 397 398 public T Current 399 { 400 get 401 { 402 if (_index < 0) 403 ThrowEnumerationNotStartedOrEnded(); 404 return _currentElement!; 405 } 406 } 407 408 private void ThrowEnumerationNotStartedOrEnded() 409 { 410 Debug.Assert(_index == -1 || _index == -2); 411 throw new InvalidOperationException(_index == -2 ? SR.InvalidOperation_EnumNotStarted : SR.InvalidOperation_EnumEnded); 412 } 413 414 object? System.Collections.IEnumerator.Current 415 { 416 get { return Current; } 417 } 418 419 void IEnumerator.Reset() 420 { 421 if (_version != _stack._version) throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion); 422 _index = -2; 423 _currentElement = default; 424 } 425 } 426 } 427 }
PS：
深入了解了一下，CopyTo和Resize都会调用Buffer.Memmove方法
4. 区别
PS：
自定义的实现本质是一个实验性项目，这里做对比，主要目的是感受和官方实现之间的差距（为了学习）
5. 总结
- 实现：场景考虑不够全面（对于数据的理解和校验明显不足）
- 技术：对于C#理解不够深入（runtime源码需要进一步深入学习和查看）
---------------------------------- 人生格言 ---------------------------------------------------------------
输入决定输出，没有输入就没有输出。