Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the first element inserted is the first to be popped out. In this article, we will cover all the basics of Queue, Operations on Queue, its implementation, advantages, disadvantages which will help you solve all the problems based on Queue.

What is Queue?

Queue is a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.

We define a queue to be a list in which all additions to the list are made at one end (back of the queue), and all deletions from the list are made at the other end(front of the queue).  The element which is first pushed into the order, the delete operation is first performed on that.

FIFO Principle of Queue:

• A Queue is like a line waiting to purchase tickets, where the first person in line is the first person served. (i.e. First Come First Serve).
• Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front of the queue(sometimes, head of the queue). Similarly, the position of the last entry in the queue, that is, the one most recently added, is called the rear (or the tail) of the queue.

Representation of Queue Data Structure:

The image below shows how we represent Queue Data Structure:

Types of Queue:

Queue data structure can be classified into 4 types:

There are different types of queues:

1. Simple Queue: Simple Queue simply follows FIFO Structure. We can only insert the element at the back and remove the element from the front of the queue.
2. Double-Ended Queue (Dequeue): In a double-ended queue the insertion and deletion operations, both can be performed from both ends. They are of two types:
   • Input Restricted Queue: This is a simple queue. In this type of queue, the input can be taken from only one end but deletion can be done from any of the ends.
   • Output Restricted Queue: This is also a simple queue. In this type of queue, the input can be taken from both ends but deletion can be done from only one end.
3. Circular Queue: This is a special type of queue where the last position is connected back to the first position. Here also the operations are performed in FIFO order.
4. Priority Queue: A priority queue is a special queue where the elements are accessed based on the priority assigned to them. They are of two types:
   • Ascending Priority Queue: In Ascending Priority Queue, the elements are arranged in increasing order of their priority values. Element with smallest priority value is popped first.
   • Descending Priority Queue: In Descending Priority Queue, the elements are arranged in decreasing order of their priority values. Element with largest priority is popper first.

Basic Operations in Queue:

Some of the basic operations for Queue in Data Structure are:

1. Enqueue: Adds (or stores) an element to the end of the queue..
2. Dequeue: Removal of elements from the queue.
3. Peek or front: Acquires the data element available at the front node of the queue without deleting it.
4. rear: This operation returns the element at the rear end without removing it.
5. isFull: Validates if the queue is full.
6. isEmpty: Checks if the queue is empty.

There are a few supporting operations (auxiliary operations):

1. Enqueue Operation in Queue: 

Enqueue() operation in Queue adds (or stores) an element to the end of the queue.
The following steps should be taken to enqueue (insert) data into a queue:

• Step 1: Check if the queue is full.
• Step 2: If the queue is full, return overflow error and exit.
• Step 3: If the queue is not full, increment the rear pointer to point to the next empty space.
• Step 4: Add the data element to the queue location, where the rear is pointing.
• Step 5: return success.

Implementation of Enqueue:

void queueEnqueue(int data)
{
    // Check queue is full or not
    if (capacity == rear) {
        printf("\nQueue is full\n");
        return;
    }

    // Insert element at the rear
    else {
        queue[rear] = data;
        rear++;
    }
    return;
}

void queueEnqueue(int data)
{
    // Check queue is full or not
    if (capacity == rear) {
        System.out.println("\nQueue is full\n");
        return;
    }

    // Insert element at the rear
    else {
        queue[rear] = data;
        rear++;
    }
    return;
}

// This code is contributed by aadityapburujwale

2. Dequeue Operation in Queue: 

Removes (or access) the first element from the queue.
The following steps are taken to perform the dequeue operation:

• Step 1: Check if the queue is empty.
• Step 2: If the queue is empty, return the underflow error and exit.
• Step 3: If the queue is not empty, access the data where the front is pointing.
• Step 4: Increment the front pointer to point to the next available data element.
• Step 5: The Return success.

Implementation of dequeue:

