Queues
Taking the first of 1,000 values out of a JavaScript array with shift moves the other 999; a ring buffer does the same job in one step.
First in, first out
A queue is a line at a shop counter. People join at the back and are served from the front, so whoever arrived first leaves first. The rule is first in, first out (FIFO). The two operations are enqueue, which adds a value at the back, and dequeue, which removes the value at the front. In MIT's 6.006 notes a queue is the sequence interface limited to insert last(x) and delete first().
Queues are everywhere that work must be handled in arrival order: documents waiting for a printer, key presses waiting for a program, messages waiting for a server. Breadth-first search, from the algorithms course, keeps the squares it still has to visit in a queue, and that is exactly why it explores in rings of equal distance.
The easy way and its hidden cost
In JavaScript the obvious queue is an array: push to enqueue at the back and shift to dequeue from the front. It works, and for short queues it is fine. But look at what shift does. MDN says it "shifts all values to the left by 1", and the ECMAScript specification writes it as a loop that copies element k to position k − 1 for every k. The front of an array is the expensive end, as the first unit showed. Dequeuing from a queue of n values costs 1 read plus n − 1 moves, so a queue of 1,000 values costs 1,000 steps per dequeue. (Engines may use shortcuts inside, but the specification gives no promise.)
If you enqueue 5 values into an empty array and then dequeue all 5, the enqueues cost 5 steps and the dequeues cost 5 + 4 + 3 + 2 + 1 = 15, for 20 in all. Most of that is moving values that are not even being removed.
Do not move the values, move the front
The fix is to stop moving values and instead remember where the front is. Keep an index called head. Dequeue reads the value at head and adds 1 to head; nothing else moves. The catch is that the cells before head are wasted. A ring buffer (circular buffer) reuses them: the array has a fixed number of cells, say 8, and positions wrap round, so the cell after 7 is 0. Store head and size. The next enqueue goes into cell (head + size) mod 8, and a dequeue takes cell head and moves head to (head + 1) mod 8. Both operations are 1 step. The price is a fixed capacity: when size reaches 8 the queue is full, unless you copy everything into a bigger ring as a dynamic array would.
Drag to turn. Scroll or pinch to zoom.
| Queue on n values | Enqueue | Dequeue |
|---|---|---|
| Array with push and shift | 1 (amortized) | 1 read + (n − 1) moves |
| Array with a head index | 1 (amortized) | 1, but front cells are wasted |
| Ring buffer of fixed size | 1, or full | 1 |
Which one should you use? For a queue that never holds more than a few dozen values, push and shift is short and clear, and the moving costs almost nothing. For a queue that thousands of items pass through, such as the squares of a large breadth-first search, a head index or a ring buffer keeps every dequeue at one step, and the difference grows with the length of the line.
| FIFO | First in, first out: values leave in the order they arrived. |
| Enqueue / dequeue | Add at the back / remove from the front. |
| shift | Removes the first array value and moves all the others one cell left. |
| Ring buffer | A fixed array used in a circle: next free cell is (head + size) mod capacity. |
- A queue gives back values in which order?
- First in, first out
- Last in, first out
- Largest first
- Random order
- Enqueue A, B, C. Dequeue once. Enqueue D. Now dequeue until empty. Put those values in order.
- With push and shift, how many steps does one dequeue take on a queue of 4 values (1 read plus moves)?
- Same method, a queue of 1,000 values: how many steps for one dequeue?
- Start with an empty array. Enqueue 5 values with push, then dequeue all 5 with shift. How many steps in total?
- A ring buffer has 8 cells (0 to 7), head = 6 and size = 3. Which cell does the next enqueue use?
- How many steps does a dequeue from a ring buffer take, however many values it holds?
- A fixed ring of 8 cells holds 8 values. What happens on enqueue?
- It overwrites the front value
- The queue is full and the value is refused
- It moves every value left
- It sorts the values
- Which search from the algorithms course keeps its waiting squares in a queue?
- Binary search
- Breadth-first search
- Depth-first search
- Linear search
- In MIT 6.006 terms, a queue uses which two sequence operations?
- insert last and delete last
- insert last and delete first
- insert first and delete first
- get at and set at
- A queue is first in, first out: enqueue at the back, dequeue from the front.
- shift moves every remaining value, so dequeuing from n values costs n steps.
- A head index or a ring buffer makes dequeue 1 step.
- In a ring of size c, the next free cell is (head + size) mod c.
Sources for this course (5)
- 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).
Checked: 2026-10-18