Queue Data Structure | Operations, Types & More (+Code Examples)

In the world of data structures, Queue stands out as a simple yet powerful tool for managing data in a specific order. Much like a line at a ticket counter or a queue of customers waiting for service, a queue in programming follows the First-In, First-Out (FIFO) principle — the first element added is the first one to be removed.

Queues are essential in scenarios where tasks need to be handled in the order they arrive, such as managing print jobs, scheduling processes in operating systems, or handling requests in web servers. In this article, we will explore the queue data structure, its types, operations, real-world applications, and how it can be implemented in various programming languages.

What Is Queue Data Structure?

A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle — the element that is inserted first will be the first one to be removed. Think of it as a line of people waiting to get tickets at a movie counter: the person who joins the line first gets served first, and the newcomers have to wait at the end of the line.

Key Characteristics Of A Queue:

• Front: The position where elements are removed from the queue.
• Rear (or Back): The position where elements are added to the queue.
• FIFO Order: Elements are processed in the exact sequence they were added.
• Two Main Operations:
• Enqueue: Add an element to the rear (end) of the queue.
• Dequeue: Remove an element from the front (beginning) of the queue.
• Access: Only the front element can be removed, and only the rear end can be used to insert.

Structure Of A Queue Data Structure:

Front --> [10] [20] [30] [40] <-- Rear

            ↑                ↑

         Dequeue          Enqueue

Real-Life Analogy: A Queue At A Ticket Counter 🎟️

Imagine you're waiting in line at a movie theater to buy tickets.

• The person who joins the queue first is the first to buy the ticket (get served).
• Others must wait their turn at the rear of the queue.
• No one can "cut the line" — just like how elements in a queue can’t skip positions.

Types Of Queues In Data Structures

A Queue is a linear structure, but depending on the specific need or optimization, it can take different forms. Let’s explore the most common and useful types of queues:

1. Simple Queue (Linear Queue)

A simple queue follows the First In, First Out (FIFO) principle strictly.

• Insertion happens at the rear end.
• Deletion happens at the front end.

Once the queue becomes full, even if some elements are removed from the front, no new elements can be inserted unless the array is shifted, which can be inefficient.

Example: Ticket counters, print queues.

2. Circular Queue

A circular queue overcomes the limitation of wasted space in a simple queue.

• In a circular queue, the last position is connected back to the first position, making the queue circular in structure.
• When the rear reaches the end of the array and there is space at the beginning (due to previous dequeues), new elements can be inserted at the start.

Example: Buffer management in computer systems, CPU scheduling.

3. Priority Queue

In a priority queue, each element is associated with a priority.

• Elements are dequeued based on their priority, not just the order of insertion.
• Higher priority elements are removed first. If two elements have the same priority, they are served according to their order in the queue (FIFO among same-priority elements).

Example: Emergency room patients in a hospital, task scheduling in operating systems.

4. Double-Ended Queue (Deque)

A deque (pronounced "deck") is a double-ended queue that allows insertion and deletion from both the front and rear ends.

• It can be used as both a queue (FIFO) and a stack (LIFO).
• There are two variations:
• Input-restricted deque: Insertion allowed at only one end, deletion allowed at both ends.
• Output-restricted deque: Deletion allowed at only one end, insertion allowed at both ends.

Example: Palindrome checking, undo operations in text editors.

Summary Table:

Each type of queue is designed to solve particular problems efficiently and is chosen depending on the needs of the application.

Basic Operations In Queue Data Structure

A queue supports several basic operations that allow it to behave according to the First In, First Out (FIFO) rule. These operations manage inserting, removing, checking, and displaying elements. Here are the main operations, along with their algorithm:

1. Enqueue (Insertion) Operation

The enqueue operation is used to insert a new element into the queue at the rear end. When we enqueue, we first check if the queue is full. If it is not full, we increase the rear index and place the new element at that position. If the queue was initially empty, both front and rear are set to the first element.

Algorithm:

1. Check if the queue is full.
2. If not full, increase rear and insert the element at rear.

Example:

void enqueue(int value) {
    if (rear == size - 1) {
        cout << "Queue Overflow!" << endl;
        return;
    }
    if (front == -1) front = 0;
    arr[++rear] = value;
}

