A queue is a first-in, first-out structure. The earliest added item is the first item removed.
Queues are important because breadth-first search depends on processing discovered items in the order they were discovered.
Core Idea
The main operations are enqueue and dequeue. In Python algorithm code, collections.deque is the standard tool because it supports efficient appends and pops at both ends.
A queue keeps work fair by not letting newer items jump ahead of older items.
Python Example
from collections import deque
queue = deque()
queue.append("first")
queue.append("second")
item = queue.popleft()After popleft, item is "first".
Common Confusions
A Python list can append at the end, but removing from the front with pop(0) is slow because the remaining elements must shift.
A queue is different from a priority queue. A normal queue removes by arrival order. A priority queue removes by priority.
When To Use It
Use a queue when the algorithm must process work in discovery order, especially in BFS, level-order traversal, simulations, and shortest paths where all edges have equal cost.