Реализация стека <> в C #

Question

Недавно я реализовал рекурсивную реализацию поиска в каталоге, и я использую стек для отслеживания элементов пути.Когда я использовал string.Join (), чтобы соединить элементы пути, я обнаружил, что они поменялись местами.Когда я отладил метод, я заглянул в стек и обнаружил, что сами элементы были инвертированы во внутреннем массиве стека, т. Е. Самый последний элемент Push () был в начале внутреннего массива, а наименее последний - Push ()Элемент ed был в конце внутреннего массива.Это кажется отсталым и очень нелогичным.Может кто-нибудь сказать мне, почему Microsoft будет реализовывать стек таким образом?

Answer 1

Я думаю, вы ошибаетесь.

Это не значит, что Stack<T>.Push внутренне вставляет элемент в начало его внутреннего массива (это не так). Скорее, он перечисляет сверху вниз, так как это способ интуитивно перечислять через стек (представьте себе стопку блинов: вы начинаете сверху и идете вниз).

Если вы посмотрите на содержимое коллекции из отладчика Visual Studio, я думаю, что он отобразит их вам в порядке их перечисления, а не в порядке их внутреннего хранения *.

Взгляните на метод Stack<T>.Push в Reflector , и вы увидите, что код в основном соответствует ожидаемому:

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

Таким образом, стек внутренне добавляет новые элементы в конец своего внутреннего массива. Вы запутались в классе Stack<T>.Enumerator, а не в классе Stack<T>.

_{* Я не знаю, верно ли это вообще, но это верно для Stack<T>; см. превосходный ответ Ханса Пассанта о причине.}

Answer 2

Вы заставили меня пойти туда на некоторое время, и это действительно выглядит совершенно невероятно Однако происходит что-то еще. Класс Stack <> имеет визуализатор отладчика с именем System_StackDebugView <>. Это внутренний класс, вам нужно посмотреть в Reflector, чтобы увидеть его.

Этот визуализатор имеет свойство Items, это то, на что вы обращаете внимание при развертывании узла в отладчике. Это свойство Items использует Stack <>. ToArray (). Который выглядит так:

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;
}

Да, назад.

Answer 3

То, что вы описали , является правильной реализацией, поскольку стек является структурой LIFO (Last in First out).Представьте, что это стопка тарелок. Последний элемент, помещенный в стопку, является первым удаленным элементом.Вы сталкивались с другим стеком, который был бы FIFO?

FIFO был бы очередью.

Answer 4

Вот как реализованы методы push и pop в стеке.Обратите внимание, что он использует последний индекс в массиве, а не первый.Так что должна быть какая-то другая проблема, чтобы вернуть вас назад.

   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 5

Чтобы добавить к другим ответам, если в отладчике вы прокрутите вниз до элементов Stack <> и откроете массив Raw View-> Non-Public members -> _, вы сможете увидеть содержимое актуального внутренний массив, используемый для хранения элементов и проверки того, что они находятся в ожидаемом порядке.

Answer 6

Я не понимаю, что имеет значение, какой конец они считают вершиной стека, если теперь вы знаете, какой это конец. На самом деле имеет больше смысла в том, что когда вы помещаете что-то в стек, вы помещаете его сверху (начало) и перемещаете другие элементы вниз ...