Для чего нужна структура данных стека?

Question

Я продолжаю читать и читать о стеках, но все же я не знаю, как использовать его в программировании в реальном мире!Я знаю, что это структура данных LIFO, но как я могу извлечь из этого выгоду?Я знаю функции POP и PUSH, но что с того?

Answer 1

Каждый раз, когда вы вызываете функцию, вы используете стек! Когда вы делаете что-то одно и вам нужно идти делать что-то другое, вы должны «отложить» то, над чем вы работали, и начать работать над чем-то другим. Каждый раз, когда вы что-то заканчиваете, вам нужно возобновить то, что вы «откладывали» последним. Все, что вы «опускаете», образует стек.

Для вызова функции необходимо «поместить» то, что вы делали, в стек. Для возврата из функции требуется «вытолкнуть» то, что вы в последний раз нажали, чтобы вернуться к ней.

Answer 2

Вот несколько мест, где стек может быть полезен: Каждый раз, когда вам нужно разобрать строку, которая использует скобки для группировки, вам нужен стек. Если вам необходимо сначала пройти по глубине дерева - например, для преобразования внутреннего представления файла XML в файл XML или для вычисления значения выражения, которое было задано пользователем, - вам нужен стек. Конечно, в большинстве таких ситуаций вы можете избежать явного использования его с помощью рекурсии (за кулисами компилятор использует стек для его реализации), но тогда вы рискуете неявным переполнением стека, от которого вы не сможете защититься.

Answer 3

Он используется внутри вашей программы, которая вызывает подпрограммы; перед вызовом подпрограмм все параметры должны быть помещены в стек.

Кроме того, вы можете использовать концепцию стека на высоком уровне (lang высокого уровня), когда это подходит.

Answer 4

Широко используемым стеком является алгоритм шунтирующего двора для преобразования инфиксного выражения, например, 2 + 3, в префиксные выражения, такие как (+ 2 3), для компьютеров гораздо проще вычислить выражения префиксной нотации.