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

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

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.

\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();
    }
}

Очередь: 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]
    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), без копирования хвоста.

`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;
}

Где стек и очередь в реальной жизни

Стек: вызовы функций (call stack), undo/redo, парсинг выражений, DFS
Очередь: BFS, задачи в воркер-пуле, буфер сообщений, принтер. См. также каналы Go - это thread-safe очередь.