queue
A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
In more detail
Items are enqueued at the back and dequeued from the front. In Python, use collections.deque with append and popleft, both O(1); a list with pop(0) is O(n) per removal. Queues drive breadth-first search, job scheduling and producer-consumer pipelines.
Related terms
- FIFO — First in, first out: the ordering rule of a queue, where the oldest item is always the next to leave.
- enqueue and dequeue — The two basic queue operations: enqueue adds an item at the back and dequeue removes the item at the front.
- deque — A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
- stack — A collection where the last item added is the first one removed, like a pile of plates.
- breadth-first search — A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers