A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. This means that the element added first is the first to be removed, similar to a queue of people waiting in line. Queues are fundamental to computer science and are widely used in various applications, ranging from CPU scheduling to data streaming.
- FIFO Order: The first element added to the queue is the first to be removed.
- Two Primary Operations:
- Enqueue: Adds an element to the rear (back) of the queue.
- Dequeue: Removes an element from the front of the queue.
- Front and Rear Pointers: Queues maintain a pointer to the front (head) and rear (tail) elements.
- Bounded or Unbounded: Queues can have a fixed maximum size (bounded queue) or can dynamically grow (unbounded queue).
- Thread-Safety Considerations: In multi-threaded environments, proper synchronization mechanisms like mutexes and semaphores must be used to prevent race conditions.
A basic queue that follows FIFO and supports standard enqueue and dequeue operations.
A queue where the last position is connected back to the first, allowing efficient memory utilization. It avoids shifting elements when dequeuing, unlike a simple queue.
A queue where elements are dequeued based on priority instead of the FIFO order. Priority is typically determined by a comparator function.
| Operation | Linked List Implementation | Array Implementation |
|---|---|---|
| Enqueue | O(1) | O(1) (if space available) |
| Dequeue | O(1) | O(1) (if no shifting needed) |
| Peek (Front) | O(1) | O(1) |
| Search | O(n) | O(n) |
| Size | O(1) | O(1) |
- Uses a fixed-size array.
- Enqueue at the rear, dequeue from the front.
- May lead to inefficient memory usage due to shifting elements.
- Uses dynamically allocated nodes with pointers.
- No fixed size, allowing dynamic growth.
- Efficient enqueue and dequeue operations without shifting elements.
- Process scheduling (Round Robin scheduling uses a queue).
- Job scheduling in multi-tasking environments.
- Data packets in routers are processed using queues.
- Message queues in distributed systems ensure proper communication flow.
- Breadth-First Search (BFS): Uses a queue to traverse graphs level by level.
- Tree Traversals: Level-order traversal of a tree uses a queue.
- Producer-Consumer problems use queues to handle data between threads.
- Message queues manage communication between processes.
- Printer queues ensure documents are printed in the order they were submitted.
- CPU task scheduling ensures fair execution.
- Used in event-driven simulations where entities are processed in order.
- Example: Airport check-in systems manage passengers in a queue.
A queue can be implemented using two stacks:
- Enqueue operation pushes elements onto one stack.
- Dequeue operation transfers elements from one stack to another to maintain FIFO order.
- Implemented using atomic operations to improve performance in concurrent environments.
- Used in high-performance systems where blocking threads is inefficient.
- Implemented using binary heaps or balanced trees.
- Provides O(log n) complexity for insertions and deletions.
Queues are a fundamental data structure in computer science with diverse applications in real-world systems. Understanding their properties, implementation techniques, and optimizations is crucial for designing efficient algorithms and software systems. Choosing the right type of queue based on the problem requirements can significantly impact performance and resource utilization.