2. Dequeue (Deletion) Operation

The dequeue operation is used to remove an element from the front end of the queue. Before dequeuing, we check if the queue is empty. If it is not empty, we remove the element pointed to by front and move the front pointer one step ahead. If the queue becomes empty after the operation, front and rear can be reset.

Algorithm:

1. Check if the queue is empty.
2. If not empty, remove the element at front and move front forward.

Example:

void dequeue() {
    if (front == -1 || front > rear) {
        cout << "Queue Underflow!" << endl;
        return;
    }
    front++;
}

3. Peek / Front Operation

The peek operation is used to view the element at the front of the queue without removing it. Peek checks if the queue is empty. If it is not empty, it returns the element at the front index without modifying the queue. This helps in accessing the next element to be removed.

Algorithm:

1. Check if the queue is empty.
2. If not empty, return the element at front.

Example:

int peek() {
    if (front == -1 || front > rear) {
        cout << "Queue is Empty!" << endl;
        return -1;
    }
    return arr[front];
}

4. isEmpty Operation

The isEmpty operation checks whether the queue contains any elements or not. The queue is empty if the front is -1 (never initialized) or if the front has moved past the rear. This operation is useful to avoid underflow during dequeue or peek operations.

Algorithm: If front == -1 or front > rear, the queue is empty.

Example:

bool isEmpty() {
    return (front == -1 || front > rear);
}

5. isFull Operation

The isFull operation checks whether the queue has reached its maximum capacity. In an array-based queue, the queue is full when the rear index reaches size - 1. If it is full, no more elements can be added unless some are removed (or unless a circular queue is used).

Algorithm: If rear == size - 1, the queue is full.

Example:

bool isFull() {
    return (rear == size - 1);
}

Note: This check is only applicable to static array-based queues, not linked list or STL queues which are dynamically resizable.

Time Complexity Overview

All these operations are constant-time because they either modify a pointer/index or perform a comparison.

Queue Implementation Using Arrays

In a queue, insertion (called enqueue) happens at the rear end, while deletion (called dequeue) happens from the front end. 

• When implementing a queue using arrays, we use two variables: front to track the start of the queue and rear to track the end. Initially, both are set to -1 to indicate that the queue is empty.
• During enqueue, we move the rear pointer forward and insert the element. 
• During dequeue, we move the front pointer forward to remove elements. 
• If the rear reaches the end of the array, the queue is full (overflow), and if the front crosses the rear, the queue is empty (underflow). 
• Arrays provide a simple and efficient way to implement queues when the maximum size is known in advance.

Here is a code example of queue implementation using arrays in C++ programming.

Code Example:

Output: 

10 enqueued to the queue.
20 enqueued to the queue.
30 enqueued to the queue.
Queue elements are: 10 20 30 
10 dequeued from the queue.
Queue elements are: 20 30 
40 enqueued to the queue.
50 enqueued to the queue.
Queue Overflow! Cannot insert 60
Queue elements are: 20 30 40 50 

Explanation:

In the above code example-

1. We start by including the <iostream> header to use input and output streams and declare using namespace std to avoid prefixing std:: everywhere.
2. We define a class named Queue that represents a simple queue using a dynamic array.
3. Inside the class, we declare private data members front, rear, and size to track the queue's state, along with a pointer arr to dynamically allocate memory for the elements.
4. We create a constructor Queue(int capacity) that initializes the size of the queue, allocates memory for arr, and sets both front and rear to -1 to indicate the queue is initially empty.
5. We also provide a destructor ~Queue() to release the dynamically allocated memory when the queue object is destroyed, avoiding memory leaks.
6. For inserting elements, we define an enqueue function. Here, we first check if the queue is full by comparing rear with size - 1. If full, we print an overflow message. Otherwise, if it's the first insertion (front == -1), we set front to 0 and then insert the new value at ++rear.
7. For removing elements, we define a dequeue function. We check if the queue is empty by verifying if front is -1 or front > rear. If so, we print an underflow message. Otherwise, we print the dequeued element and increment front.
8. We define a display function to show all elements from front to rear. If the queue is empty, we inform the user accordingly.
9. In the main() function, we create a Queue object q with a capacity of 5.
10. We enqueue the values 10, 20, and 30 into the queue, and then display the current elements.
11. We dequeue one element, display the updated queue, and then enqueue 40 and 50.
12. When we attempt to enqueue 60, the queue overflows because it has reached its maximum capacity, and we see an overflow message.
13. We display the final state of the queue before ending the program.

