Стек и очередь: порядок обработки как часть договора

Редактор проверяет скобки в выражении ([{}]). Диспетчер обрабатывает заявки в порядке поступления. В обоих случаях элементы добавляют и удаляют, но требуемый порядок разный. Одна операция «достать следующий» без уточнения порядка не описывает структуру.

Последний пришёл — первый вышел

Стек работает по правилу LIFO. Добавление и удаление происходят с одного конца. В Go учебный стек удобно хранить срезом: append добавляет элемент, чтение последнего и сокращение длины удаляют его. Перед обращением к последнему элементу проверяйте len: пустой стек — обычное состояние, а не повод для паники.

Для проверки скобок запоминаем незакрытые открывающие скобки. Когда приходит закрывающая, она должна соответствовать последней открытой. На ([)] число открытий и закрытий одинаково, но порядок неверен. Один счётчик не различит этот случай.

stack := []rune{}
// При открытии:
stack = append(stack, '(')
// При закрытии ')':
if len(stack) == 0 || stack[len(stack)-1] != '(' {
    // ошибка соответствия
} else {
    stack = stack[:len(stack)-1]
}

После просмотра префикса stack хранит именно ещё не закрытые открытия в их порядке. В конце он должен быть пустым. В эталонной Balanced поддерживаются три типа скобок, а остальные символы игнорируются. Это выбранный договор, не универсальная проверка синтаксиса языка: скобки внутри строковых литералов здесь тоже считаются.

Первый пришёл — первый вышел

Очередь работает по FIFO. Новые элементы приходят в конец, обработка идёт с начала. Она нужна при обходе графа в ширину и обработке событий одного потока. FIFO не обещает, что несколько параллельных исполнителей завершат задания в таком же порядке: различайте извлечение и завершение.

queue := []int{10, 20, 30}
for head := 0; head < len(queue); head++ {
    current := queue[head]
    // Здесь можно добавить новые значения через append.
    _ = current
}

Вместо удаления первого элемента с копированием хвоста мы двигаем head. На последовательности из n извлечений постоянное копирование хвоста дало бы O(n²) работы. Учебная очередь с head оставляет уже обработанные элементы в срезе: общая память O(n). Для долго работающей службы нужна политика освобождения или кольцевой буфер.

Если элементы содержат указатели, забытые значения в backing array могут удерживать объекты для сборщика мусора. Обнуление извлечённой ячейки и периодическое уплотнение требуют аккуратного договора владения. Пока важнее не скрыть эту цену, чем писать производственный контейнер в учебном упражнении.

Очередь из двух стеков

Можно складывать новые элементы в стек input, а извлекать из output. Если output пуст, перемещаем в него весь input: порядок переворачивается, и самым верхним становится самый ранний элемент. Одна операция переноса может стоить O(n), но каждый элемент переносится не больше одного раза. Серия n добавлений и n удалений требует O(n) действий, значит операция имеет амортизированную O(1) стоимость.

Это не среднее по случайным входам. Любая последовательность допустимых операций получает ту же суммарную границу. Память — O(n) для одновременно хранящихся элементов.

Самостоятельная практика

Напишите Balanced и тесты (), ([{}]), ([)], ], ((, пустой строки. Затем создайте очередь двух стеков с методами Push и Pop, где Pop возвращает (value, ok). Последовательность Push1,Push2,Pop,Push3,Pop,Pop должна вернуть 1,2,3.

Критерии готовности: пустое извлечение не паникует; разные типы скобок проверяются; в очереди порядок сохраняется при чередовании действий; объяснена суммарная цена переносов. На практику заложите 45 минут.

Разбор

Число скобок само по себе недостаточно. Нужен последний незакрытый тип, поэтому подходит стек. Для очереди второй стек переворачивает вход только когда прежние элементы output закончились. Перенос при каждом Push изменит порядок или стоимость. Проверяйте не только окончательный результат, но и промежуточные извлечения.

Источники: Princeton: стеки и очереди, Go: container/list. Список стандартной библиотеки не отменяет стоимость поиска узла; для этих учебных операций срез обычно проще.