Интересной задачей является реализация очереди с помощью двух стеков. Классическое решение использует один стек для добавления элементов (enqueue), а другой — для удаления (dequeue). Когда требуется удалить элемент, но второй стек пуст, все элементы перекладываются из первого стека во второй, в результате чего порядок инвертируется и первый добавленный элемент оказывается на вершине второго стека, готовый к извлечению.

Пример 8

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

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

Пример 9

Функция отмены действий в редакторах также полагается на стек для хранения состояний.

Пример 10

Стек вызовов, управляющий выполнением функций в программе, — еще один яркий пример. Когда функция вызывает другую, ее контекст помещается в стек, а после завершения вложенной функции — восстанавливается.

Пример 11

Проверка корректности HTML-тегов — задача, где стек отслеживает вложенность открывающих и закрывающих элементов.

Пример 12

Для реализации очереди в Python оптимально использовать класс deque из модуля collections. Это двусторонняя очередь, которая обеспечивает константную сложность O(1) для операций добавления и удаления с обоих концов, в отличие от списка, где удаление из начала (pop(0)) имеет линейную сложность O(n). Полноценная реализация очереди на deque включает все основные операции.

Пример 13

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

Пример 14

С точки зрения сложности операций, стек на основе списка Python обеспечивает O(1) для push, pop и peek, так же как и проверка на пустоту. Очередь на основе deque также гарантирует O(1) для enqueue, dequeue, front и isEmpty. Важно подчеркнуть, что использование обычного списка для очереди неэффективно из-за линейной сложности операции pop(0), что делает deque предпочтительным выбором.

В заключение, стек и очередь — это фундаментальные структуры данных, каждая со своим строгим принципом доступа: LIFO для стека, подобно стопке тарелок, и FIFO для очереди, как очередь людей. Их понимание критически важно для изучения алгоритмов и системного программирования, поскольку они лежат в основе множества механизмов — от управления памятью и планирования процессов до синтаксического анализа и работы с историей. Ключевые моменты для запоминания: стек оперирует с одним концом, очередь — с двумя; в Python для стека используется list, для очереди — deque; обе структуры обеспечивают высокую эффективность основных операций.

#algorithm