Как узнать, когда использовать Stack вместо других коллекций?

Question

Вот небольшая прелюдия к более общему вопросу, о котором мне интересно:

Я недавно занимался программированием, когда вы должны написать метод, который проверяет баланс круглых скобок в данной строке. Предполагалось, что метод должен принимать строку и возвращать индекс, в котором первые дополнительные «)» или «(« круглые скобки », или длина строки, если они равны. Некоторые примеры входных данных были бы такими:») (asdf))) "- 0; "((((asdf)))" - 0; "(((asdf))" - 1; "(ab) (((cd) (asdf)" - 5.

Я начал с попытки создайте список для каждого направления круглых скобок, в котором будут храниться индексы всех из них в String. Затем я пройду через каждый символ в String, добавлю его индекс в любой из них, если он будет соответствовать, и проверьте, были ли они уже В некоторых случаях эта стратегия работала, но некоторые сценарии по-прежнему не удались. Чувствуя, что я застрял, я проверил некоторые другие ответы на вызов и увидел, что они используют Stack для хранения индекса левых скобок, который они будут нажимать на и поп с этого момента, когда это необходимо. Этот способ работал много, намного лучше, и я чувствовал себя немного смущенным из-за того, что не думал об этом сам.

Это подводит меня к моему вопросу ... как я могу ow, когда лучше использовать Stack над другими различными коллекциями? Каковы некоторые распространенные вещи, которые могут меня опрокинуть, чтобы использовать Stack над любой другой коллекцией?

Я знаю, как стеки работают и использовали их в некоторых учебниках и т. Д., Но никогда не использовали их в реальном мире ... которые, видя простоту, которую они создали с вызовом, заставляют меня думать, что я упустили некоторые возможности для упрощения/улучшения кода.

Answer 1

Когда вам нужно работать с LIFO (Last In First Out) , как при вызове функции или с постфиксной нотацией.

You can see here more java examples!

Answer 2

Как и другие говорили, стек используется, когда вам нужно вашей коллекции, чтобы Последняя In, First Out (LIFO) поведение. Это может проявляться всякий раз, когда вы обрабатываете информацию о «самом верхнем» или «последнем».

Пример, о котором вы говорили, был отличным примером этого, так как для наиболее эффективного процесса группировки скобок вы храните левую скобку в коллекции, и вы удаляете последнюю скобку слева, когда вы запускаете правую часть, скобка.

Стеки также могут использоваться в определенных алгоритмах обхода дерева/графика. Подходы, основанные на глубине, будут использовать Stack для хранения списка узлов, которые еще нужно пройти, поскольку использование Stack в сочетании с последовательным шаблоном вставки имеет неотъемлемое свойство поиска глубины деревьев по их ширине. (Это означает, что алгоритмы пересечения в первом порядке используют очередь.)

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

Есть еще множество других приложений. Все, что у них общего, заключается в том, что они работают на время, когда вам нужно либо на самом верхнем, либо на последнем элементе коллекции. Зная, может ли ваше конкретное приложение извлечь выгоду из стека, требуется немного опыта в понимании того, как распознать эти сценарии.

EDIT: О, и, конечно, есть стека, который использует .NET для метода-объема и временных переменных. Не случайно, что он разделяет свое название с структурой данных. Когда переменная объявляется в методе, ее распределение памяти добавляется в конец стека. Затем, когда метод возвращается и переменная выходит за пределы области действия, эта память вылетает из стека и передается сборщику мусора.

Answer 3

Еще один хороший случай для стека - это когда вы вводите какой-то «контекст», который вы в конце концов уйдете. Тем более, если вы храните некоторую информацию, которая действительна только между двумя моментами, и ее можно забыть, как только вы покинете этот «контекст».

В примере круглых скобок вы «вводите» всякий раз, когда вы сопоставляете ( и «оставляете» круглые скобки при сопоставлении ). Пока вы находитесь в круглых скобках, вам нужно запомнить начальную позицию ( (в случае, если у нее нет соответствия )), но как только вы найдете соответствующее ), вы можете забыть эту информацию.

Answer 4

Ниже выбранный ответ копируется из SO вопрос: When to use the Stack collection in C#?

P.S. Я не плагиат. Я написал этот ответ.

---

В идеале вы используете, или создать по мере необходимости, классы, которые отражают, как вещи работают в реальном мире, то, что вы моделирования в коде. Такие классы дают нам уровень абстракции, поэтому мы можем кодировать в терминах того, что мы моделируем/имитируем. Кроме того, при кодировании некоторой сложной вещи, используя знакомую парадигму, помогает. Для остроумия: О, этот класс Fuzzinator использует стек. Я знаю, что такое стек и как он работает.

Во-вторых, этот класс более высокого уровня абстракции дает нам код, который работает (мы предполагаем, что платформа .NET была протестирована) и экономит время и боль при повторном создании колеса.

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

Использование классов с более совершенной функциональностью помогает ограничить возможности использования этой функции.

В целом ваше приложение просто лучше, когда оно закодировано на соответствующих уровнях абстракции.

Стек является одним из этих классов.

Калькулятор моего HP-41X выполняет свою арифметику, используя стек. Этот способ расчета называется RPN - Reverse Polish Notation.

Если бы я имитировал столовую, то Стек был бы идеальным для этой стопки пластин. Пластины поднимаются и выходят из стека сверху. Не середина, не конец; просто сверху. Стек. Я могу только Push() и Pop(), что делает код более простым и понятным.

В качестве альтернативы, представьте себе кодировку с эквивалентом C# для субатомных частиц - общей коллекции или общего IEnumerable и т. Д. Я в конечном итоге использую общие методы и свойства утилиты с общими именами с множеством переменных параметров, которые в совокупности неясны тот факт, что я укладываю тарелки.