Queue Implementation Using Linked List

A queue can also be implemented using a linked list instead of an array. In a linked list-based queue, each element is stored in a node that contains two parts: the data and a pointer to the next node. This approach allows the queue to grow and shrink dynamically without worrying about fixed size or overflow unless the system runs out of memory. 

• We maintain two pointers: front, which points to the first node (for deletion), and rear, which points to the last node (for insertion). 
• To enqueue an element, we create a new node and link it at the end of the list by updating the rear pointer. 
• To dequeue an element, we remove the node pointed to by front and move the front pointer to the next node.
• If front becomes NULL, it means the queue is empty. 
• Linked list-based queues are flexible and efficient for applications where the maximum number of elements is not known in advance.

Here is a code example of queue implementation using a linked list in C++.

Code Example:

Output: 

10 enqueued to the queue.
20 enqueued to the queue.
30 enqueued to the queue.
Queue elements are: 10 20 30 
10 dequeued from the queue.
Queue elements are: 20 30 
20 dequeued from the queue.
30 dequeued from the queue.
Queue Underflow! Cannot dequeue.

Explanation:

In the above code example-

1. We begin by including the <iostream> header for input and output operations and use using namespace std to simplify our code.
2. We define a Node structure that holds two members: an integer data to store the value and a pointer next to link to the next node.
3. We create a Queue class that uses linked nodes instead of an array. Inside the class, we keep two pointers, front and rear, to represent the start and end of the queue.
4. We define a constructor Queue() that initializes both front and rear to nullptr, indicating the queue is initially empty.
5. For inserting elements, we implement the enqueue function. Here, we create a new node, assign it the given value, and set its next pointer to nullptr.
6. If the queue is empty (rear == nullptr), we set both front and rear to point to the new node. Otherwise, we link the new node at the end of the queue by updating rear->next, and then move rear to the new node.
7. For removing elements, we define the dequeue function. If the queue is empty (front == nullptr), we print an underflow message. Otherwise, we print the value at the front, move front to the next node, and delete the old front node.
8. After dequeuing, if the queue becomes empty (front == nullptr), we also set rear to nullptr to correctly update the state.
9. We define a display function to print all elements from front to rear. If the queue is empty, we show a message accordingly.
10. In the main() function, we create a Queue object q and enqueue the values 10, 20, and 30.
11. We display the current elements of the queue after inserting these values.
12. We dequeue one element and display the updated queue.
13. We continue to dequeue all elements, and finally attempt another dequeue when the queue is empty, which triggers an underflow message.

Advantages Of Queue Data Structure

1. Orderly Processing (FIFO Behavior): Queues strictly follow the First In, First Out (FIFO) order, making them ideal for situations where elements must be processed in the order they arrive. Example: Print jobs in a printer queue are handled in the order they were submitted.
2. Efficient Resource Sharing: In multi-user systems (like operating systems), queues are used to manage tasks efficiently, allowing fair access to shared resources like CPU time, disk drives, etc.
3. Simplified Scheduling: Queues help in implementing scheduling algorithms (like round-robin scheduling), making task management straightforward and organized.
4. Useful in Real-World Applications: Queues are used everywhere: customer service lines, traffic systems, call centers, and more. Their behavior matches naturally with many real-world processes.
5. Supports Variants: Different types like circular queues, priority queues, and double-ended queues (deque) provide flexibility to handle a variety of specific use cases.

Disadvantages Of Queue Data Structure

1. Fixed Size (in Array Implementation): In a static array-based queue, the size must be defined in advance. If the queue becomes full, no more elements can be added even if there is unused space (unless using a circular queue).
2. Wasted Space (Simple Queue): After many dequeue operations, front elements are removed, but the physical space they occupied is not reused unless special techniques like circular arrays are used.
3. Sequential Access Only: Unlike arrays or linked lists where any element can be accessed directly, queues allow access only at the front (for removal) and rear (for insertion).
4. Complex Implementation for Special Queues: Implementing advanced types like priority queues or double-ended queues can be more complex and may require additional data structures like heaps or doubly linked lists.
5. Overhead in Dynamic Implementation: In linked list-based queues, managing memory (allocation and deallocation) introduces some overhead compared to simple array-based structures.

