Стек и очередь: два базовых контейнера

Стек и очередь: два базовых контейнера

Стек и очередь - это не просто «структуры данных из учебника». Ты используешь их каждый день, даже не замечая.

Stack LIFO vs Queue FIFO: куда вставляем и откуда достаём

Стек: 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 очередь.

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.