Стек и очередь: два базовых контейнера
Стек и очередь: два базовых контейнера
Стек и очередь - это не просто «структуры данных из учебника». Ты используешь их каждый день, даже не замечая.
Стек: LIFO (Last In, First Out)
type Stack[T any] struct {
items []T
}
func (s *Stack[T]) Push(item T) {
s.items = append(s.items, item)
}
func (s *Stack[T]) Pop() (T, bool) {
if len(s.items) == 0 {
var zero T
return zero, false
}
item := s.items[len(s.items)-1]
s.items = s.items[:len(s.items)-1]
return item, true
}
func (s *Stack[T]) Peek() (T, bool) {
if len(s.items) == 0 {
var zero T
return zero, false
}
return s.items[len(s.items)-1], true
}
func (s *Stack[T]) Len() int {
return len(s.items)
}
<?php
declare(strict_types=1);
// Вариант 1: SplStack из ядра (всегда доступен)
$stack = new SplStack();
$stack->push(1);
$stack->push(2);
$stack->push(3);
echo $stack->top(); // 3 (peek без pop)
echo $stack->pop(); // 3
echo count($stack); // 2
// Вариант 2: голый array как стек (push/pop O(1) с конца)
$arr = [];
$arr[] = 1; // push
$arr[] = 2;
$top = array_pop($arr); // pop
// Вариант 3: \Ds\Stack (ext-ds, чуть быстрее на больших объёмах)
$ds = new Ds\Stack();
$ds->push('a', 'b', 'c');
$ds->peek(); // 'c'
$ds->pop(); // 'c'
В PHP не нужно писать стек руками: есть готовый \SplStack (наследник \SplDoublyLinkedList). Альтернативно - \Ds\Stack из ext-ds.
from typing import Generic, TypeVar
T = TypeVar("T")
# Стек поверх list - того же динамического массива, что и слайс в Go.
# Вместо (T, bool) - исключение IndexError, как у самого list.pop().
class Stack(Generic[T]):
def __init__(self) -> None:
self._items: list[T] = []
def push(self, item: T) -> None:
self._items.append(item)
def pop(self) -> T:
if not self._items:
raise IndexError("pop from empty stack")
return self._items.pop() # O(1): снимает последний элемент
def peek(self) -> T:
if not self._items:
raise IndexError("peek at empty stack")
return self._items[-1]
def __len__(self) -> int:
return len(self._items)
# На практике класс не пишут: голый list уже стек -
# append() это push, pop() это pop, items[-1] это peek.
\SplStackдоступен из коробки, без расширений.array_push/array_popработают на голом массиве - часто это самый прагматичный выбор.
Практика: проверка скобок
Классическая задача - проверить, что скобки сбалансированы.
func isValid(s string) bool {
stack := &Stack[rune]{}
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
for _, ch := range s {
switch ch {
case '(', '[', '{':
stack.Push(ch)
case ')', ']', '}':
top, ok := stack.Pop()
if !ok || top != pairs[ch] {
return false
}
}
}
return stack.Len() == 0
}
// isValid("({[]})") → true
// isValid("([)]") → false
// isValid("((") → false
<?php
declare(strict_types=1);
final class BracketsValidator
{
/** @var array<string, string> */
private const PAIRS = [')' => '(', ']' => '[', '}' => '{'];
public function isValid(string $s): bool
{
$stack = new SplStack();
foreach (str_split($s) as $ch) {
$isOpen = match ($ch) {
'(', '[', '{' => true,
')', ']', '}' => false,
default => null,
};
if ($isOpen === true) {
$stack->push($ch);
} elseif ($isOpen === false) {
if ($stack->isEmpty() || $stack->pop() !== self::PAIRS[$ch]) {
return false;
}
}
}
return $stack->isEmpty();
}
}
def is_valid(s: str) -> bool:
stack: Stack[str] = Stack()
pairs = {")": "(", "]": "[", "}": "{"}
for ch in s:
match ch:
case "(" | "[" | "{":
stack.push(ch)
case ")" | "]" | "}":
if len(stack) == 0 or stack.pop() != pairs[ch]:
return False
return len(stack) == 0
# is_valid("({[]})") -> True
# is_valid("([)]") -> False
# is_valid("((") -> False
Практика: следующий больший элемент (монотонный стек)
Задача: для каждого числа найти ближайшее справа число больше него (если нет - -1). Наивное решение - для каждого элемента просмотреть всё справа, это O(n²).
Монотонный стек решает за O(n). В стеке лежат индексы элементов, для которых ответ ещё не найден, и значения под ними убывают снизу вверх. Пришёл новый элемент - снимаем с вершины все, что меньше него: для них он и есть «следующий больший». Каждый индекс кладётся и снимается ровно один раз, поэтому суммарно O(n).
// nextGreater для каждого элемента находит ближайший справа больший.
// Если такого нет - -1.
func nextGreater(nums []int) []int {
res := make([]int, len(nums))
for i := range res {
res[i] = -1
}
stack := []int{} // индексы; значения под ними убывают снизу вверх
for i, v := range nums {
// v - «следующий больший» для всех меньших на вершине
for len(stack) > 0 && nums[stack[len(stack)-1]] < v {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res[top] = v
}
stack = append(stack, i)
}
return res
}
// nextGreater([]int{2, 1, 5, 3, 4}) -> [5 5 -1 4 -1]
<?php
declare(strict_types=1);
/**
* @param list<int> $nums
* @return list<int>
*/
function nextGreater(array $nums): array
{
$res = array_fill(0, count($nums), -1);
$stack = []; // индексы; значения под ними убывают снизу вверх
foreach ($nums as $i => $v) {
while ($stack !== [] && $nums[$stack[count($stack) - 1]] < $v) {
$res[array_pop($stack)] = $v;
}
$stack[] = $i;
}
return $res;
}
// nextGreater([2, 1, 5, 3, 4]) -> [5, 5, -1, 4, -1]
def next_greater(nums: list[int]) -> list[int]:
res = [-1] * len(nums)
stack: list[int] = [] # индексы; значения под ними убывают снизу вверх
for i, v in enumerate(nums):
while stack and nums[stack[-1]] < v:
res[stack.pop()] = v
stack.append(i)
return res
# next_greater([2, 1, 5, 3, 4]) -> [5, 5, -1, 4, -1]
Тот же приём решает задачи «сколько дней ждать более тёплой погоды» и «самый большой прямоугольник в гистограмме».
Очередь: FIFO (First In, First Out)
type Queue[T any] struct {
items []T
}
func (q *Queue[T]) Enqueue(item T) {
q.items = append(q.items, item)
}
func (q *Queue[T]) Dequeue() (T, bool) {
if len(q.items) == 0 {
var zero T
return zero, false
}
item := q.items[0]
var zero T
q.items[0] = zero // не держим ссылку на снятый элемент
q.items = q.items[1:]
return item, true
}
func (q *Queue[T]) Len() int {
return len(q.items)
}
<?php
declare(strict_types=1);
$queue = new SplQueue();
$queue->enqueue('a');
$queue->enqueue('b');
$queue->enqueue('c');
$head = $queue->dequeue(); // 'a' - O(1), реально удаляется голова
echo count($queue); // 2
// Альтернатива: массив + array_shift (но array_shift - O(n)!)
$arr = [];
array_push($arr, 'a', 'b', 'c');
$first = array_shift($arr); // O(n) - переиндексация остальных
В PHP - \SplQueue (тоже наследник \SplDoublyLinkedList). Это полноценный двусвязный список, поэтому dequeue - O(1), без копирования хвоста.
from collections import deque
from typing import Generic, TypeVar
T = TypeVar("T")
class Queue(Generic[T]):
def __init__(self) -> None:
# Не list: list.pop(0) сдвигает все элементы - O(n).
# deque - двусвязный список блоков по 64 элемента,
# добавление и удаление с обоих концов за O(1).
self._items: deque[T] = deque()
def enqueue(self, item: T) -> None:
self._items.append(item)
def dequeue(self) -> T:
if not self._items:
raise IndexError("dequeue from empty queue")
return self._items.popleft() # O(1), память головы освобождается сразу
def __len__(self) -> int:
return len(self._items)
# Для очереди между потоками есть queue.Queue - тот же deque,
# но с блокировками и ожиданием: ближе к каналу Go, чем к этому классу.
⚠️ Производительность
q.items[1:]оставляет снятый элемент в массиве до следующего перевыделения вappend: тогда копируются только живые элементы, и бесконечного роста нет. Но если в очереди указатели, объекты, на которые они ссылаются, GC до этого момента не соберёт. Минимальная правка - обнулять голову перед сдвигом:var zero T; q.items[0] = zero; q.items = q.items[1:]. Для высоконагруженных очередей лучше кольцевой буфер на слайсе;container/listаллоцирует память на каждый элемент и обычно медленнее.
В PHP та же ловушка для
array_shift- он переиндексирует весь массив, O(n). На горячем пути используй\SplQueue(O(1) с обеих сторон) или\Ds\Queueиз ext-ds.
Практика: обход графа в ширину (BFS)
func bfs(graph map[string][]string, start string) []string {
visited := make(map[string]bool)
queue := &Queue[string]{}
result := []string{}
queue.Enqueue(start)
visited[start] = true
for queue.Len() > 0 {
node, _ := queue.Dequeue()
result = append(result, node)
for _, neighbor := range graph[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue.Enqueue(neighbor)
}
}
}
return result
}
<?php
declare(strict_types=1);
/**
* @param array<string, array<string>> $graph
* @return array<string>
*/
function bfs(array $graph, string $start): array
{
$visited = [];
$queue = new SplQueue();
$result = [];
$queue->enqueue($start);
$visited[$start] = true;
while (!$queue->isEmpty()) {
$node = $queue->dequeue();
$result[] = $node;
foreach ($graph[$node] ?? [] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue->enqueue($neighbor);
}
}
}
return $result;
}
def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
visited: set[str] = set() # вместо map[string]bool - множество
queue: Queue[str] = Queue()
result: list[str] = []
queue.enqueue(start)
visited.add(start)
while len(queue) > 0:
node = queue.dequeue()
result.append(node)
for neighbor in graph.get(node, []): # graph[node] для узла без рёбер даст KeyError
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue(neighbor)
return result
Очередь с приоритетом
Обычная очередь отдаёт элементы в порядке прихода. Очередь с приоритетом всегда отдаёт самый важный элемент, например с минимальным временем запуска. Её строят на куче (binary heap): это дерево, уложенное в массив, где каждый родитель не больше своих детей. Минимум всегда в корне, а вставка и извлечение стоят O(log n).
В Go готовой структуры нет, есть пакет container/heap: ты описываешь слайс и пять методов интерфейса heap.Interface (Len, Less, Swap, Push, Pop), а пакет поддерживает порядок кучи.
import "container/heap"
// IntHeap - min-heap из int: Less сравнивает «меньше».
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func main() {
h := &IntHeap{5, 2, 8}
heap.Init(h) // O(n): упорядочить как кучу
heap.Push(h, 1) // O(log n)
for h.Len() > 0 {
fmt.Print(heap.Pop(h), " ") // 1 2 5 8 - всегда минимум
}
}
Для max-heap достаточно перевернуть сравнение в Less. Важно вызывать heap.Push и heap.Pop, а не методы h.Push напрямую: только функции пакета восстанавливают порядок кучи.
<?php
declare(strict_types=1);
// Куча из коробки: SplMinHeap / SplMaxHeap
$heap = new SplMinHeap();
foreach ([5, 2, 8, 1] as $v) {
$heap->insert($v); // O(log n)
}
while (!$heap->isEmpty()) {
echo $heap->extract(), ' '; // 1 2 5 8
}
// Очередь с явным приоритетом: больший приоритет выходит первым
$pq = new SplPriorityQueue();
$pq->insert('low', 1);
$pq->insert('high', 10);
echo $pq->extract(); // high
import heapq
# heapq работает поверх обычного list и всегда держит минимум в h[0]
h = [5, 2, 8]
heapq.heapify(h) # O(n)
heapq.heappush(h, 1) # O(log n)
print([heapq.heappop(h) for _ in range(len(h))]) # [1, 2, 5, 8]
Где встречается: планировщики задач и таймеров, алгоритм Дейкстры, выбор top-K элементов.
Где стек и очередь в реальной жизни
- Стек: вызовы функций (call stack), undo/redo, парсинг выражений, DFS
- Очередь: BFS, задачи в воркер-пуле, буфер сообщений, принтер. См. также каналы Go - это thread-safe очередь.