Стек и очередь: структуры данных простыми словами с примерами

Короткий ответ

• Стек — последним пришёл, первым ушёл (LIFO). Как стопка тарелок: кладёте сверху и берёте сверху. Операции: push, pop, peek.
• Очередь — первым пришёл, первым ушёл (FIFO). Как очередь к кассе: новые встают в конец, обслуживают первого. Операции: enqueue, dequeue.

Это не новые виды памяти, а ограничения. Они разрешают доступ только к одному или двум концам, поэтому код проще, а операции работают за O(1).

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

Дек (deque, двусторонняя очередь) позволяет добавлять и забирать с обоих концов. Он может работать и как стек, и как очередь.

Реализация стека

Динамический массив — идеальный стек: вершина — это конец массива, а добавление и удаление с конца стоят амортизированно O(1).

stack = []
stack.append("a")   # push
stack.append("b")
top = stack[-1]     # peek -> "b"
stack.pop()         # pop  -> "b"

const stack = [];
stack.push("a");
stack.push("b");
stack.at(-1); // peek -> "b"
stack.pop();  // pop  -> "b"

Реализация очереди

Здесь наивный подход вредит. list.pop(0) в Python и array.shift() в JavaScript удаляют из начала и сдвигают все остальные элементы — O(n) на каждую операцию.

В Python используйте collections.deque:

from collections import deque

queue = deque()
queue.append("task1")    # enqueue
queue.append("task2")
first = queue.popleft()  # dequeue -> "task1"

Во встроенном JavaScript очереди нет. Для небольших очередей shift() вполне подходит. Для больших храните индекс чтения или используйте связный список:

class Queue {
  constructor() { this.items = []; this.head = 0; }
  enqueue(x) { this.items.push(x); }
  dequeue() {
    if (this.head >= this.items.length) return undefined;
    const x = this.items[this.head++];
    if (this.head > 1024 && this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head); // отбрасываем прочитанное
      this.head = 0;
    }
    return x;
  }
  get size() { return this.items.length - this.head; }
}

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

Где используют стек

• История отмены. Каждое действие кладётся в стек, Ctrl+Z снимает последнее. Повтор (redo) обычно хранится во втором стеке.
• Стек вызовов. Каждый вызов функции кладёт кадр с локальными переменными и адресом возврата, return его снимает. Слишком глубокая рекурсия приводит к stack overflow.
• Проверка скобок. Каждая открывающая скобка кладётся в стек; на закрывающей снимаем верхнюю и проверяем пару.
• Поиск в глубину (DFS) и перебор с возвратом — явно или через рекурсию.

Проверка скобок — классическая задача:

def balanced(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

balanced("{[()]}")  # True
balanced("([)]")    # False

Где используют очередь

• Очереди задач. Фоновые задания, письма, обработка изображений: производители добавляют задачи, воркеры забирают их по порядку. В продакшене это часто отдельный брокер, но идея тот же FIFO.
• Поиск в ширину (BFS). Посещаем узел, добавляем соседей в очередь, повторяем. Так находится кратчайший путь в невзвешенном графе.
• Буферы. Ввод с клавиатуры, сетевые пакеты, потоки событий — всё, что обрабатывается в порядке поступления.

from collections import deque

def bfs(graph, start):
    seen, order = {start}, []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

Частые ошибки

• Использовать shift() или pop(0) на больших очередях и получить квадратичное время.
• Вызывать pop у пустого стека без проверки: Python бросит IndexError, JavaScript молча вернёт undefined.
• Перепутать порядок: если в BFS заменить очередь стеком, получится обход в глубину.
• Глубокая рекурсия там, где явный стек помог бы не упереться в лимит стека вызовов.