void queueDequeue()
{
    // If queue is empty
    if (front == rear) {
        printf("\nQueue is empty\n");
        return;
    }

    // Shift all the elements from index 2
    // till rear to the left by one
    else {
        for (int i = 0; i < rear - 1; i++) {
            queue[i] = queue[i + 1];
        }

        // decrement rear
        rear--;
    }
    return;
}

void queueDequeue()
{
    // If queue is empty
    if (front == rear) {
        System.out.println("\nQueue is empty\n");
        return;
    }

    // Shift all the elements from index 2
    // till rear to the left by one
    else {
        for (int i = 0; i < rear - 1; i++) {
            queue[i] = queue[i + 1];
        }

        // decrement rear
        rear--;
    }
    return;
}

// This code is contributed by aadityapburujwale

3. Front Operation in Queue: 

This operation returns the element at the front end without removing it.

// Function to get front of queue
int front(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    return queue->arr[queue->front];
}

// Function to get front of queue
int front(Queue queue)
{
    if (isempty(queue))
        return Integer.MIN_VALUE;
    return queue.arr[queue.front];
}

// This code is contributed by aadityapburujwale

4. Rear Operation in Queue: 

This operation returns the element at the rear end without removing it.

int rear(queue<int>& myQueue)
{
    queue<int> tempQueue = myQueue;

    while (tempQueue.size() > 1) {
        tempQueue.pop();
    }

    return tempQueue.front();
}

public static int rear(Queue<Integer> myQueue)
{
    if (myQueue.isEmpty()) {
        System.out.println("Queue is empty.");
        return -1;
    }

    int rearElement = -1;
    while (!myQueue.isEmpty()) {
        rearElement = myQueue.poll();
    }

    return rearElement;
}

5. isEmpty Operation in Queue: 

This operation returns a boolean value that indicates whether the queue is empty or not.

// This function will check whether
// the queue is empty or not:
bool isEmpty()
{
    if (front == -1)
        return true;
    else
        return false;
}

// This function will check whether
// the queue is empty or not:
boolean isEmpty()
{
    if (front == -1)
        return true;
    else
        return false;
}

// This code is contributed by aadityapburujwale

6. isFull Operation in Queue: 

This operation returns a boolean value that indicates whether the queue is full or not.

// This function will check
// whether the queue is full or not.
bool isFull()
{
    if (front == 0 && rear == MAX_SIZE - 1) {
        return true;
    }
    return false;
}

// This function will check
// whether the queue is full or not.
boolean isFull()
{
    if (front == 0 && rear == MAX_SIZE - 1) {
        return true;
    }
    return false;
}

// This code is contributed by aadityapburujwale

Queue Implementation:

Queue can be implemented using following data structures:

• Implementation of Queue using Arrays
• Implementation of Queue using Linked List

We have discussed the implementation of Queue below:

// Implementation of queue(enqueue, dequeue).
#include <bits/stdc++.h>
using namespace std;

class Queue {
public:
    int front, rear, size;
    unsigned cap;
    int* arr;
};

Queue* createQueue(unsigned cap)
{
    Queue* queue = new Queue();
    queue->cap = cap;
    queue->front = queue->size = 0;

    queue->rear = cap - 1;
    queue->arr = new int[(queue->cap * sizeof(int))];
    return queue;
}

int isFull(Queue* queue)
{
    return (queue->size == queue->cap);
}

int isempty(Queue* queue) { return (queue->size == 0); }
// Function to add an item to the queue.
// It changes rear and size.
void enqueue(Queue* queue, int item)
{
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->cap;
    queue->arr[queue->rear] = item;
    queue->size = queue->size + 1;
    cout << item << " enqueued to queue\n";
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    int item = queue->arr[queue->front];
    queue->front = (queue->front + 1) % queue->cap;
    queue->size = queue->size - 1;
    return item;
}
int front(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    return queue->arr[queue->front];
}
int rear(Queue* queue)
{
    if (isempty(queue))
        return INT_MIN;
    return queue->arr[queue->rear];
}

