02 — Стек и очередь (LIFO/FIFO)

Стек (Stack)

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

Просмотреть стек можно целиком, а работать — только с вершиной. Для этого надо удалить или добавить последний элемент.

Как применяют стеки:

• Для реализации рекурсии.
• Для вычислений постфиксных значений.
• Для временного хранения данных, например истории запросов или изменений.

Очередь (Queue)

Этот вид структуры представляет собой ряд данных, как и стек. Но в отличие от него она работает по принципу FIFO — First In, First Out (англ. «первым пришёл — первым ушёл»). Данные добавляют в конец, а извлекают из начала.

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

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

Как применяют очереди:

• Для реализации очередей, например на доступ к определённому ресурсу.
• Для управления потоками в многопоточных средах.
• Для генерации значений.
• Для создания буферов.