5.4   Резюме¶

1.   Основные выводы¶

• Стек - это структура данных, следующая правилу «последним пришел - первым вышел», и его можно реализовать с помощью массива или связного списка.
• С точки зрения временной эффективности реализация стека на массиве обычно работает быстрее в среднем, но во время расширения емкости временная сложность отдельной операции push может ухудшаться до \(O(n)\) . Напротив, реализация стека на связном списке дает более стабильные характеристики.
• С точки зрения использования памяти реализация стека на массиве может приводить к некоторой потере пространства. Однако следует учитывать, что узлы связного списка занимают больше памяти, чем элементы массива.
• Очередь - это структура данных, следующая правилу «первым пришел - первым вышел», и ее также можно реализовать с помощью массива или связного списка. Сравнение временной и пространственной эффективности для очереди в целом приводит к тем же выводам, что и для стека.
• Двусторонняя очередь - это очередь с более высокой степенью свободы, которая позволяет добавлять и удалять элементы с обоих концов.

2.   Q & A¶

Q: Реализованы ли кнопки «вперед» и «назад» в браузере с помощью двусвязного списка?

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

Q: Нужно ли освобождать память узла после извлечения его из стека?

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

Q: Двусторонняя очередь выглядит как два соединенных стека. Для чего она нужна?

Двусторонняя очередь похожа на комбинацию стека и очереди или на два соединенных стека. Она объединяет логику обеих структур, поэтому может покрыть все их применения и при этом остается более гибкой.

Q: Как именно реализуются отмена (undo) и повтор (redo)?

Используются два стека: стек A для отмены и стек B для повтора.

1. Каждый раз, когда пользователь выполняет действие, это действие помещается в стек A , а стек B очищается.
2. Когда пользователь выполняет «undo», последнее действие извлекается из стека A и помещается в стек B .
3. Когда пользователь выполняет «redo», последнее действие извлекается из стека B и помещается обратно в стек A .

Оставляйте свои идеи, вопросы и предложения в комментариях