Queue #

FIFO (First In, First Out)

Access at the front and back is $\mathcal{O}(1)$.

Insertion at the back is $\mathcal{O}(1)$, and deletion at the front is $\mathcal{O}(1)$.

Types: Simple Queue, Double-Ended Queue (Deque), Priority Queue

Insertion and deletion at both ends are $\mathcal{O}(1)$.

Arranges elements based on priority, not insertion order.

Typically implemented with a binary heap.

Access to the highest-priority element is $\mathcal{O}(1)$.

Insertion is $\mathcal{O}(\log n)$ due to priority rearrangement.

Deletion of the highest-priority element is $\mathcal{O}(\log n)$ due to priority rearrangement.