Стеки и очереди

живой пример

public class Stack {
    private final long[] a;
    private int top = -1;
    Stack(int size) { a = new long[size]; }
    void push(long v) { a[++top] = v; }
    long pop()        { return a[top--]; }
    long peek()       { return a[top]; }
    boolean isEmpty() { return top == -1; }

    public static void main(String[] args) {
        Stack s = new Stack(4);
        s.push(17);
        s.push(42);
        s.push(8);
        System.out.println("на вершине: " + s.peek());
        StringBuilder order = new StringBuilder();
        while (!s.isEmpty()) order.append(s.pop()).append(' ');
        System.out.println("выходят: " + order);
    }
}

живой пример

package main

import "fmt"

type Stack struct {
	a   []int64
	top int
}

func NewStack(size int) *Stack {
	return &Stack{a: make([]int64, size), top: -1}
}

func (s *Stack) Push(v int64) {
	s.top++
	s.a[s.top] = v
}

func (s *Stack) Pop() int64 {
	v := s.a[s.top]
	s.top--
	return v
}

func (s *Stack) Peek() int64 { return s.a[s.top] }

func (s *Stack) IsEmpty() bool { return s.top == -1 }

func main() {
	s := NewStack(4)
	s.Push(17)
	s.Push(42)
	s.Push(8)
	fmt.Println("на вершине:", s.Peek())
	order := ""
	for !s.IsEmpty() {
		order += fmt.Sprint(s.Pop(), " ")
	}
	fmt.Println("выходят:", order)
}

живой пример

