Почему класс Stack <T>в C # допускает ElementAt (index), пока он ADT?

Question

Стек - это абстрактный тип данных (ADT), и он должен иметь запечатанный список операций, таких как Push (), Pop (), Peek (), ... для принудительного «последним-первым-на-выходе» (LIFO).) Принцип.

Но у него есть ElementAt (индекс), который позволяет мне получить доступ к любому элементу в стеке.Насколько я понимаю, стек должен иметь меньшую видимость элементов, которых нет на поверхности.Не так ли?

Answer 1

Стек - это абстрактный тип данных (ADT)

Это верно для общей концепции стека, но System.Collections.Generic.Stack<T> никогда не обещает быть (просто) ADT.

Он должен обеспечивать как минимум функциональность ADT (чтобы соответствовать названию), но может предложить больше.

Так что он не пытается скрыть Contains (), Count, TryPeek () и т. Д.

Answer 2

В псевдокоде вот ElementAt, который является внешним по отношению к Stack и использует только операции ADT:

T ElementAt<T>(Stack<T> items, int index)
{
    var tmp = new Stack<T>();
    while(!items.Empty && index > 0)
    {
       tmp.Push(items.Peek());
       items.Pop();
       index --
    }
    try {
        return items.Peek(); //Presumed to throw an appropriate exception if empty
    }
    finally {
       while(!tmp.Empty)
       {
          items.Push(tmp.Peek());
          tmp.Pop();
       }
    }
}

(Выше предполагается, что мутирование Stack s - немного другая реализациябудет работать для неизменных стеков и не потребует неуклюжих действий отмены)

Конечно, дело в том, что тип Stack в .NET предназначен для практического решения проблем не для какой-то абстрактной чистоты, и (благодаря предложению Stack разрешить перечисление) здесь действительно доступна более эффективная реализация .И мы не заставляем людей копировать такие методы в библиотеку «utils».

Answer 3

ElementAt() предоставляется через Enumerable.ElementAt() от Linq, а не через интерфейс Stack<T>.

Это работает, потому что Stack<T> реализует IEnumerable<T>, что все, что нужнореализовать ElementAt(), поскольку все, что он делает, - это перебирает все элементы, предоставленные с помощью IEnumerable<T>, до тех пор, пока к ним не будет получен доступ к N.

Для Stack<T> это операция O (N).Если вы используете ElementAt(), скажем, с List<T>, тогда внутренняя оптимизация превращает ее в операцию O (1).

Почему Stack<T> реализует IEnumerable<T> - только один из разработчиковдействительно могу ответить на этот вопрос.Так как это не мутирующая операция, то она не нарушает ничего фундаментального в стеке.Я бы предположил , что это было предоставлено для удобства.

Как указывает / u / Damien_The_Unbeliever в своем ответе, код может определить N-й элемент без интерфейса IEnumerable путем привязки N элементов к другому.укладывают, а затем толкают их все в обратном порядке, чтобы исходный стек не изменился.

Муха в этой мази заключается в том, что Microsoft не документирует порядок, в котором стек IEnumerableвозвращает его элементы.Вы можете проверить исходный код, чтобы убедиться, что он действительно возвращает элементы в порядке LIFO - но это просто не задокументировано.

Это обсуждается в ответах на этот вопрос .

В любом случае, где интерфейс ADT определен для абстрактного стека, о котором вы говорите?Я не думаю, что есть определенный ответ для этого.Строго говоря, можно сказать, что в стеке есть только Push() и Pop().И все же большинство реализаций также предоставляют Count.

Как и в , статья о стеке в Википедии гласит: :

Во многих реализациях стек имеет больше операций, чем"толчок" и "поп".В качестве примера можно привести «top of stack» или «peek», который наблюдает за самым верхним элементом, не удаляя его из стека.

, поскольку это можно сделать с помощью «pop» и «push» содни и те же данные, это не существенно.В операции «вершина стека» может возникнуть условие недостаточного заполнения, если стек пуст, так же, как и «pop».Кроме того, реализации часто имеют функцию, которая просто возвращает, является ли стек пустым.

Поэтому принципиально ответ на ваш вопрос:

Разработчики библиотеки решили добавить несколькоудобные методы без мутаций в дополнение к просто методам мутации Push() и Pop().