Applications Of Queue Data Structure

1. Job Scheduling in Operating Systems: Queues are used to schedule processes that are waiting for CPU time. Processes are handled in the order they arrive, following FIFO to ensure fairness.
2. Handling Requests in Web Servers: Web servers use queues to manage incoming client requests. Requests are processed one after another to maintain a stable load.
3. Printer Spooling: When multiple print jobs are sent to a printer, they are queued up and printed one by one in the order they were received.
4. Call Center Systems: Incoming calls are placed in a queue and served based on their arrival time, ensuring that no call is missed or skipped.
5. Data Buffers (IO Buffers): Queues are used as buffers in devices like keyboards, hard disks, or networks where data must be stored temporarily and processed in order.
6. Breadth-First Search (BFS) in Graphs: The BFS algorithm for traversing or searching tree or graph data structures uses a queue to keep track of the nodes yet to be explored.
7. Traffic Systems: Traffic at toll booths, traffic lights, or vehicle queues in congestion management can be modeled using queues to handle vehicles in a fair sequence.
8. Resource Management in Networks: In networking, queues manage data packets while they wait to be transmitted over the network, ensuring orderly and efficient communication.
9. Simulation Systems: Queues are used in simulations of real-world systems like supermarkets, banks, airports, and hospitals to study and optimize service processes.
10. Load Balancing: Tasks can be queued and distributed among servers for load balancing, helping systems handle large amounts of work without becoming overloaded.

Conclusion

The queue is a fundamental and widely used data structure that plays a critical role in both real-world systems and computer science applications. By following the First-In, First-Out (FIFO) principle, queues ensure orderly processing where elements are served in the exact sequence they arrive.

From simple linear queues to more specialized forms like circular queues, priority queues, and double-ended queues (deques), each type of queue addresses specific needs related to storage efficiency, task scheduling, and resource management. Understanding the basic operations such as enqueue, dequeue, peek, isEmpty, and isFull, and recognizing their constant time complexity, enables developers to design solutions that are both efficient and reliable.

Whether managing print jobs, handling server requests, or implementing algorithms like breadth-first search (BFS) in graphs, queues offer a structured and predictable way to organize data. A strong grasp of queue concepts forms a foundation for mastering more complex data structures and algorithms.

By integrating queues thoughtfully into your programs, you can ensure better performance, resource handling, and a clearer logic flow — essential qualities in professional software development.

Frequently Asked Questions

Q. What is the main principle behind a queue data structure?

A queue operates on the First-In, First-Out (FIFO) principle. This means the first element inserted into the queue is the first one to be removed, just like standing in a line at a ticket counter.

Q. How does a circular queue differ from a linear queue?

In a linear queue, once the queue is full, no more elements can be inserted even if there is empty space at the front. In a circular queue, the rear end connects back to the front, allowing the available space to be reused efficiently.

Q. What are some real-world applications of queues?

Queues are used in a variety of real-world systems such as:

• Managing processes in operating systems (CPU scheduling).
• Handling requests in web servers.
• Task scheduling in printers.
• Breadth-first search (BFS) algorithms in graphs.

Q. Why is the time complexity of queue operations O(1)?

All basic queue operations like enqueue, dequeue, peek, isEmpty, and isFull only involve simple pointer updates or checks. They do not require shifting or searching elements, which keeps their time complexity constant, i.e., O(1).

Q. What is the role of a priority queue, and how does it differ from a normal queue?

In a priority queue, elements are processed based on their priority rather than the order of arrival. Higher-priority elements are served before lower-priority ones. In contrast, a normal queue strictly follows the FIFO order without considering any priority.

Suggested Reads: 

1. What Is Selection Sort Algorithm? Explained With Code Examples
2. Learn All About Bubble Sort Algorithm (With Code Examples)
3. Merge Sort Algorithm | Working, Applications & More (+Examples)
4. Quick Sort Algorithm | Working, Applications & More (+Examples)
5. Heap Sort Algorithm - Working And Applications (+ Code Examples)