Queue

Data Structures

avgO(1)worstO(1)spaceO(n)

← out

7front

19rear

← in

A queue of 2; 7 is at the front

1 / 12

Code

class Queue {  private items: number[] = [];  private head = 0;  enqueue(value: number) {    this.items.push(value);  }  dequeue() {    if (this.head === this.items.length) throw new Error("Queue is empty");    const value = this.items[this.head];    this.head++;    return value;  }  get size() {    return this.items.length - this.head;  }}

structure Queue  items ← empty list  head ← 0    ▷ index of the front  procedure enqueue(value)    append value at the rear  end procedure  procedure dequeue()    if the queue is empty then error    value ← items[head]    head ← head + 1    ▷ O(1): no shifting    return value  end procedure  function size    return length − head  end functionend structure

Variables

size=2

Counters

enqueues: 0
dequeues: 0

Starting contents2 values

Operations7 / 40

1. enqueue(31)
2. enqueue(4)
3. dequeue()
4. enqueue(56)
5. dequeue()
6. dequeue()
7. enqueue(12)

How it works

First in, first out: enqueue joins at the rear and dequeue leaves from the front. Keeping a moving head index instead of shifting the array makes both operations O(1). Breadth-first search, schedulers and buffers all use queues.

Complexity

Best: O(1)
Average: O(1)
Worst: O(1)
Space: O(n)

Queue

How it works

Complexity

Search algorithms