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 is an abstract data type for a pending ordered collection. Enqueue adds an element after all currently pending elements; dequeue removes the earliest pending element; peek observes that element without removal. The essential contract is first in, first out among elements still present. How elements are stored—linked nodes, a circular array, or another representation—is not part of that abstract identity.[1][2]
This is narrower than every programming API named Queue. Cornell explicitly notes that Java's Queue interface need not guarantee FIFO, since some implementations order by priority. It is also distinct from the live Queueing prime, which concerns arrival, waiting and service processes rather than one collection's operation trace.[1]
The frozen candidate titled Queue (data structure) redirects to Queue (abstract data type). Both candidate IDs remain in provenance, but an implementation is an instance of the contract only if its operations preserve FIFO.
Structural Signature¶
Sig role-phrases:
- Pending ordered collection: retained elements have an insertion order. Removing all state would leave no earliest pending item to choose.
- Rear insertion: enqueue appends after all already pending elements; inserting in front would violate the stated trace.
- Front access/removal: dequeue and peek select the earliest still pending element, not the latest or highest-priority one.
- Representation-independent invariant: equivalent operation sequences produce the same returned order whether storage is linked or circular. A physical array index may wrap while logical age order remains.
- Edge-state policy: empty removal and, for bounded realizations, full-buffer behavior require API choices; these refine operations but do not replace FIFO.[1][2][3]
Condensed: ordered pending state + append at rear + remove oldest at front → FIFO trace contract.
What It Is Not¶
- Not a stack. A stack removes the most recently inserted pending item.
- Not a priority queue. A priority queue can remove a later urgent item before an earlier one.
- Not a circular buffer itself. Modulo-N indices are one implementation, not the abstract queue.[3]
- Not a physical line or queueing theory. Waiting people may skip, abandon or be served by priority; the ADT specifies an operation rule.
- Not fairness for all actors. FIFO orders items already admitted, not which producer enqueues first, how long service takes after dequeue, or what happens to an item rejected by a full buffer.
- Not every Java Queue. The interface name does not universally promise FIFO.[1]
Scope of Application¶
In breadth-first search, newly discovered vertices enter a frontier at the rear and the earliest discovered pending vertex is expanded first. MIT's lecture states an invariant relating queue order to distance layers, so FIFO contributes to correctness for unweighted graph traversal. A LIFO stack would change the exploration order, not merely its storage.[4]
In an N-character producer–consumer buffer, MIT describes read and write indices moving modulo N through an array. The physical index wraps from the last slot to the first, but logical read order remains the order of admitted characters. Finite capacity requires coordination at full and empty states; FIFO alone does not prescribe block, reject, drop or overwrite.[3]
Cornell's functional-structures lecture presents a queue interface while discussing representation abstraction. A linked implementation, circular array and two-stack implementation may have different costs, but represent the same ADT only when they satisfy the same operation semantics.[2][1]
Clarity¶
The contract separates what a client may rely on from how an implementer arranges memory. “It is a circular buffer” answers the latter. “Every dequeue returns the oldest pending insertion” answers the former. The distinction prevents a false inference from an API name: Java's Queue interface may hold a priority queue, so a client requiring FIFO must inspect the actual contract.[1]
For the trace enqueue(A), enqueue(B), dequeue(), enqueue(C), dequeue(), the two returns must be A then B, regardless of physical array indices. Returning C second exits this narrow identity unless an explicit cancellation operation changed which elements remained pending.
Manages Complexity¶
The ADT hides representation state behind a few operations and one ordering invariant. An algorithm can prove that its frontier is processed in discovery order without knowing whether a circular array or linked list stores it. A hardware designer can reason about wraparound while a consumer reasons about character order. The abstraction intentionally omits throughput, memory bounds, concurrency and overflow handling; those are real implementation obligations, not consequences of FIFO.
Abstract Reasoning¶
Model the logical queue as a sequence Q. Enqueue(x) appends x at its end; dequeue on nonempty Q returns its first element and leaves the remaining sequence. This trace rule proves ordering claims across representations. In BFS it supports the distance-layer invariant only together with the algorithm's vertex-discovery rule. In a bounded buffer it proves admitted-item order but says nothing about an item rejected before admission.[4][3]
To test an implementation, use interleaved insertion/removal, physical wraparound, empty and full transitions. Compare returned traces with the abstract sequence rule. Internal index values need not match a canonical layout.
Knowledge Transfer¶
The FIFO contract transfers literally from graph frontiers to producer–consumer buffers and across storage methods. The contents differ—vertices versus characters—but the operation trace is the same. It does not turn every waiting system into this ADT: a printer scheduler that reorders by urgency and a physical service line allowing abandonment have different transitions. The broader Abstract Data Type prime can carry the interface/implementation distinction; this entry carries the specific FIFO rule.
Examples¶
Breadth-first search frontier¶
MIT's BFS lecture puts newly discovered adjacent vertices at the end of a FIFO queue and removes the front vertex for expansion. The ordering invariant links that frontier to distance layers, making FIFO part of the correctness argument. This is a precise algorithm trace, not a claim that any work queue yields shortest paths.[4]
Mapped back: pending discovered vertices are the ordered collection; discovery enqueues each at the rear; expansion dequeues the oldest frontier vertex; any storage must preserve that order; termination occurs when the frontier is empty, with no bounded-overflow rule in the cited pseudocode.
N-character producer–consumer buffer¶
MIT's computation-structures material describes an N-character FIFO buffer with an array and read/write indices advancing modulo N. This lets a producer and consumer run at different rates without synchronous handoff for each character. Array slot order cycles, but admitted characters are read in entry order. A full buffer still requires a separately specified coordination policy.[3]
Mapped back: unread characters form the pending collection; write-index admission enqueues at the rear; read-index consumption dequeues at the front; modulo wraparound changes storage positions but not FIFO; bounded capacity adds full/empty conditions beyond the core contract.
Java interface boundary¶
Cornell notes that Java's Queue interface does not itself require FIFO. A priority implementation may satisfy that interface while returning a later element first. This is a negative comparison, not a third positive case of this narrow FIFO ADT.[1]
Structural Tensions¶
Abstract contract versus concrete performance. Specifying only FIFO makes clients and proofs insensitive to storage choice. It leaves operation cost, memory, concurrency and capacity unresolved. A circular array bounds storage but introduces full/empty and synchronization duties; linked storage can grow differently but incurs allocation overhead. Diagnostic: is the question about returned order or about latency, memory and overflow under a workload?[2][3]
Arrival order versus other service objectives. FIFO ensures an admitted earlier item is selected before a later admitted item. Priority service may be preferable for urgent work, while multi-producer fairness may need rules before items reach the queue. Letting a later urgent item overtake an earlier one exits this narrow ADT; insisting on FIFO may delay urgent work. Diagnostic: must the next selection be oldest pending or most urgent?[1]
Structural–Framed Character¶
The FIFO queue is strongly structural: operation traces decide compliance without aesthetic judgment. Human choices define the API and workloads, but once the contract is fixed its invariant does not depend on institutional authority. Programming-language institutions may use “Queue” for broader interfaces, showing that the label alone is not proof of FIFO. The vocabulary travels literally between BFS and hardware buffering when operation semantics agree; importing it to a service system with overtaking is analogy or a different policy. Recognition means checking traces, not recognizing a line-like picture. Its character: a formal behavioral structure whose fairness and performance effects remain contingent on admission, scheduling and implementation.
Structural Core vs. Domain Accent¶
The skeletal relation is a behavior-first interface specified independently of representation, with the live Abstract Data Type prime as proposed parent. The domain-bound mechanism is a computer-science collection state and its FIFO enqueue/dequeue operations. The named queue does not clear the prime bar: replacing elements and operations with people in a physical line or tasks in a stochastic service system introduces abandonment, priority and completion mechanisms. Queueing may be a related prime, but it is not this ADT's necessary genus. The portable interface/implementation skeleton belongs to Abstract Data Type, not to the named FIFO child as a cross-domain prime.
Instantiates / Related Primes¶
This entry is a kind of Abstract Data Type.
The live Abstract Data Type is the strict genus: this FIFO operation contract specializes behavior-first specification while leaving storage substitutable. Stacks and sets are ADTs without FIFO. Queueing concerns arrival and service dynamics, not this container contract, and an API merely named Queue need not qualify.
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.Every admitted queue has enqueue, dequeue and peek behavior constrained by FIFO while allowing multiple storage realizations. Stacks and sets are abstract data types without the FIFO differentia; an API merely named Queue need not satisfy this child identity.
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
Not to Be Confused With¶
Stack: LIFO. Priority queue: removes by priority rather than necessarily age. Circular buffer: one finite storage realization that can implement FIFO. Queueing process: arrivals, waits and service over time, possibly with non-FIFO policies. Java Queue interface: a broader API label. Deque: permits operations at both ends and behaves as this queue only under restricted use.[1]
References¶
[1] Cornell CS2110, abstract data types reference, Queue section, FIFO operations, implementations and Java-interface caveat. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i
[2] Cornell CS312, functional structures and abstractions lecture, queue signature and front/rear semantics. registry ↩a ↩b ↩c ↩d
[3] MIT 6.004, Computation Structures annotated slides 19.1, N-character FIFO circular buffer. registry ↩a ↩b ↩c ↩d ↩e ↩f
[4] MIT 6.046J, Shortest Paths I lecture, BFS FIFO frontier and distance invariant. registry ↩a ↩b ↩c