// Driver code
int main()
{
    Queue* queue = createQueue(1000);
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    cout << dequeue(queue);
    cout << " dequeued from queue\n";
    cout << "Front item is " << front(queue) << endl;
    cout << "Rear item is " << rear(queue);
    return 0;
}

// Java program for array
// implementation of queue

// A class to represent a queue
class Queue {
    int front, rear, size;
    int capacity;
    int array[];

    public Queue(int capacity)
    {
        this.capacity = capacity;
        front = this.size = 0;
        rear = capacity - 1;
        array = new int[this.capacity];
    }

    // Queue is full when size becomes
    // equal to the capacity
    boolean isFull(Queue queue)
    {
        return (queue.size == queue.capacity);
    }

    // Queue is empty when size is 0
    boolean isEmpty(Queue queue)
    {
        return (queue.size == 0);
    }

    // Method to add an item to the queue.
    // It changes rear and size
    void enqueue(int item)
    {
        if (isFull(this))
            return;
        this.rear = (this.rear + 1) % this.capacity;
        this.array[this.rear] = item;
        this.size = this.size + 1;
        System.out.println(item + " enqueued to queue");
    }

    // Method to remove an item from queue.
    // It changes front and size
    int dequeue()
    {
        if (isEmpty(this))
            return Integer.MIN_VALUE;

        int item = this.array[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size = this.size - 1;
        return item;
    }

    // Method to get front of queue
    int front()
    {
        if (isEmpty(this))
            return Integer.MIN_VALUE;

        return this.array[this.front];
    }

    // Method to get rear of queue
    int rear()
    {
        if (isEmpty(this))
            return Integer.MIN_VALUE;

        return this.array[this.rear];
    }
}

// Driver class
public class Test {
    public static void main(String[] args)
    {
        Queue queue = new Queue(1000);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        System.out.println(queue.dequeue()
                           + " dequeued from queue");

        System.out.println("Front item is "
                           + queue.front());

        System.out.println("Rear item is " + queue.rear());
    }
}

// This code is contributed by Susobhan Akhuli

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40

Complexity Analysis of Operations on Queue

Applications of Queue:

Application of queue is common. In a computer system, there may be queues of tasks waiting for the printer, for access to disk storage, or even in a time-sharing system, for use of the CPU. Within a single program, there may be multiple requests to be kept in a queue, or one task may create other tasks, which must be done in turn by keeping them in a queue.

• Queue can be used in job scheduling like Printer Spooling.
• Queue can be used where we have a single resource and multiple consumers.
• In a network, a queue is used in devices such as a router/switch and mail queue.
• Queue can be used in various algorithm techniques like Breadth First Search, Topological Sort, etc.

Advantages of Queue:

• A large amount of data can be managed efficiently with ease.
• Operations such as insertion and deletion can be performed with ease as it follows the first in first out rule.
• Queues are useful when a particular service is used by multiple consumers.
• Queues are fast in speed for data inter-process communication.
• Queues can be used in the implementation of other data structures.

Disadvantages of Queue:

• The operations such as insertion and deletion of elements from the middle are time consuming.
• Searching an element takes O(N) time.
• Maximum size of a queue must be defined prior in case of array implementation.

FAQs (Frequently asked questions) on Queue:

1. What data structure can be used to implement a priority queue?

Priority queues can be implemented using a variety of data structures, including linked lists, arrays, binary search trees, and heaps. Priority queues are best implemented using the heap data structure.

3. In data structures, what is a double-ended queue?

In a double-ended queue, elements can be inserted and removed at both ends.

4. What is better, a stack or a queue?

If you want things to come out in the order you put them in, use a queue. Stacks are useful when you want to reorder things after putting them in. 

5. Is Queue a LIFO or FIFO?

Queue follows FIFO (First-In-First-Out) principle, so the element which is inserted first will be deleted first.

6. What are the four types of Queue?

The four types of Queue are: Simple Queue, Double-ended queue, Circular Queue and Priority Queue.

7. What are some real-life applications of Queue?

Real-life applications of queue include: Cashier Line in Stores, CPU Scheduling, Disk Scheduling, Serving requests on a shared resource like Printer.

8. What are some limitations of Queue?

Some of the limitations of Queue are: deletion of some middle element is not possible until all the elements before it are not deleted. Also random access of any element takes linear time complexity.

9. What are the different ways to implement a Queue?

Queue data structure can be implemented by using Arrays or by using Linked List. The Array implementation requires the size of the Queue to be specified at the time of declaration.

10. What are some common operations in Queue?

Some common operations on Queue are: Insertion or Enqueue, Deletion or Dequeue, Front, Rear, isFull, isEmpty, etc.

Related articles:

• Queue Operations 
• Applications, Advantages and Disadvantages of Queue
• Maximum of all subarrays of size k
• Generate Binary Numbers
• Queue using two Stacks
• Reverse First K elements of Queue

Similar to Stack, Queue is a linear data structure that follows a particular order in which the operations are performed for storing data. The order is First In First Out (FIFO). One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line. It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. 
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Queue Data structure

Basic Operations on Queue: 

• enqueue(): Inserts an element at the end of the queue i.e. at the rear end.
• dequeue(): This operation removes and returns an element that is at the front end of the queue.
• front(): This operation returns the element at the front end without removing it.
• rear(): This operation returns the element at the rear end without removing it.
• isEmpty(): This operation indicates whether the queue is empty or not.
• isFull(): This operation indicates whether the queue is full or not.
• size(): This operation returns the size of the queue i.e. the total number of elements it contains.  

Types of Queues: 

• Simple Queue: Simple queue also known as a linear queue is the most basic version of a queue. Here, insertion of an element i.e. the Enqueue operation takes place at the rear end and removal of an element i.e. the Dequeue operation takes place at the front end. Here problem is that if we pop some item from front and then rear reach to the capacity of the queue and although there are empty spaces before front means the queue is not full but as per condition in isFull() function, it will show that the queue is full then. To solve this problem we use circular queue.
• Circular Queue:  In a circular queue, the element of the queue act as a circular ring. The working of a circular queue is similar to the linear queue except for the fact that the last element is connected to the first element. Its advantage is that the memory is utilized in a better way. This is because if there is an empty space i.e. if no element is present at a certain position in the queue, then an element can be easily added at that position using modulo capacity(%n).
• Priority Queue: This queue is a special type of queue. Its specialty is that it arranges the elements in a queue based on some priority. The priority can be something where the element with the highest value has the priority so it creates a queue with decreasing order of values. The priority can also be such that the element with the lowest value gets the highest priority so in turn it creates a queue with increasing order of values. In pre-define priority queue, C++ gives priority to highest value whereas Java gives priority to lowest value.
• Dequeue: Dequeue is also known as Double Ended Queue. As the name suggests double ended, it means that an element can be inserted or removed from both ends of the queue, unlike the other queues in which it can be done only from one end. Because of this property, it may not obey the First In First Out property. 

 

Applications of Queue: 

Queue is used when things don’t have to be processed immediately, but have to be processed in First In First Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.

• When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling. 
•  When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc. 
•  Queue can be used as an essential component in various other data structures.

Array implementation Of Queue:

For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from the front. If we simply increment front and rear indices, then there may be problems, the front may reach the end of the array. The solution to this problem is to increase front and rear in circular manner.

Steps for enqueue:

1. Check the queue is full or not
2. If full, print overflow and exit
3. If queue is not full, increment tail and add the element

Steps for dequeue:

1. Check queue is empty or not
2. if empty, print underflow and exit
3. if not empty, print element at the head and increment head

Below is a program to implement above operation on queue

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40

Complexity Analysis:  

• Time Complexity

• Auxiliary Space: 
  O(N) where N is the size of the array for storing elements.

Advantages of Array Implementation:  

• Easy to implement.
• A large amount of data can be managed efficiently with ease.
• Operations such as insertion and deletion can be performed with ease as it follows the first in first out rule.

Disadvantages of Array Implementation:  

• Static Data Structure, fixed size.
• If the queue has a large number of enqueue and dequeue operations, at some point (in case of linear increment of front and rear indexes) we may not be able to insert elements in the queue even if the queue is empty (this problem is avoided by using circular queue).
• Maximum size of a queue must be defined prior.

In this article, the Linked List implementation of the queue data structure is discussed and implemented. Print ‘-1’ if the queue is empty.

Approach: To solve the problem follow the below idea:

we maintain two pointers, front, and rear. The front points to the first item of the queue and rear points to the last item.

• enQueue(): This operation adds a new node after the rear and moves the rear to the next node.
• deQueue(): This operation removes the front node and moves the front to the next node.

Follow the below steps to solve the problem:

• Create a class QNode with data members integer data and QNode* next
  • A parameterized constructor that takes an integer x value as a parameter and sets data equal to x and next as NULL
• Create a class Queue with data members QNode front and rear
• Enqueue Operation with parameter x:
  • Initialize QNode* temp with data = x
  • If the rear is set to NULL then set the front and rear to temp and return(Base Case)
  • Else set rear next to temp and then move rear to temp
• Dequeue Operation:
  • If the front is set to NULL return(Base Case)
  • Initialize QNode temp with front and set front to its next
  • If the front is equal to NULL then set the rear to NULL
  • Delete temp from the memory

Below is the Implementation of the above approach:

Queue Front : 40
Queue Rear : 50

Time Complexity: O(1), The time complexity of both operations enqueue() and dequeue() is O(1) as it only changes a few pointers in both operations
Auxiliary Space: O(1), The auxiliary Space of both operations enqueue() and dequeue() is O(1) as constant extra space is required

Related Article:
Introduction and Array Implementation of Queue

What is a Circular Queue?

A Circular Queue is an extended version of a normal queue where the last element of the queue is connected to the first element of the queue forming a circle.

The operations are performed based on FIFO (First In First Out) principle. It is also called ‘Ring Buffer’. 
 

In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we can not insert the next element even if there is a space in front of queue.

Operations on Circular Queue:

• Front: Get the front item from the queue.
• Rear: Get the last item from the queue.
• enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at the rear position. 
  • Check whether the queue is full – [i.e., the rear end is in just before the front end in a circular manner].
  • If it is full then display Queue is full. 
    • If the queue is not full then,  insert an element at the end of the queue.
• deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from the front position. 
  • Check whether the queue is Empty.
  • If it is empty then display Queue is empty.
    • If the queue is not empty, then get the last element and remove it from the queue.

Illustration of Circular Queue Operations:

Follow the below image for a better understanding of the enqueue and dequeue operations.

Working of Circular queue operations

How to Implement a Circular Queue?

A circular queue can be implemented using two data structures:

• Array
• Linked List

Here we have shown the implementation of a circular queue using an array data structure.

Implement Circular Queue using Array:

1. Initialize an array queue of size n, where n is the maximum number of elements that the queue can hold.
2. Initialize two variables front and rear to -1.
3. Enqueue: To enqueue an element x into the queue, do the following:
   • Increment rear by 1.
     • If rear is equal to n, set rear to 0.
   • If front is -1, set front to 0.
   • Set queue[rear] to x.
4. Dequeue: To dequeue an element from the queue, do the following:
   • Check if the queue is empty by checking if front is -1. 
     • If it is, return an error message indicating that the queue is empty.
   • Set x to queue[front].
   • If front is equal to rear, set front and rear to -1.
   • Otherwise, increment front by 1 and if front is equal to n, set front to 0.
   • Return x.

Below is the implementation of the above idea: