Queue

The Queue in data structure is an ordered, linear sequence of items. It is a FIFO (First In First Out) data structure, which means that we can insert an item to the rear end of the queue and remove from the front of the queue only.
A Queue is a sequential data type, unlike an array, in an array, we can access any of its elements using indexing, but we can only access the element at the front of the queue at a time.

A queue of people waiting for their turn or a queue of airplanes waiting for landing instructions are also some real life examples of the queue data structure.

In the above illustration, we can see that the person standing at the front of the queue will be the first one to leave the queue and the person standing at the last of the queue will be the last one to leave.

Other real-life applications of queues include:

• Managing people on an escalator
• Organizing customers in a cashier line at a store
• Queueing vehicles at a car wash
• Regulating traffic flow through one-way exits

Queue Representation

A Queue in data structure can be accessed from both of its sides (at the front for deletion and back for insertion).

The following diagram tries to explain the queue representation as a data structure-

A Queue in data structure can be implemented using arrays, linked lists, or vectors. For the sake of simplicity, we will be implementing queue using a one-dimensional array.

Types of Queue in Data Structure

1. Simple Queue:

• Follows the First-In-First-Out (FIFO) principle.
• Elements are inserted to the rear and removed from the front.
• Linear structure with ordered collection of comparable data.
• Addition of new elements requires deletion of older elements in order.

2. Circular Queue:

• Last member is linked to the first, forming a circular structure.
• Also known as a Ring Buffer.
• Insertion occurs at the front, and deletion at the end of the queue.

3. Priority Queue:

• Nodes have predefined priorities.
• Node with the least priority is removed first.
• Insertion based on the order of node arrival.
• Used in algorithms like Dijkstra’s shortest path and Prim’s algorithm, and in data compression techniques like Huffman coding.

4. Deque (Double-Ended Queue):

• Allows insertion and deletion at both front and rear ends.
• Provides flexibility in managing data with operations from both ends.

Queue Operations

Enqueue

The Enqueue operation inserts an element at the rear of the queue.

Algorithm Procedure:

1. Verify if the Queue is at full capacity.
2. Initialize front to 0 for the initial element.
3. Increment rear by 1.
4. Place the new element at the rear index.

Dequeue

The Dequeue operation extracts an element from the front of the queue.

Algorithm Procedure:

1. Verify if the Queue is empty.
2. Retrieve the value at the front index.
3. Increment front by 1.
4. For the last element, set both front and rear to -1.

Peek

The Peek operation is used to return the front most element of the queue.

Algorithm Procedure:

1. Check if the Queue is empty.
2. Return the value at the front index.

isFull

The isFull operation is used to check if the queue is full or not.

Algorithm Procedure:

1. Check if the number of elements in the queue (size) is equal to the capacity, if yes, return True.
2. Return False.

isEmpty

The isEmpty operation is used to check if the queue is empty or not.

Algorithm Procedure:

1. Check if the number of elements in the queue (size) is equal to 0, if yes, return True.
2. Return False.

Code Implementation of Queue in Data Structure

C++:

#include <iostream>
using namespace std;

#define MAX_SIZE 100

class Queue {
private:
    int arr[MAX_SIZE];
    int front, rear;

public:
    Queue() {
        front = rear = -1;
    }

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

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

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full. Cannot enqueue.\n";
            return;
        }
        if (isEmpty())
            front = 0;
        arr[++rear] = value;
        cout << value << " enqueued to queue.\n";
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot dequeue.\n";
            return -1;
        }
        int value = arr[front];
        if (front == rear)
            front = rear = -1;
        else
            front++;
        cout << value << " dequeued from queue.\n";
        return value;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot peek.\n";
            return -1;
        }
        return arr[front];
    }
};

int main() {
    Queue queue;
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    cout << "Front element: " << queue.peek() << endl;

    queue.dequeue();
    queue.dequeue();

    cout << "Front element after dequeuing: " << queue.peek() << endl;

    return 0;
}

Java:

