Стек и Очередь, Почему?

Question

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

Answer 1

Существуют алгоритмы, которые проще понять, написать и прочитать с помощью стеков, а не массивов. Это делает более чистый код с меньшим количеством логики управления и итераторов, поскольку они предполагаются самой структурой данных.

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

Answer 2

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

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

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