A 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, and all deletions from the list are made at the other end. The element which is first pushed into the order, the delete operation is first performed on that.

When an element is inserted in a queue, then the operation is known as Enqueue and when an element is deleted from the queue, then the operation is known as Dequeue. It is important to know that we cannot insert an element if the size of the queue is full and cannot delete an element when the queue itself is empty. If we try to insert an element even after the queue is full, then such a condition is known as overflow whereas, if we try to delete an element even after the queue is empty then such a condition is known as underflow.

Characteristics of Queue:

• Queue can handle multiple data.

• We can access both ends.

• They are fast and flexible.

Queue Representation:

1. Array Representation of Queue:

Like stacks, Queues can also be represented in an array: In this representation, the Queue is implemented using the array. Variables used in this case are

• Queue: the name of the array storing queue elements.

• qfront: the index where the first element is stored in the array representing the queue.

• rear: the index where the last element is stored in an array representing the queue.

• size: the size of the array.

    class Queue{
       int *arr;
       int qfront;
       int rear;
       int size;
    public:
      Queue(){
            size = 100001;
            arr = new int[size];
            qfront = 0;
            rear = 0;
           }
     void enqueue(int data)
        {
            if (rear == size)
            {
                cout << "Queue is full." << endl;
            }
            else
            {
                arr[rear] = data;
                rear++;
            }
        }
  
        int dequeue()
        {
            if (qfront == rear)
            {
                return -1;
            }
            else
            {
                int ans = arr[qfront];
                arr[qfront] = -1;
                qfront++;
                if (qfront == rear)
                {
                    qfront = 0;
                    rear = 0;
                }
                return ans;
            }
        }
  
        int front()
        {
            if (qfront == rear)
            {
                return -1;
            }
            else
            {
                return arr[qfront];
            }
        }
  
        bool isEmpty()
        {
            if (qfront == rear)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    };
  

2. Linked List Representation of Queue:

A queue can also be represented using the following entities:

• Linked-lists,

• Pointers, and

• Structures.

    struct Node {
        int data;
        Node* next;
    };
  
    // Define a Queue class
    class Queue {
    private:
        Node* front;
        Node* rear;
  
    public:
        Queue() {
            front = nullptr;
            rear = nullptr;
        }
      // Function to check if the queue is empty
        bool isEmpty() {
            return front == nullptr;
        }
  
        // Function to add an element to the back of the queue
        void enqueue(int value) {
            Node* newNode = new Node;
            newNode->data = value;
            newNode->next = nullptr;
  
            if (isEmpty()) {
                front = newNode;
                rear = newNode;
            } else {
                rear->next = newNode;
                rear = newNode;
            }
        }
  
        // Function to remove and return an element from the front of the queue
        int dequeue() {
            if (isEmpty()) {
                std::cout << "Queue is empty." << std::endl;
                return -1; // You can choose any value to indicate an error
            }
  
            Node* temp = front;
            int value = temp->data;
            front = front->next;
            delete temp;
            return value;
        }
    };
  

Basic Operations for Queue in Data Structure:

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. isNull() – Checks if the queue is empty.

There are a few supporting operations (auxiliary operations):

1. Enqueue():

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.

2. Dequeue():

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.

3. front():

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

4. rear():

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

5. isEmpty():

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

6. isFull():

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

Advantages of a 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 follow 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 a Queue:

• The operations such as insertion and deletion of elements from the middle are time-consuming.

• Limited Space.

• In a classical queue, a new element can only be inserted when the existing elements are deleted from the queue.

• Searching for an element takes O(N) time.

• The maximum size of a queue must be defined prior.

Application of a Queue:

• Multi programming: Multi programming means when multiple programs are running in the main memory. It is essential to organize these multiple programs and these multiple programs are organized as queues.

• Network: In a network, a queue is used in devices such as a router or a switch. another application of a queue is a mail queue which is a directory that stores data and controls files for mail messages.

• Job Scheduling: The computer has a task to execute a particular number of jobs that are scheduled to be executed one after another. These jobs are assigned to the processor one by one which is organized using a queue.

• Shared resources: Queues are used as waiting lists for a single shared resource.

Real-time application of Queue:

• ATM Booth Line

• Ticket Counter Line

• Key press sequence on the keyboard

• CPU task scheduling

• Waiting time of each customer at call centres.