Стек <> реализация в C#
Я недавно реализовывал рекурсивную реализацию поиска каталога, и я использую Стек для отслеживания элементов пути. Когда я использовал строку. Соединение () для присоединения к элементам пути я нашел, что они были инвертированы. Когда я отладил метод, я изучил стек и нашел, что сами элементы были инвертированы во внутреннем массиве Стека, т.е. последний раз Нажатие (), элемент редактора был в начале внутреннего массива, и наименьшее количество недавно Нажатие (), элемент редактора был в конце внутреннего массива. Это кажется обратным задницей и очень парадоксальным. Кто-то может сказать мне, почему Microsoft реализовала бы стек таким способом?
6 ответов
Я думаю, вы ошибаетесь.
Дело не в том, что Stack внутренне вставляет элемент в начало своего внутреннего массива (это не так). Скорее, он перечисляет сверху вниз, поскольку именно таким образом интуитивно можно перечислить все элементы в стопке (вспомните стопку блинов: вы начинаете с самого верха и идете вниз).
Если вы посмотрите на содержимое коллекции из отладчика Visual Studio, я думаю, что он покажет вам его в порядке перечисления, а не в порядке внутреннего хранения*.
Посмотрите на метод Stack в Reflector и вы увидите, что код в основном именно такой, как вы ожидали:
// (code to check array size)
this._array[this._size++] = item;
// (code to update internal version number)
Итак, стек внутренне добавляет новые элементы в конец своего внутреннего массива. Это класс Stack, который вас запутал, а не сам класс Stack.
* Я не знаю, верно ли это в общем случае, но это верно для Stack; причину этого см. в отличном ответе Ганса Пассана.
То, что вы описали , является правильной реализацией, поскольку стек представляет собой структуру LIFO (последний пришел, первым ушел). Представьте себе стопку тарелок, элемент, помещенный в стопку последним, удаляется первым. Вы сталкивались со стеком в другом месте, который является FIFO?
FIFO будет очередью.
Я не понимаю, какое значение имеет, какой конец они считают вершиной стека, если вы теперь знаете, какой это конец. На самом деле имеет больше смысла, когда вы «помещаете» что-то в стек, вы помещаете его наверх (начало) и перемещаете другие элементы вниз ...
Вы заставили меня немного повозиться, это действительно выглядит совершенно нелогично. Однако здесь есть кое-что еще. Класс 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;
}
Ага, в обратную сторону.
Чтобы добавить к другим ответам, если в отладчике прокрутить вниз до нижней части элементов Stack<> и открыть Raw View->Непубличные члены->_array вы можете увидеть содержимое фактического внутреннего массива, используемого для хранения элементов, и убедиться, что они находятся в ожидаемом порядке.
Вот как реализованы методы push и pops стека. Обратите внимание, что используется последний индекс в массиве, а не первый. Так что должна быть какая-то другая проблема, чтобы получить ваш вариант в обратном порядке.
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;
}