Queue Data Structure

What is Queue?

Queue is a fundamental data structure and it plays an important role in software development. Queue is useful in many real-world scenarios such as Printer Job Queues, Task Scheduling and Traffic Management.

Queue is a linear data structure that follows the FIFO (First-In-First-Out).In queues, insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.

How Queue Works?

At its core, queue is a collection of elements with following operations.

• Enqueue: Adding an element to the back of the queue.
• Dequeue: Removing the element from the front of the queue.
• Front: Get the element at the front.
• Rear or (Back): Get the element at the rear.
• isEmpty: Check if Queue is empty.
• Size: Finding the number of elements in the queue.

Queue Implementation in C++

#include<iostream>

using namespace std;

const int MAX_SIZE = 6;

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

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

  // method to check if queue is empty.
  bool isEmpty() {
    if(elementCount == 0) {
      return true;
    }
    else {
      return false;
    }
  }

  // method to check if queue is full.
  bool isFull() {
    if(elementCount == MAX_SIZE) {
      return true;
    } 

    else {
      return false;
    }
  }

  // method to add item in the queue.
  void enqueue(int element) {
    if(isFull() == true) {
      cout << "Queue is full.";
      return;
    }

    rear = (rear + 1) % MAX_SIZE;
    arr[rear] = element;

    elementCount++;
  }

  // method to remove item for the queue. 
  int dequeue() {
    if(isEmpty() == true) {
      cout << "Queue is empty.";
      return -1;
    }

    int x = arr[front];
    front = (front + 1) % MAX_SIZE;

    elementCount--;

    return x;
  }

  // method to get peek of the queue.
  int peek() {
    if(isEmpty() == true) {
      cout << "Queue is empty.";
        return -1;
    }

    return arr[front];
  }
};

int main() {
  Queue q;

  q.enqueue(10);
  q.enqueue(12);
  q.enqueue(15);
  q.enqueue(14);

  // Peek of the Queue is 10
  cout << "Peak of the Queue is "<< q.peek() << endl; 
  // Dequeued element from the queue is 10
  cout << "Dequeued element from the queue is " << q.dequeue() << endl; 
  // Dequeued element from the queue is 12
  cout << "Dequeued element from the queue is "q.dequeue() << endl;
}

Types of Queues

There are following types of queues.

1. Simple Queue

Simple queue strictly follows the FIFO (First-In-First-Out). Each element is enqueued at the REAR and dequeued from the FRONT.

2. Priority Queue

A priority queue assigns a priority to each item of queue. Elements are dequeue based on their priority.Higher-priority elements are dequeued before lower-priority ones. Priority queues are useful in scenarios where some tasks are more urgent than others.

3. Circular Queue

In a circular queue, the last item of the queue is connect with first item of the queue. This allows for efficient memory utilization and is often used in scenarios such as scheduling processes in an operating system.

4. Double-ended Queue

A Double-ended queue allows elements to be enqueued and dequeued from both ends. This type of queues makes suitable for wide range of applications such as implementing data structures like stack and queue simultaneously.

Real-World Applications of Queue

Real-World applications of queues are as follows.

1. Print Queue

In a printer job queue, print jobs are processed in the order they are received, following the FIFO principle.

2. Task Scheduling

Operating systems use queues to manage processes and allocate CPU time, ensuring that each process gets its fair share.

3. Breadth-First Search (BFS)

BFS, a popular graph traversal algorithm, uses queues to explore nodes level by level.

4. Call Center Systems

Call centers use queues to manage incoming calls, ensuring that calls are answered in the order they are received.

Conclusion

Queues are a fundamental concept in computer science, with a lot of applications in various domains. Understanding the FIFO principle and the basic operations of enqueue and dequeue provides the foundation for implementing and solving complex problems efficiently.

Thanks for Reading and have a nice day.