Стек, очередь, дек и монотонный стек

Перед началом: хеш-таблицы (модуль 4). Инструменты: Go 1.27, slices, container/list — для сравнения. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Незакрытая скобка в конфиге унесла полфайла»

Ночной деплой поднял сервис с пустым DSN для базы: в переменную уехала пустая строка, сработал fallback на localhost с дефолтным паролем. Конфиг-сервис, раскрывающий плейсхолдеры ${...}, искал их регуляркой «от ${ до ближайшего }». В шаблоне остался незакрытый ${ в закомментированной строке — выражение склеило его с первым } через четыреста строк, вырезало кусок чужого значения и подставило как имя переменной. Ни одна проверка не сработала: строка оставалась синтаксически валидной.

Второй дефект: парсер проверял «в конфиге есть }», а не вложенность. На ([)] количество скобок сходится, но структура сломана — это ловит только стек. Чиним в модуле: стек как память об ожидании — для скобок, плейсхолдеров, вычислений и обходов; заодно разберём очередь, дек и монотонный стек.

📖 Теория

5.1 Стек на срезе: push, pop, peek

Стек — это LIFO: добавляем и забираем с одного конца. В Go его не нужно изобретать: срез, у которого вершина — последний элемент.

go
stack := make([]int, 0, 16)   // преаллокация — как обычно
stack = append(stack, 42)     // push: амортизированно O(1)
top := stack[len(stack)-1]    // peek без удаления
stack = stack[:len(stack)-1]  // pop: O(1), ничего не сдвигается

Все операции — O(1): append амортизирован (модуль 1), а усечение среза ничего не копирует; пустота — это len(stack) == 0.

5.2 min-stack: минимум за O(1)

Задача: push, pop, min за O(1). Наивный min — проход по всему стеку, O(n); решение — второй стек с минимумом на каждой глубине.

go
type minStack struct {
	data, mins []int // mins[i] — минимум стека на глубине i
}

func (s *minStack) push(v int) {
	s.data = append(s.data, v)
	if len(s.mins) == 0 || v <= s.mins[len(s.mins)-1] {
		s.mins = append(s.mins, v) // новый минимум (или дубликат прежнего)
	}
}

При pop минимум снимается, только если уходит именно он. Условие v <= top (не <) принципиально: с < дубликаты минимума теряются и mins останется с устаревшим значением. Цена — до двух копий данных.

5.3 Очередь: почему срез не годится, и кольцевой буфер

FIFO-очередь «из головы» на срезе выглядит как q = q[1:] — и это ловушка: массив не освобождается (память держится), а ёмкость тает; честный copy для сдвига — это O(n) на каждый pop. Одна операция из двух всегда плоха — пока не вспомнить про кольцо.

Кольцевой буфер — массив фиксированной длины плюс head и count. Хвост — это (head + count) % len(buf): индексы «заворачиваются».

go
type ring[T any] struct {
	buf         []T
	head, count int
}

func (r *ring[T]) pop() (T, bool) {
	if r.count == 0 {
		var zero T
		return zero, false
	}
	v := r.buf[r.head]
	r.head = (r.head + 1) % len(r.buf) // замыкание кольца
	r.count--
	return v, true
}

Оба конца — O(1), память фиксирована. Дек — тот же буфер с операциями и с головы: она двигается назад по модулю len(buf). Это базовый инструмент для окна переменной ширины и «скользящего максимума».

5.4 Монотонный стек: next greater за O(n)

Задача: для каждого элемента найти ближайший справа больший. Перебор — O(n²); монотонный стек решает за один проход: держим индексы с убывающими значениями; приходит элемент больше вершины — вершина «дождалась ответа» и покидает стек.

go
func nextGreater(a []int) []int {
	res := make([]int, len(a))
	for i := range res {
		res[i] = -1
	}
	stack := make([]int, 0, len(a)) // индексы, не значения: нужны позиции
	for i, v := range a {
		for len(stack) > 0 && a[stack[len(stack)-1]] < v {
			res[stack[len(stack)-1]] = v // ответ вершине
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}
	return res
}

Почему O(n): каждый индекс кладётся в стек один раз и снимается не более одного раза. Тот же шаблон «первый меньший слева и справа» даёт идею largest rectangle in histogram.

5.5 Где это живёт

Один приём — четыре сценария: скобки и плейсхолдеры (валидность вложенности из инцидента), RPN (два операнда со стека на каждый оператор), undo/redo (стек действий), итеративный обход дерева — рекурсию заменяет явный стек; понадобится в модуле 11. Очередь — это BFS (модуль 14) и буферизация событий.

5.6 Компромиссы

Правило: срез — для стека и для очереди, которую можно крутить кольцом; container/list — когда нужны стабильные указатели на узлы (LRU из модуля 6); монотонный стек — когда вопрос звучит «первый больше-меньше».

💻 Практика

1. Валидация вложенности. Реализуйте validBrackets для ()[]{} и напишите версию firstBad(s string) (int, bool), возвращающую индекс первого символа, ломающего структуру. Тесты: "", "([)]", "(]", "{", лишняя ")"; почему счётчики скобок без стека не ловят "([)]"?
2. min-stack. Реализуйте стек с push, pop, top, min за O(1). Тест: push 2, push 2, pop, min → 2 (дубликаты минимума); push 5, push 1, pop, min → 5. Объясните, что сломает условие < вместо <=.
3. next greater. Реализуйте nextGreater из §5.4. Тесты: [2,1,2,4,3] → [4,2,4,-1,-1]; убывающий вход — все -1; возрастающий — сдвиг влево на один. Затем вариант circular: массив по кругу, ответ ищется после «заворота» — с чего начать обход и сколько нужно проходов?
4. RPN-вычислитель. evalRPN(expr string) (int, error) для "+ - * /" на целых: "3 4 + 2 *" → 14, "5 1 2 + 4 * + 3 -" → 14. Деление на ноль, недостаток операндов и мусорные токены — ошибка, не паника. Тестовые случаи включите все три.
5. Кольцевой буфер. Реализуйте ring с фиксированной ёмкостью 4: push, pop, len. Выберите политику переполнения (ошибка или перезапись старейшего) и обоснуйте. Тест на заворачивание: push 3, pop 2, push 3 — проверьте head, count и порядок. Сравните с q = q[1:]: что происходит с памятью и cap у каждого.

🧩 Quiz

✅ Итоги модуля

• Стек в Go — это срез: push — append, pop — усечение; O(1) с конца за счёт амортизации.
• min-stack показывает приём «вторая структура рядом»: минимум на глубине за O(1) ценой дополнительной памяти.
• Очередь на срезе с удалением головы — ловушка; кольцевой буфер даёт O(1) с обоих концов и фиксированную память.
• Монотонный стек: индексы с монотонными значениями, каждый входит и выходит один раз — O(n) для next greater и подобных задач.
• Скобки, RPN, undo и итеративные обходы — один стек, четыре разных продовых сценария.

🔗 Мостик к Модулю 6

Стек и очередь хороши, пока доступ нужен с краёв. Дальше — структура, где вставка и удаление работают в любой точке по указателю: связные списки. Развернём список, найдём середину методом fast/slow и соберём LRU-кэш из map и двусвязного списка — первый в курсе пример структуры, собранной из двух.