Stack <> implementation in C#

Question

Gần đây tôi đã triển khai thực hiện tìm kiếm thư mục đệ quy và tôi đang sử dụng ngăn xếp để theo dõi các phần tử đường dẫn. Khi tôi sử dụng string.Join() để tham gia các phần tử đường dẫn, tôi thấy rằng chúng đã bị đảo ngược. Khi tôi sửa lỗi phương thức, tôi nhìn vào ngăn xếp và thấy rằng chính các phần tử đã được đảo ngược trong mảng nội bộ của Stack, tức là phần tử Push() gần đây nhất là ở đầu mảng bên trong, và gần đây nhất Push() phần tử ed nằm ở cuối mảng nội bộ. Điều này có vẻ ass-lạc hậu và rất phản trực quan. Ai đó có thể cho tôi biết lý do tại sao Microsoft sẽ thực hiện một ngăn xếp theo cách như vậy?

Answer 1

Tôi nghĩ bạn đã nhầm.

Nó không phải là Stack<T>.Push nội bộ chèn một mục ở đầu mảng nội bộ của nó (nó không). Thay vào đó, nó liệt kê từ trên xuống dưới, vì đây là cách thức mà người ta sẽ trực quan liệt kê thông qua một chồng (nghĩ về một chồng bánh kếp: bạn bắt đầu ở đầu và làm việc theo cách của bạn xuống).

Nếu bạn xem nội dung của bộ sưu tập từ bên trong trình gỡ rối của Visual Studio, tôi nghĩ nó sẽ hiển thị chúng theo thứ tự chúng được liệt kê - không phải thứ tự chúng được lưu trữ nội bộ *.

Hãy xem phương pháp Stack<T>.Push trong Reflector và bạn sẽ thấy rằng mã cơ bản là chính xác những gì bạn mong muốn:

// (code to check array size) 
this._array[this._size++] = item; 
// (code to update internal version number) 

Vì vậy, các ngăn xếp trong nội bộ cho biết thêm các yếu tố mới vào cuối nội bộ của mình mảng. Đó là lớp học Stack<T>.Enumerator khiến bạn bối rối, chứ không phải chính lớp học Stack<T>.

_{* Tôi không biết đây có phải là sự thật nói chung hay không, nhưng đó là sự thật cho Stack<T>; xem Hans Passant's excellent answer vì lý do tại sao.}

Answer 2

Những gì bạn mô tả là việc triển khai chính xác, vì ngăn xếp là cấu trúc LIFO (Last in First out). Hãy tưởng tượng nó giống như một chồng đĩa, nguyên tố gần đây nhất được đặt vào ngăn xếp là cái đầu tiên bị loại bỏ. Bạn đã chạy vào một chồng ở đâu đó là FIFO?

FIFO sẽ là Hàng đợi.

Answer 3

Tôi không thấy những gì quan trọng mà cuối cùng họ xem xét trên cùng của ngăn xếp, miễn là bạn bây giờ biết đó là kết thúc. Nó thực sự có ý nghĩa hơn rằng khi bạn 'đẩy' một cái gì đó vào ngăn xếp, bạn đang đẩy nó lên trên cùng (đầu) và di chuyển các mục khác xuống ...

Answer 4

Bạn đã cho tôi đến đó một chút, điều đó thực sự trông hoàn toàn bass-ackwards. Tuy nhiên có một cái gì đó khác đang xảy ra. Lớp Stack <> có trình hiển thị trình gỡ rối, có tên System_StackDebugView <>. Đây là một lớp học nội bộ, bạn phải nhìn với Reflector để xem nó.

Trình hiển thị trực quan đó có thuộc tính Mục, đó là những gì bạn xem khi mở rộng nút trong trình gỡ lỗi. Thuộc tính Mục đó sử dụng Stack <> .ToArray(). Hình như sau:

public T[] ToArray() 
{ 
    T[] localArray = new T[this._size]; 
    for (int i = 0; i < this._size; i++) 
    { 
     localArray[i] = this._array[(this._size - i) - 1]; 
    } 
    return localArray; 
} 

Yup, ngược.

Answer 5

Dưới đây là cách các phương pháp đẩy và bật của ngăn xếp được triển khai. Lưu ý rằng nó đang sử dụng chỉ mục cuối cùng trong mảng, chứ không phải là chỉ mục đầu tiên. Vì vậy, phải có một số vấn đề khác xảy ra để giúp bạn quay trở lại.

public virtual void Push(object obj) 
    { 
     if (this._size == this._array.Length) 
     { 
      object[] destinationArray = new object[2 * this._array.Length]; 
      Array.Copy(this._array, 0, destinationArray, 0, this._size); 
      this._array = destinationArray; 
     } 
     this._array[this._size++] = obj; 
     this._version++; 
    } 


public virtual object Pop() 
    { 
     if (this._size == 0) 
     { 
      throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack")); 
     } 
     this._version++; 
     object obj2 = this._array[--this._size]; 
     this._array[this._size] = null; 
     return obj2; 
    } 

Answer 6

Để thêm vào các câu trả lời khác, nếu trong debugger bạn cuộn xuống dưới cùng của ngăn xếp của bạn <> 's yếu tố và mở ra Raw View-> thành viên phi công -> _ mảng bạn sẽ nhìn thấy nội dung của mảng nội bộ thực tế được sử dụng để giữ các mục và xác minh rằng chúng nằm trong thứ tự mong muốn.