Очереди
Если взять первое из 1000 значений массива JavaScript через shift, остальные 999 сдвинутся; кольцевой буфер делает ту же работу за один шаг.
Первым пришёл, первым ушёл
Очередь похожа на очередь к кассе в магазине. Люди встают в конец, а обслуживают их с начала, так что кто пришёл первым, тот первым и уходит. Правило называется «первым пришёл, первым ушёл» (FIFO). Две операции: enqueue (добавить) ставит значение в конец, а dequeue (извлечь) убирает значение из начала. В конспектах MIT 6.006 очередь является интерфейсом последовательности, ограниченным операциями insert last(x) и delete first().
Очереди встречаются везде, где работу нужно выполнять в порядке поступления: документы ждут принтер, нажатия клавиш ждут программу, сообщения ждут сервер. Поиск в ширину из курса об алгоритмах хранит клетки, которые ему ещё нужно посетить, в очереди, и именно поэтому он исследует кольцами равного расстояния.
Простой путь и его скрытая цена
В JavaScript очевидная очередь является массивом: push добавляет в конец, а shift извлекает из начала. Это работает, и для коротких очередей это нормально. Но посмотри, что делает shift. MDN пишет, что он «сдвигает все значения влево на 1», а спецификация ECMAScript записывает его как цикл, который копирует элемент k на позицию k − 1 для каждого k. Начало массива является дорогой стороной, как показал первый урок. Извлечение из очереди из n значений стоит 1 чтение плюс n − 1 сдвигов, так что очередь из 1000 значений стоит 1000 шагов на одно извлечение. (Движки могут внутри использовать хитрости, но спецификация ничего не обещает.)
Если добавить 5 значений в пустой массив, а затем извлечь все 5, добавления стоят 5 шагов, а извлечения 5 + 4 + 3 + 2 + 1 = 15, всего 20. Большая часть этого уходит на сдвиг значений, которые даже не удаляются.
Не двигай значения, двигай начало
Решение: перестать двигать значения и вместо этого помнить, где начало. Храни индекс head. Извлечение читает значение на позиции head и прибавляет к head 1; больше ничего не двигается. Подвох в том, что ячейки перед head пропадают зря. Кольцевой буфер (циклический буфер) использует их снова: в массиве фиксированное число ячеек, скажем 8, и позиции идут по кругу, так что после ячейки 7 идёт 0. Храни head и size. Следующее добавление идёт в ячейку (head + size) mod 8, а извлечение берёт ячейку head и переносит head на (head + 1) mod 8. Обе операции стоят 1 шаг. Плата за это фиксированная ёмкость: когда size доходит до 8, очередь полна, если только не скопировать всё в кольцо побольше, как сделал бы динамический массив.
Перетащи, чтобы повернуть. Колёсико или щипок для масштаба.
| Очередь из n значений | Добавление | Извлечение |
|---|---|---|
| Массив с push и shift | 1 (амортизированно) | 1 чтение + (n − 1) сдвигов |
| Массив с индексом head | 1 (амортизированно) | 1, но ячейки в начале пропадают |
| Кольцевой буфер фиксированного размера | 1 или «полон» | 1 |
Что выбрать? Для очереди, в которой никогда не бывает больше нескольких десятков значений, push и shift коротко и понятно, а сдвиги почти ничего не стоят. Для очереди, через которую проходят тысячи элементов, например клетки большого поиска в ширину, индекс head или кольцевой буфер держат каждое извлечение на одном шаге, и разница растёт с длиной очереди.
| FIFO | Первым пришёл, первым ушёл: значения уходят в порядке поступления. |
| Enqueue / dequeue | Добавить в конец / убрать из начала. |
| shift | Убирает первое значение массива и сдвигает все остальные на ячейку влево. |
| Кольцевой буфер | Фиксированный массив, используемый по кругу: следующая свободная ячейка (head + size) mod ёмкость. |
- В каком порядке очередь возвращает значения?
- Первым пришёл, первым ушёл
- Последним пришёл, первым ушёл
- Сначала наибольшее
- В случайном порядке
- Добавь A, B, C. Извлеки один раз. Добавь D. Теперь извлекай, пока очередь не опустеет. Расставь эти значения по порядку.
- Сколько шагов занимает одно извлечение через push и shift из очереди в 4 значения (1 чтение плюс сдвиги)?
- Тот же способ, очередь из 1000 значений: сколько шагов на одно извлечение?
- Начни с пустого массива. Добавь 5 значений через push, затем извлеки все 5 через shift. Сколько всего шагов?
- В кольцевом буфере 8 ячеек (от 0 до 7), head = 6 и size = 3. Какую ячейку займёт следующее добавление?
- Сколько шагов занимает извлечение из кольцевого буфера, сколько бы в нём ни было значений?
- В фиксированном кольце из 8 ячеек лежит 8 значений. Что будет при добавлении?
- Оно затрёт первое значение
- Очередь полна, и значение не принимается
- Оно сдвинет каждое значение влево
- Оно отсортирует значения
- Какой поиск из курса об алгоритмах хранит ждущие клетки в очереди?
- Двоичный поиск
- Поиск в ширину
- Поиск в глубину
- Линейный поиск
- Какие две операции последовательности использует очередь в терминах MIT 6.006?
- insert last и delete last
- insert last и delete first
- insert first и delete first
- get at и set at
- Очередь работает по правилу «первым пришёл, первым ушёл»: добавление в конец, извлечение из начала.
- shift сдвигает все оставшиеся значения, поэтому извлечение из n значений стоит n шагов.
- Индекс head или кольцевой буфер позволяют извлекать за 1 шаг.
- В кольце размера c следующая свободная ячейка (head + size) mod c.
Источники курса (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Проверено: 2026-10-18