Queue ADT Definition and FIFO Principle
What you'll learn: You'll understand what a queue is and why its First-In-First-Out ordering makes it fundamentally different from a stack.
What is a Queue?
A queue is an abstract data type (ADT) that stores a collection of elements with a specific ordering rule: First-In-First-Out (FIFO). This means the first element added to the queue is the first one removed—just like people waiting in line at a grocery store checkout.
Think of it this way: when you stand in line, the person who arrived first gets served first. New arrivals join the back of the line, and service happens from the front. No cutting allowed!
FIFO vs LIFO
This is the opposite of a stack's Last-In-First-Out (LIFO) principle. Remember stacks? The most recent item pushed is the first one popped (like a stack of plates). Queues work differently—they preserve arrival order, ensuring fairness and sequential processing.
Core Properties
A queue maintains two ends:
- Front (or Head): Where elements are removed
- Rear (or Tail): Where elements are added
The queue enforces strict ordering: you can only add at the rear and remove from the front. You cannot access elements in the middle directly—this restriction is what makes it an abstract data type with specific behavior.
Real-World Analogy
- Printer queue: Documents sent to a printer are processed in the order they arrive
- Customer service line: First caller waits the shortest time
- Playlist: Songs play in the order they were added
Key Takeaway: A queue is an ADT that enforces First-In-First-Out ordering, where elements are added at the rear and removed from the front, preserving the sequence in which they arrived.