Queue (FIFO Abstract Data Type)¶
A FIFO queue adds elements at the rear and removes the earliest still-pending element from the front, independent of its storage implementation.
Core Idea¶
A FIFO queue adds each element at the rear and removes the earliest still-pending element from the front. Peek observes that front element without removal. The abstract data type promises operation order, not a particular array, linked list or other storage layout. Cornell notes that Java's broader Queue interface need not itself require FIFO.[^ref-af379fe51320]
Scope of Application¶
Breadth-first search uses a FIFO frontier so earlier discovered vertices are expanded before later distance layers. An MIT producer–consumer character buffer uses read/write indices modulo N to realize FIFO despite array wraparound. Bounded storage must additionally define full/empty behavior; FIFO alone does not say to block or drop.[ref-1a151e19a1fb][ref-2edf6da57b3a]
Clarity¶
Separate the contract from the implementation. A circular buffer stores a queue; a priority queue can have “queue” in its name while returning a later, higher-priority item. The frozen title Queue (data structure) redirects to the ADT page, but both candidate IDs and the distinction remain visible.
Manages Complexity¶
Clients can reason from one trace rule—oldest pending item leaves next—without tracking internal pointers or indices. That simplification does not guarantee throughput, producer fairness or completion order after removal.
Abstract Reasoning¶
For enqueue(A), enqueue(B), dequeue(), enqueue(C), dequeue(), a FIFO queue returns A then B. Run similar interleaved traces to test linked, circular or two-stack implementations. In BFS the rule supports distance-layer ordering together with the graph algorithm's discovery rule.[^ref-1a151e19a1fb]
Knowledge Transfer¶
The same operation contract transfers literally between graph frontiers and character buffers. A physical service line with abandonment or priority overtaking is not automatically this ADT. The live Abstract Data Type is the strict genus; Queueing is a related process concept.
[^ref-af379fe51320]: Cornell, Queue ADT reference. [^ref-1a151e19a1fb]: MIT, BFS FIFO frontier lecture. [^ref-2edf6da57b3a]: MIT, N-character FIFO buffer lecture.
Relationships to Other Abstractions¶
Current abstraction Queue (FIFO Abstract Data Type) Domain-specific
Parents (1) — more general patterns this builds on
-
Queue (FIFO Abstract Data Type) is a kind of Abstract Data Type Prime
The FIFO queue is an abstract data type specified by its operation contract rather than storage implementation.
Hierarchy paths (3) — routes to 2 parentless roots
- Queue (FIFO Abstract Data Type) → Abstract Data Type → Information Hiding → Abstraction
- Queue (FIFO Abstract Data Type) → Abstract Data Type → Information Hiding → Boundary
- Queue (FIFO Abstract Data Type) → Abstract Data Type → Interface → Boundary
Neighborhood in Abstraction Space¶
Queue (FIFO Abstract Data Type) sits in a moderately populated region (58th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Storage & Lookup Data Structures (21 abstractions)
Nearest neighbors
- Self-Organizing List — 0.89
- Queap — 0.86
- Rope (Data Structure) — 0.85
- Sorted Array — 0.84
- Sequence number — 0.84
Computed from structural-signature embeddings · 2026-10-08