Queue functions
Each snippet below is something you will reach for while solving queue problems. Skim the short description, then copy the patterns for common situations.
Prefer Overview for how queues work, and Problems for practice once problems are linked.
Array as a queue
push and shift work, but shift is O(n). Prefer an index pointer on hot paths.
push() + shift()
Enqueue at the end, dequeue from the front. Fine for small queues; shift slides every element.
const q: number[] = [];
// ——— enqueue (back) ———
q.push(10);
q.push(20); // [10, 20]
// ——— dequeue (front) ———
const next = q.shift(); // 10; q is [20]
// ——— caveat: shift is O(n) — everyone slides left ———
while (q.length > 0) {
const v = q.shift()!;
// use v
}unshift() + pop()
The other orientation — avoid for queues; unshift also slides the whole array.
const q: number[] = [];
// ——— enqueue at front (slow) ———
q.unshift(1);
q.unshift(2); // [2, 1]
// ——— dequeue from back ———
const next = q.pop(); // 1
// Prefer push + head index instead of unshift.Head index (amortized O(1))
Keep a read pointer so dequeue never shifts. Compact when the unused prefix grows.
head pointer
Enqueue with push. Dequeue by reading q[head] and bumping head — no slide.
const q: number[] = [];
let head = 0;
function enqueue(v: number): void {
q.push(v);
}
function dequeue(): number | undefined {
if (head >= q.length) return undefined;
const v = q[head];
head += 1;
// optional: compact when head is large
if (head > 50 && head * 2 > q.length) {
q.splice(0, head);
head = 0;
}
return v;
}
function isEmpty(): boolean {
return head >= q.length;
}size via indices
Live length is the gap between the write end and the head.
function size(q: number[], head: number): number {
return q.length - head;
}
function peek(q: number[], head: number): number | undefined {
return head < q.length ? q[head] : undefined;
}Queue with two stacks
Amortized O(1) enqueue and dequeue when you flip the inbox into the outbox.
inbox / outbox
Push into in. On dequeue, if out is empty, pour in into out, then pop out.
const inn: number[] = [];
const out: number[] = [];
function enqueue(v: number): void {
inn.push(v);
}
function dequeue(): number | undefined {
if (out.length === 0) {
while (inn.length > 0) out.push(inn.pop()!);
}
return out.pop();
}
function peek(): number | undefined {
if (out.length === 0) {
while (inn.length > 0) out.push(inn.pop()!);
}
return out.at(-1);
}why it works
Pouring reverses twice overall, so the oldest value sits on top of out.
// enqueue 1, 2, 3 → inn = [1, 2, 3]
// first dequeue pours → out = [3, 2, 1], pop → 1
// next dequeue pops 2 without pouring againCircular buffer
Fixed capacity. Head and tail walk with modulo so empty slots after dequeue can be reused.
ring enqueue / dequeue
Store values in a fixed array; wrap indices with % capacity.
class CircularQueue<T> {
private buf: (T | undefined)[];
private head = 0;
private tail = 0;
private len = 0;
constructor(private capacity: number) {
this.buf = new Array(capacity);
}
enqueue(v: T): boolean {
if (this.len === this.capacity) return false;
this.buf[this.tail] = v;
this.tail = (this.tail + 1) % this.capacity;
this.len += 1;
return true;
}
dequeue(): T | undefined {
if (this.len === 0) return undefined;
const v = this.buf[this.head];
this.buf[this.head] = undefined;
this.head = (this.head + 1) % this.capacity;
this.len -= 1;
return v;
}
get size(): number {
return this.len;
}
}full vs empty
Track size (or leave one slot empty) so head === tail is not ambiguous.
// With an explicit size counter:
// empty → size === 0
// full → size === capacity
// head === tail alone is not enough when size is not stored.Queue class
A small typed wrapper keeps enqueue, dequeue, peek, and isEmpty in one place.
Queue<T>
Linked-style API over an array with a head index.
class Queue<T> {
private items: T[] = [];
private head = 0;
enqueue(value: T): void {
this.items.push(value);
}
dequeue(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.items[this.head];
this.head += 1;
if (this.head > 32 && this.head * 2 > this.items.length) {
this.items = this.items.slice(this.head);
this.head = 0;
}
return value;
}
peek(): T | undefined {
return this.isEmpty() ? undefined : this.items[this.head];
}
isEmpty(): boolean {
return this.head >= this.items.length;
}
get size(): number {
return this.items.length - this.head;
}
}BFS and level order
Queues are the backbone of breadth-first search — visit neighbors in the order you discover them.
graph BFS
Seed the queue with the start node. Dequeue, enqueue unseen neighbors.
function bfs(start: number, adj: number[][]): number[] {
const seen = new Set<number>([start]);
const q = [start];
const order: number[] = [];
let head = 0;
while (head < q.length) {
const node = q[head++]!;
order.push(node);
for (const next of adj[node] ?? []) {
if (seen.has(next)) continue;
seen.add(next);
q.push(next);
}
}
return order;
}level-order tree
Capture queue size at the start of each round to group one level at a time.
type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const q: TreeNode[] = [root];
const levels: number[][] = [];
let head = 0;
while (head < q.length) {
const size = q.length - head;
const level: number[] = [];
for (let i = 0; i < size; i++) {
const node = q[head++]!;
level.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
levels.push(level);
}
return levels;
}Deque patterns
When both ends matter — sliding-window maximum, palindrome checks, dual stacks.
two-ended indices
Track left and right ends over a buffer when you need push/pop on both sides.
class Deque<T> {
private buf: T[] = [];
private left = 0;
pushBack(v: T): void {
this.buf.push(v);
}
pushFront(v: T): void {
if (this.left === 0) this.buf.unshift(v);
else {
this.left -= 1;
this.buf[this.left] = v;
}
}
popFront(): T | undefined {
if (this.isEmpty()) return undefined;
const v = this.buf[this.left];
this.left += 1;
return v;
}
popBack(): T | undefined {
if (this.isEmpty()) return undefined;
return this.buf.pop();
}
isEmpty(): boolean {
return this.left >= this.buf.length;
}
}sliding-window max sketch
Keep indices of useful candidates in a deque — front is always the max in window.
function maxSlidingWindow(nums: number[], k: number): number[] {
const dq: number[] = []; // indices, values decreasing
const out: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length && dq[0]! <= i - k) dq.shift();
while (dq.length && nums[dq.at(-1)!]! <= nums[i]!) dq.pop();
dq.push(i);
if (i >= k - 1) out.push(nums[dq[0]!]!);
}
return out;
}