class Stack {
  #a;
  #top = -1;
  constructor(size) { this.#a = new Array(size); }
  push(v) { this.#a[++this.#top] = v; }
  pop() { return this.#a[this.#top--]; }
  peek() { return this.#a[this.#top]; }
  isEmpty() { return this.#top === -1; }
}

const s = new Stack(4);
s.push(17);
s.push(42);
s.push(8);
console.log("на вершине:", s.peek());
let order = "";
while (!s.isEmpty()) order += s.pop() + " ";
console.log("выходят:", order);

живой пример

class Stack:
    def __init__(self, size: int) -> None:
        self._a = [0] * size
        self._top = -1

    def push(self, v: int) -> None:
        self._top += 1
        self._a[self._top] = v

    def pop(self) -> int:
        v = self._a[self._top]
        self._top -= 1
        return v

    def peek(self) -> int:
        return self._a[self._top]

    def is_empty(self) -> bool:
        return self._top == -1


s = Stack(4)
s.push(17)
s.push(42)
s.push(8)
print("на вершине:", s.peek())
order = ""
while not s.is_empty():
    order += f"{s.pop()} "
print("выходят:", order)

живой пример

public class RingBuffer {
    private final int[] a;
    private int head, tail, size;
    RingBuffer(int capacity) { a = new int[capacity]; }

    boolean offer(int v) {
        if (size == a.length) return false;
        a[tail] = v;
        tail = (tail + 1) % a.length;
        size++;
        return true;
    }

    int poll() {
        int v = a[head];
        head = (head + 1) % a.length;
        size--;
        return v;
    }

    public static void main(String[] args) {
        RingBuffer q = new RingBuffer(3);
        q.offer(1); q.offer(2); q.offer(3);
        System.out.println("полна, четвёртый не влез: " + q.offer(4));
        System.out.println("забрали " + q.poll() + ", хвост перескочил в ячейку " + q.tail + ": " + q.offer(4));
        System.out.println(q.poll() + " " + q.poll() + " " + q.poll());
    }
}

живой пример

package main

import "fmt"

type RingBuffer struct {
	a                []int
	head, tail, size int
}

func NewRingBuffer(capacity int) *RingBuffer {
	return &RingBuffer{a: make([]int, capacity)}
}

func (q *RingBuffer) Offer(v int) bool {
	if q.size == len(q.a) {
		return false
	}
	q.a[q.tail] = v
	q.tail = (q.tail + 1) % len(q.a)
	q.size++
	return true
}

func (q *RingBuffer) Poll() int {
	v := q.a[q.head]
	q.head = (q.head + 1) % len(q.a)
	q.size--
	return v
}

func main() {
	q := NewRingBuffer(3)
	q.Offer(1)
	q.Offer(2)
	q.Offer(3)
	fmt.Println("полна, четвёртый не влез:", q.Offer(4))
	first := q.Poll()
	fmt.Printf("забрали %d, хвост перескочил в ячейку %d: %v\n", first, q.tail, q.Offer(4))
	fmt.Println(q.Poll(), q.Poll(), q.Poll())
}

живой пример

class RingBuffer {
  constructor(capacity) {
    this.a = new Array(capacity);
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }
  offer(v) {
    if (this.size === this.a.length) return false;
    this.a[this.tail] = v;
    this.tail = (this.tail + 1) % this.a.length;
    this.size++;
    return true;
  }
  poll() {
    const v = this.a[this.head];
    this.head = (this.head + 1) % this.a.length;
    this.size--;
    return v;
  }
}

const q = new RingBuffer(3);
q.offer(1); q.offer(2); q.offer(3);
console.log("полна, четвёртый не влез:", q.offer(4));
console.log(`забрали ${q.poll()}, хвост перескочил в ячейку ${q.tail}: ${q.offer(4)}`);
console.log(q.poll(), q.poll(), q.poll());

живой пример

class RingBuffer:
    def __init__(self, capacity: int) -> None:
        self.a = [0] * capacity
        self.head = self.tail = self.size = 0

    def offer(self, v: int) -> bool:
        if self.size == len(self.a):
            return False
        self.a[self.tail] = v
        self.tail = (self.tail + 1) % len(self.a)
        self.size += 1
        return True

    def poll(self) -> int:
        v = self.a[self.head]
        self.head = (self.head + 1) % len(self.a)
        self.size -= 1
        return v


q = RingBuffer(3)
q.offer(1); q.offer(2); q.offer(3)
print("полна, четвёртый не влез:", q.offer(4))
print(f"забрали {q.poll()}, хвост перескочил в ячейку {q.tail}: {q.offer(4)}")
print(q.poll(), q.poll(), q.poll())

Стек и очередь легко написать самому — кода в них на десять строк, — но в стандартной библиотеке они есть. Выбирать приходится между двумя классами, и один из них лучше обойти стороной.

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

Все операции — O(1) (амортизированно — из-за того самого редкого переезда в больший массив):

• как стек: push кладёт в голову, pop забирает оттуда же, peek смотрит;
• как очередь: offer добавляет в хвост, poll забирает из головы.

У каждой операции очереди два имени, и выбор между ними не вкус, а поведение на границе. add, remove и element бросают исключение: add в переполненную ограниченную очередь даёт IllegalStateException, remove и element на пустой NoSuchElementException. Их пары offer, poll и peek вместо этого возвращают специальное значение: false или null. Правило выбора простое: если пустая очередь в этом месте это ошибка программы, берут бросающую пару, чтобы упасть сразу и с понятным следом; если пустота штатная (воркер проверяет, есть ли работа), берут poll и проверяют null. Самая частая ошибка новичка это remove() в цикле «пока что-то есть» и NoSuchElementException на последнем шаге. У стека та же история: pop на пустом ArrayDeque бросает NoSuchElementException, pollFirst возвращает null.

Один класс закрывает обе структуры — дек их обобщает. Разница видна на одних и тех же данных:

живой пример

import java.util.ArrayDeque;
import java.util.Deque;

public class StackVsQueue {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        Deque<String> queue = new ArrayDeque<>();
        for (String task : new String[]{"первая", "вторая", "третья"}) {
            stack.push(task);
            queue.offer(task);
        }
        System.out.println("стек:    " + stack.pop() + ", " + stack.pop());
        System.out.println("очередь: " + queue.poll() + ", " + queue.poll());
    }
}

Три одинаковых задачи, один и тот же класс — но стек начинает с последней, а очередь с первой. А интерфейсы Deque и Queue, которые он реализует, — это и есть ADT в чистом виде: код пишут против поведения, а реализацию подставляют любую.

Класс, который обходят стороной, — Stack. Он появился в самой первой версии Java и унаследован от Vector, а значит, каждый его метод синхронизирован: за блокировки вы платите даже в одном потоке, где они не нужны. Хуже другое: Stack — это ещё и список, и перебирается он снизу вверх, от самого старого элемента к вершине, то есть в порядке, обратном тому, в котором стек отдаёт элементы через pop. Новый код на Stack не пишут — берут ArrayDeque.

Приоритетная очередь живёт отдельно: это PriorityQueue, построенная на куче. Одна деталь ломает ожидания: «выше приоритет» здесь по умолчанию значит меньше по порядку сравнения. Без компаратора PriorityQueue всегда отдаёт наименьший элемент, и чтобы первым выходил самый большой, компаратор задают явно — например, Comparator.reverseOrder().

Про потоки. ArrayDeque не потокобезопасен так же, как HashMap: два потока, кладущих в него одновременно, портят индексы головы и хвоста молча, а Stack «зря синхронизирован» только для одного потока, для нескольких его замка тоже недостаточно для составных операций. Очередь задач в сервисе почти всегда межпоточная: один поток кладёт, другой забирает. Для неё берут BlockingQueue из java.util.concurrent: ArrayBlockingQueue это то же кольцо, но ограниченное и с замком, take ждёт, пока появится элемент, put ждёт места, а offer с таймаутом отвечает на вопрос про переполнение из раздела про очередь. Как эти очереди устроены и чем отличаются, разбирает фаза про многопоточность.

Грабля у ArrayDeque одна, но о неё спотыкаются регулярно: null в него класть нельзя — прилетит NullPointerException. poll и peek возвращают null, когда дек пуст, и разреши мы хранить null внутри — этот ответ стал бы двусмысленным. LinkedList в роли дека null принимает, и там пустой дек и дек с null на конце различить уже нельзя.

Стек и очередь легко написать самому — кода в них на десять строк, — и в Go именно так и делают: отдельных типов для них в стандартной библиотеке нет, обе структуры собирают из среза.

Стек это срез и три строки: s = append(s, v) кладёт на вершину, s[len(s)-1] смотрит, s = s[:len(s)-1] снимает. Всё за O(1) амортизированно, переезд в больший массив редкий. Очередь на срезе пишут так же: q = append(q, v) в хвост, v, q = q[0], q[1:] из головы. Здесь прячется грабля: q[1:] не освобождает память, срез просто сдвигает начало, а массив за спиной остаётся прежним, пока append не переедет. Долгоживущая очередь, через которую прошли миллионы задач, держит в памяти хвост давно обработанных, а если в элементах указатели, то и всё, на что они смотрят. Лечат либо обнулением q[0] перед сдвигом, либо кольцом, как в разделе про циклическую очередь.

Второй способ сделать очередь, и он же ответ на вопрос про переполнение: канал. make(chan Task, 100) это кольцевой буфер на сто элементов с замком внутри. Отправка ch <- t в полный канал ждёт места, чтение <-ch из пустого ждёт элемента; отказать вместо ожидания позволяет select с веткой default, подождать ограниченно — select с таймером. То есть три стратегии из раздела про переполнение это три формы одного select.

Один срез закрывает обе структуры — разница только в том, с какого конца забирать. Она видна на одних и тех же данных:

живой пример

package main

import "fmt"

func main() {
	var stack, queue []string
	for _, task := range []string{"первая", "вторая", "третья"} {
		stack = append(stack, task)
		queue = append(queue, task)
	}
	pop := func() string {
		v := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		return v
	}
	poll := func() string {
		v := queue[0]
		queue = queue[1:]
		return v
	}
	fmt.Println("стек:    " + pop() + ", " + pop())
	fmt.Println("очередь: " + poll() + ", " + poll())
}

Три одинаковых задачи, один и тот же срез — но стек начинает с последней, а очередь с первой.

В стандартной библиотеке есть и container/list, двусвязный список с PushBack, PushFront и Remove, из которого можно сделать и стек, и очередь, и дек. В бою его берут редко: значения в нём хранятся как any, то есть с упаковкой и без проверки типов, а узлы разбросаны по памяти. Срез почти всегда быстрее, а честную очередь без утечки пишут кольцом на срезе.

Приоритетная очередь живёт в container/heap: это не тип, а функции heap.Push и heap.Pop над вашим типом с пятью методами интерфейса, разобрано в статье про кучу. Одна деталь ломает ожидания: «выше приоритет» здесь значит меньше по Less. Пока Less не перевёрнут, первым выходит наименьший элемент.

Про горутины. Срез и container/list не потокобезопасны: одновременный append из двух горутин это гонка, которую находит go test -race, а без него данные портятся молча. Очередь задач в сервисе почти всегда межгорутинная: одна горутина кладёт, другие забирают. Для неё берут канал: make(chan Task, n) это то же кольцо, но с замком, ожиданием и закрытием через close, после которого цикл for task := range ch сам заканчивается. Как каналы устроены и чем буферизованные отличаются от небуферизованных, разбирает статья про горутины и каналы.

Грабля у стека на срезе одна, но о неё спотыкаются регулярно: s[len(s)-1] на пустом срезе паникует с index out of range. Проверка len(s) == 0 перед снятием обязательна, специального значения вроде nil срез не вернёт. У канала своя грабля: чтение из закрытого канала возвращает нулевое значение, а не ошибку, поэтому пишут v, ok := <-ch и смотрят на ok.

Стек и очередь легко написать самому — кода в них на десять строк, — и в JavaScript отдельных классов для них нет: обе структуры делают из массива, а очередь получше берут из пакета.

Стек это массив как есть: push кладёт на вершину, pop снимает, a.at(-1) смотрит. Всё за O(1) амортизированно, переезд в больший массив редкий. Очередь на массиве тоже пишут в две строки: push в хвост, shift из головы, и вот здесь грабля: shift сдвигает все элементы и стоит O(N). На десятке задач это незаметно, на очереди в сто тысяч событий цикл «пока есть, shift» становится квадратичным. Движок V8 умеет ускорять shift на небольших массивах, но полагаться на это нельзя.

Честную очередь делают одним из двух способов: держат индекс головы и не удаляют элементы вовсе, только изредка обрезая массив, либо пишут кольцо, как в разделе про циклическую очередь. В проектах обычно берут готовый пакет denque, внутри у которого то же кольцо с ростом.

Один массив закрывает обе структуры — разница только в том, с какого конца забирать. Она видна на одних и тех же данных:

живой пример

const stack = [];
const queue = [];
for (const task of ["первая", "вторая", "третья"]) {
  stack.push(task);
  queue.push(task);
}
console.log("стек:    " + stack.pop() + ", " + stack.pop());
console.log("очередь: " + queue.shift() + ", " + queue.shift());

Три одинаковых задачи, один и тот же массив — но стек начинает с последней, а очередь с первой.

На вопрос про переполнение массив не отвечает: он растёт, пока не кончится память процесса. Ограниченную очередь с отказом или вытеснением старого пишут руками поверх кольца: offer возвращает false, когда размер дошёл до ёмкости. «Подождать места» в однопоточном JavaScript значит вернуть промис, который разрешится, когда кто-то заберёт элемент; так устроены очереди задач вроде p-queue.

Приоритетной очереди в языке нет: пишут двоичную кучу в массиве, разобрано в статье про кучу, или берут пакет heap-js. Одна деталь ломает ожидания и там: «выше приоритет» в большинстве реализаций значит меньше по функции сравнения, и чтобы первым выходил самый большой, сравнение переворачивают.

Про потоки. Внутри одного потока JavaScript гонок нет: обработчики событий выполняются по очереди, и массив-очередь между таймером, который кладёт, и обработчиком, который забирает, безопасен без замков. Между воркерами (worker_threads) память не общая, туда передают сообщения через postMessage, а общий SharedArrayBuffer с Atomics это редкий инструмент для особых случаев.

Грабля у стека и очереди на массиве одна, но о неё спотыкаются регулярно: pop и shift на пустом массиве возвращают undefined, а не бросают исключение. Цикл «пока pop() что-то возвращает» тихо останавливается раньше времени, если в стеке лежит undefined или null; проверяют length, а не значение.

Стек и очередь легко написать самому — кода в них на десять строк, — но в стандартной библиотеке они есть. Выбирать приходится между тремя вещами, и у каждой своя роль.

Стек это обычный list: append кладёт на вершину, pop() без аргумента снимает её, a[-1] смотрит. Всё за O(1) амортизированно. А вот очередь из списка делать нельзя: pop(0) сдвигает все элементы за O(N), и цикл обработки становится квадратичным.

Правильная очередь — collections.deque. Это дек из предыдущего раздела, но внутри не кольцо, а двусвязный список блоков по 64 элемента: добавление и удаление с обоих концов за O(1) без переезда всего массива, а память растёт и освобождается блоками. append и pop работают справа, appendleft и popleft слева; доступ по индексу в середину O(N), для него дек не предназначен.

У deque есть ответ на вопрос про переполнение, причём встроенный: deque(maxlen=1000) при добавлении в полный дек молча выбрасывает элемент с противоположного конца. Это стратегия «вытеснить старое» из раздела про очередь: последняя тысяча событий журнала, скользящее окно. Стратегии «отказать» и «подождать» живут в другом модуле: queue.Queue(maxsize=100) с put_nowait, который бросает queue.Full, и с put, который ждёт места.

Один класс закрывает обе структуры — дек их обобщает. Разница видна на одних и тех же данных:

живой пример

from collections import deque

stack = deque()
queue = deque()
for task in ("первая", "вторая", "третья"):
    stack.append(task)
    queue.append(task)
print("стек:    " + stack.pop() + ", " + stack.pop())
print("очередь: " + queue.popleft() + ", " + queue.popleft())

Три одинаковых задачи, один и тот же класс — но стек начинает с последней, а очередь с первой.

Приоритетная очередь живёт отдельно: модуль heapq, функции heappush и heappop над обычным списком, построенные на куче. Одна деталь ломает ожидания: «выше приоритет» здесь значит меньше по порядку сравнения, куча минимальная, и чтобы первым выходил самый большой, приоритет кладут со знаком минус или заворачивают в кортеж (-priority, item).

Про потоки. Отдельные append и popleft у deque атомарны благодаря глобальной блокировке интерпретатора, но составная операция «проверить, что не пуст, и забрать» уже нет: между проверкой и снятием другой поток успевает забрать последний элемент. Очередь задач между потоками это queue.Queue: внутри тот же deque, но с замком и условными переменными, get ждёт элемент, put ждёт место, а join и task_done считают завершённые задачи. Для кода на asyncio есть asyncio.Queue с теми же операциями через await.

Грабля у deque одна, но о неё спотыкаются регулярно: pop и popleft на пустом деке бросают IndexError, как и list.pop(). Специального значения вроде None они не возвращают, поэтому цикл «пока есть работа» пишут через while queue:, а в queue.Queue для этого есть get_nowait с исключением queue.Empty.

• В Java обе структуры закрывает один ArrayDeque; Stack не берут — он синхронизирован и перебирается снизу вверх, против LIFO.
• add/remove/element бросают исключение на границе, offer/poll/peek возвращают false или null; ArrayDeque не для потоков, межпоточная очередь это BlockingQueue.

• В Go обе структуры делают из среза: стек это append и s[:len(s)-1], очередь либо срез с индексом головы или кольцо (q[1:] держит память), либо канал.
• Канал с буфером и есть ограниченная очередь с замком: отправка в полный ждёт, select с default отказывает; срез не для горутин, а s[len(s)-1] на пустом срезе паникует.

• В JavaScript стек это массив с push/pop; очередь через shift стоит O(N), честная очередь это индекс головы, кольцо или пакет denque.
• pop и shift на пустом массиве возвращают undefined, а не бросают; переполнение массив не ограничивает, отказ и ожидание пишут руками поверх кольца и промисов.

• В Python стек это list с append/pop(), очередь только collections.deque с popleft; list.pop(0) это O(N).
• deque(maxlen=n) вытесняет старое молча, queue.Queue(maxsize) отказывает через put_nowait или ждёт в put; pop на пустом деке бросает IndexError, межпоточная очередь это queue.Queue.