class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;

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

    public void enqueue(int item) {
        if (!isFull()) {
            rear = (rear + 1) % maxSize;
            queueArray[rear] = item;
            currentSize++;
            System.out.println(item + " enqueued to queue.");
        } else {
            System.out.println("Queue is full. Cannot enqueue " + item);
        }
    }

    public int dequeue() {
        if (!isEmpty()) {
            int removedItem = queueArray[front];
            front = (front + 1) % maxSize;
            currentSize--;
            return removedItem;
        } else {
            System.out.println("Queue is empty. Cannot dequeue.");
            return -1;
        }
    }

    public int peek() {
        if (!isEmpty()) {
            return queueArray[front];
        } else {
            System.out.println("Queue is empty. Cannot peek.");
            return -1;
        }
    }

    public boolean isFull() {
        return currentSize == maxSize;
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Queue queue = new Queue(3);

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

        System.out.println("Front element: " + queue.peek());

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

        System.out.println("Front element after dequeuing: " + queue.peek());
    }
}

Python:

class Queue:
    def __init__(self, size):
        self.max_size = size
        self.queue_array = [None] * size
        self.front = 0
        self.rear = -1
        self.current_size = 0

    def enqueue(self, item):
        if not self.is_full():
            self.rear = (self.rear + 1) % self.max_size
            self.queue_array[self.rear] = item
            self.current_size += 1
            print(f"{item} enqueued to queue.")
        else:
            print("Queue is full. Cannot enqueue", item)

    def dequeue(self):
        if not self.is_empty():
            removed_item = self.queue_array[self.front]
            self.front = (self.front + 1) % self.max_size
            self.current_size -= 1
            return removed_item
        else:
            print("Queue is empty. Cannot dequeue.")
            return None

    def peek(self):
        if not self.is_empty():
            return self.queue_array[self.front]
        else:
            print("Queue is empty. Cannot peek.")
            return None

    def is_full(self):
        return self.current_size == self.max_size

    def is_empty(self):
        return self.current_size == 0

# Example usage
if __name__ == "__main__":
    queue = Queue(3)

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

    print("Front element:", queue.peek())

    print(queue.dequeue(), "dequeued from queue.")
    print(queue.dequeue(), "dequeued from queue.")

    print("Front element after dequeuing:", queue.peek())

Output:

10 enqueued to queue.
20 enqueued to queue.
30 enqueued to queue.
Front element: 10
10 dequeued from queue.
20 dequeued from queue.
Front element after dequeuing: 30

Limitations of Queue

Following are the limitations/disadvantages of a Queue data structure:

1. A queue is not readily searchable: You might have to maintain another queue to store the dequeued elements in search of the wanted element.
2. Traversal possible only once: The front most element needs to be dequeued to access the element behind it, this happens throughout the queue while traversing through it. In this process, the queue becomes empty.
3. Memory Wastage: In a Static Queue, the array’s size determines the queue capacity, the space occupied by the array remains the same, no matter how many elements are in the queue.

Applications of Queue

A Queue data structure is used when things don’t have to be accessed immediately but in FIFO (First In First Out) order. This property of the queue data structure makes queue applicable for the following situations:

1. Job Scheduling
   The computer schedules the job execution one by one. There are many jobs like a key press, a mouse click, etc. in the system.
   The jobs are brought in the main memory and are assigned to the processor one by one which is organized using a queue. For eg, Round Robin processor scheduling in queues.
2. Multiprogramming
   If there are multiple programs in the main memory, then that state is called multiprogramming. The programs in the main memory are organized in the form of queues, which are then called “Ready Queues”.
   The processors will execute the programs by accessing them from the "Cache Memory" for simultaneous execution.
3. Operation on data structures
   Certain operations like BFS (Breadth First Search), and tree traversal uses Queue. The sequence of traversal of inputs is set using queues.
4. Buffer Space
   Queues are used in networking, during transmission of data from one point to another point.

Conclusion

1. Fundamental Structure: A queue in data structure is an ordered sequence where elements are inserted at the back and removed from the front, adhering to the FIFO principle.
2. Real-life Analogies: Just like people waiting in line or airplanes queued for landing, queues find application in scenarios requiring orderly processing.
3. Representation: Queues can be represented using various structures like arrays, linked lists, or vectors, each offering different advantages based on the use case.
4. Types of Queues: Simple, Circular, Priority, and Deque (Double-Ended Queue) are the primary types, each serving distinct purposes and offering unique functionalities.
5. Queue Operations: Enqueueing, dequeueing, peeking, and checking for fullness or emptiness are the fundamental operations performed on queues, ensuring efficient data management.
6. Applications: From job scheduling in operating systems to implementing algorithms like BFS, queues find extensive use in diverse fields where orderly processing is paramount.

Join our Data Structures in C++ Free Course now and gain a competitive edge in your programming career!