Queue ADT
Definition
A Queue is a linear data structure that processes elements in a First-In, First-Out (FIFO) manner. The element added earliest is removed first, similar to a line in a store or tickets at a booth. Key operations occur at both ends: insertion (enqueue) at the rear and removal (dequeue) from the front.
Queue Operations
| Operation | Description |
|---|---|
| enqueue(x) | Adds element x to the rear of the queue. |
| dequeue() | Removes and returns the front element. |
| front()/peek() | Views the front element without removal. |
| isEmpty() | Checks if the queue has no elements. |
| isFull() | Checks if capacity is reached (fixed size). |
| size() | Returns the number of items in the queue. |
-
Sequence: enqueue(5), enqueue(3), dequeue() → returns 5 (frontmost), queue becomes .
Circular Queues
A Circular Queue is a queue in which the last position is connected back to the first to make a circle, overcoming the limitation of unused space present in array-based queues (due to front and rear pointer movement). When rear reaches the end, it wraps around to the front, provided there’s available space.
Characteristics:
-
Efficient use of space.
-
Avoids the "false full" scenario of linear array queues.
-
Commonly implemented with modulo arithmetic to update front and rear indices.
DeQueue (Double-Ended Queue)
A DeQueue (Double-Ended Queue) allows insertion and deletion at both the front and rear ends.
Types:
-
Input-restricted: insertion at only one end, deletion at both ends.
-
Output-restricted: deletion at only one end, insertion at both ends.
Operations:
-
insertFront(x): Insert element at the front.
-
insertRear(x): Insert element at the rear.
-
deleteFront(): Remove element from the front.
-
deleteRear(): Remove element from the rear.
DeQueues are versatile, supporting the features of both stacks and queues.
Applications of Queues
Queues, with their FIFO or flexible access (in Dequeues), are integral to various computing and real-world processes:
1. Task Scheduling & Resource Management
-
Print queues: Print jobs are sent in order and handled one by one.
-
CPU scheduling: Operating systems schedule tasks/jobs (process scheduling) using queues for fair resource allocation.
-
Disk scheduling: Queue structure manages access to disk drives.
2. Communication & Buffering
-
Network packet handling: Routers maintain queues for data packets awaiting transmission or routing.
-
IO Buffers: Data is queued in buffers before being processed by slower devices like printers or hard drives.
3. Customer Service Systems
-
Call center support: Customer calls are queued and addressed in the order received.
-
Ticket counters & banks: Service is rendered to customers based on their arrival order.
4. Simulation & Modeling
-
Traffic management: Simulate traffic flow and congestion at signals or junctions.
-
Logistics: Manage loading/unloading in scenarios like airports, warehouses.
5. Data Stream & Multithreading
-
Producer-consumer problems: In concurrent programming, queues buffer data between producers (generating data) and consumers (processing data).
-
Event handling: Event queues store user/system events until processed by applications.
Summary Table
| Queue Variant | Key Feature | Common Application Examples |
|---|---|---|
| Standard Queue | FIFO insert & remove | Print jobs, OS task scheduling |
| Circular Queue | Efficient space reuse (wrap-around) | Resource buffer pools, round-robin tasks |
| DeQueue | Insert/delete at both ends (flexible) | Palindrome checks, undo-redo, caching |
Join the conversation