Queue

    By
    Himanshu Tyagi
    -
    0
    4
    « Back to Glossary Index

    What is a Queue?

    A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle—the first element inserted is the first to be removed.

    The queue resembles a line at a ticket counter: elements join at the rear, wait their turn, and leave from the front. This ordering makes queues suitable for scenarios where items must be processed in the order they arrive.

    How Queues Work

    Queues maintain two pointers: front and rear. The front points to the element ready to be served—the element that will be removed next. The rear points to the most recently added element. The basic queue operations are:

    • Enqueue: Insert an element at the rear. If the queue is full, an overflow error occurs.
    • Dequeue: Remove the element at the front. If the queue is empty, an underflow error occurs.
    • Peek/Front: Return the front element without removing it.
    • Size: Return the number of elements currently in the queue.
    • isEmpty/isFull: Check whether the queue is empty or full.

    For well-implemented queues, insertion (enqueue) and removal (dequeue) operations run in constant time, or O(1).

    Types of Queues

    While the simple linear queue implements FIFO strictly, variations adapt the basic structure to different needs:

    • Circular Queue: Connects the last position back to the first, forming a circle. Circular queues utilize unused memory in a linear queue and are used in memory management, computer-controlled traffic lights, and operating system process scheduling.
    • Deque (Double-Ended Queue): This type of queue allows insertion and deletion at both ends. It also supports stack and queue operations, making it useful for problems requiring flexibility at both ends.
    • Priority Queue: This queue associates each element with a priority and serves elements based on priority rather than arrival order. The smallest element is removed first; in a descending priority queue, the largest element is removed first.
    • Input-Restricted Queue: Inserts at the rear only but allows deletions from both ends.
    • Output-Restricted Queue: Allows insertions from both ends but deletions from the front only.
    • Concurrent Queue: Supports safe access by multiple threads, making it suitable for multi-threaded applications like web servers.

    Queue Use Cases and Examples

    Queues appear in many algorithms and systems because they enforce fairness and order:

    • Operating System Scheduling: CPU and disk scheduling algorithms maintain queues of processes or tasks ready for execution. Processes are placed in a circular queue in a round-robin scheduler to ensure equitable CPU time.
    • Asynchronous Data Transfer: When data is produced and consumed at different rates, a queue acts as a buffer between processes or devices—for example, I/O buffers or printer queues.
    • Breadth-First Search (BFS): BFS traverses a graph level by level using a queue to keep track of nodes to visit next.
    • Level Order Traversal of Trees: Trees can be traversed level by level by enqueuing child nodes and visiting them in FIFO order.
    • Message and Task Queues: In web servers and microservices, requests are placed in a queue for asynchronous processing.
    • Print and Network Queues: Print jobs and network packets wait in queues until the printer or network interface is ready to process them.

    Queue Summary Table

    Data Structure Key Characteristics and Uses
    Simple Queue Strict FIFO; insert at rear and remove at front; used for resource sharing and scheduling tasks.
    Circular Queue Connects last position to first; efficient memory use and constant-time operations; used in traffic systems and memory management.
    Deque Insert and delete at both ends; supports both stack and queue operations.
    Priority Queue Serves the highest/lowest priority element first, not based on arrival order; used in scheduling and networking.
    Input-Restricted Queue Adds at the rear, removes from either end; useful when occasionally removing recently added data is necessary.
    Output-Restricted Queue It adds at both ends and removes only from the front; it is used when the insertion order matters, but removal must follow FIFO.
    Concurrent Queue It supports safe access by multiple threads and is used in multi-threaded applications like web servers.
    Related Concepts

    Queues are often compared with stacks, which follow a Last-In, First-Out (LIFO) order. While both are linear structures, queues serve items in the order they arrive, whereas stacks remove the most recently added item.

    Deques combine both behaviors. Queues also complement lists and arrays for sequential storage and appear in algorithms like Dijkstra’s shortest path (priority queue), Huffman coding, and producer–consumer problems.

    Understanding queues and their variants equips students to design algorithms that process data streams and tasks in order, while supporting fairness and concurrency.

    Summary

    A queue is a simple yet powerful data structure that processes elements in the order they arrive. By maintaining front and rear pointers and supporting enqueue, dequeue, and related operations, queues provide a fair and efficient way to manage tasks, requests, and data streams.

    Variants such as circular, deques, and priority queues adapt the basic FIFO principle to different needs, from memory management and scheduling to real-time systems. Mastery of queues and their operations is essential for understanding algorithms and building robust, scalable applications.

    « Back to Glossary Index