Стек и очередь

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

Очередь работает по принципу «первым пришёл — первым вышел» (FIFO, First In — First Out), как очередь в магазине: новый человек встаёт в конец, а обслуживают того, кто стоит первым. Основные операции: enqueue — добавить в конец, dequeue — взять элемент из начала.

В Python стек можно сделать из обычного списка: s.append(x) добавляет элемент наверх, а s.pop() возвращает верхний элемент и удаляет его. Для очереди удобен deque из модуля collections: q.append(x) добавляет в конец, а q.popleft() берёт элемент из начала. Для очереди не стоит использовать a.pop(0) у обычного списка: он сдвигает все остальные элементы и на больших списках работает медленно.

Стек встречается повсюду: кнопка «Назад» в браузере, отмена действия в текстовом редакторе (Ctrl+Z), порядок вызовов функций (в том числе при рекурсии), проверка правильности скобок в выражении. Очередь применяют для документов, отправленных на печать, сетевых пакетов и порядка выполнения процессов в операционной системе.

Главное

• Стек работает по принципу LIFO: последний добавленный элемент извлекается первым.
• Очередь работает по принципу FIFO: первый добавленный элемент извлекается первым.
• Операции стека: push, pop, peek; операции очереди: enqueue, dequeue.
• В Python стек удобно делать на списке, а очередь — на collections.deque.
• Стек применяют для отмены действий и проверки скобок, очередь — для выполнения задач по порядку.