What is a Queue? FIFO Data Structure Explained with Examples
💡 Concept Name
Queue — A fundamental linear data structure that keeps items in the order they arrive, following the First-In-First-Out (FIFO) rule. The earliest element added is always the first to be removed.
📘 Quick Intro
A queue in programming acts just like a real-world line: people join at the back and are served from the front. In data structures, a queue allows new elements to be added at the rear (enqueue) and removed from the front (dequeue), maintaining a fair and predictable order.
🧠 Analogy / Short Story
Think of boarding a bus. Passengers enter at the end of the line and leave from the front as seats become available. Nobody jumps ahead—everyone’s position is respected, making queues fair and orderly.
🔧 Technical Explanation
- 🔁 FIFO Order: First-In-First-Out—oldest entry leaves first, like tickets at a helpdesk.
- 📥 Enqueue: Operation to add an item at the rear (tail) of the queue.
- 📤 Dequeue: Removes the item at the front (head) of the queue.
- 👀 Peek: Lets you view the front element without removing it, handy for checking what’s next in line.
- 🧩 Implementations: Queues can be built using arrays, linked lists, or optimized as circular queues for better space usage.
- ⚡ Efficiency: Enqueue and dequeue operations are O(1), making queues perfect for fast, ordered processing.
🎯 Purpose & Use Case
- 🖨️ **Print Spoolers:** Documents are printed in the order received.
- 🧑💻 **CPU Scheduling:** Processes are handled one by one, maintaining system fairness.
- 🗂️ **Buffer Management:** Queues smooth out bursts in data streams, like keyboard input or network packets.
- 🌳 **Level-Order Traversal:** Algorithms use queues for traversing trees and graphs layer by layer.
- 🎫 **Ticketing Systems:** Manage customer service tickets or call center requests efficiently.
💻 Real Code Example (C#)
// Simple Queue usage in C#
Queue<string> queue = new Queue<string>();
queue.Enqueue("Alice");
queue.Enqueue("Bob");
Console.WriteLine(queue.Dequeue()); // Output: Alice (first in, first out)
Console.WriteLine(queue.Peek()); // Output: Bob (next in line)
❓ Interview Q&A
Q1: What is a queue?
A: A linear data structure that follows First-In-First-Out (FIFO) principle for insertion and deletion.
Q2: How do enqueue and dequeue operations work in a queue?
A: Enqueue adds an element at the rear, and dequeue removes an element from the front.
Q3: What are the key properties of a queue?
A: FIFO order, fixed or dynamic size, and efficient insertion/deletion at ends.
Q4: What are common implementations of queues?
A: Arrays and linked lists.
Q5: What is the time complexity of enqueue and dequeue?
A: O(1) for both operations.
Q6: Can queues be circular?
A: Yes, circular queues reuse memory efficiently by wrapping around.
Q7: What are real-world applications of queues?
A: CPU scheduling, printer spooling, and buffering.
Q8: What happens if you dequeue from an empty queue?
A: Underflow condition occurs, and no elements can be removed.
Q9: How do you check if a queue is empty?
A: When front and rear pointers are equal or set to a sentinel value.
Q10: What is the difference between a queue and a stack?
A: Queue follows FIFO; stack follows LIFO (Last-In-First-Out).
📝 MCQs
Q1. What order does a queue follow?
- LIFO
- FIFO
- Random
- Priority
Q2. Where are elements added in a queue?
- Front
- Rear
- Middle
- Anywhere
Q3. Where are elements removed from in a queue?
- Rear
- Front
- Middle
- Anywhere
Q4. What is the time complexity of enqueue operation?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q5. What is the time complexity of dequeue operation?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q6. Can queues be implemented using arrays?
- No
- Yes
- Sometimes
- Depends
Q7. What happens when dequeuing from an empty queue?
- Overflow
- Underflow
- Error
- No effect
Q8. Are queues linear or nonlinear?
- Linear
- Nonlinear
- Tree-based
- Graph-based
Q9. What is a real-world use of queues?
- Sorting
- CPU scheduling
- Memory management
- Graph traversal
Q10. Difference between queue and stack?
- LIFO vs FIFO
- FIFO vs LIFO
- Both FIFO
- Both LIFO
💡 Bonus Insight
In .NET, the Queue<T> class from System.Collections.Generic provides a robust, ready-to-use queue implementation. It automatically manages resizing and memory, letting you focus on solving problems instead of building data structures from scratch.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!