What Is Queue Data Structure in C++?

What Is Queue Data Structure in C++?

In C++, a queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. It operates on elements in a similar way to how we wait in queues in our daily lives – the first person who joins the queue will be the first one to leave.

In programming terms, this means that the element that is inserted first will be the first one to be removed.

Queue Operations:

To understand how a queue works, it’s essential to know about its basic operations. The main operations performed on a queue are:

• Enqueue: This operation adds an element to the end of the queue.
• Dequeue: This operation removes an element from the front of the queue.
• Front: This operation retrieves the front element of the queue without removing it.
• Rear: This operation retrieves the last element of the queue without removing it.
• IsEmpty: This operation checks if the queue is empty or not.
• IsFull: This operation checks if the queue is full or not (in case of a fixed-size implementation).

C++ Implementation:

In C++, we can implement a queue using arrays or linked lists. Here, we’ll focus on array implementation for simplicity.

To begin, let’s define a class named “Queue” with private and public members as follows:

class Queue {
  private:
    int front;          // front element index
    int rear;           // rear element index
    int maxSize;        // maximum size of the queue
    int* elements;      // array to store the elements

  public:
    Queue(int size);    // constructor to initialize the queue
    ~Queue();           // destructor to release memory
    void enqueue(int element);        // function to add an element to the queue
    void dequeue();                   // function to remove an element from the queue
    int getFront();                   // function to get the front element of the queue
    int getRear();                    // function to get the rear element of the queue
    bool isEmpty();                   // function to check if the queue is empty
};

In this implementation, we use four variables: front, rear, maxSize, and elements. The front variable keeps track of the front element’s index, while rear tracks the rear element’s index.

The maxSize variable represents the maximum size of our queue, and elements is an array that stores all our elements.

The constructor initializes these variables, while the destructor frees up memory used by our array. The enqueue operation adds an element at the end of our array by incrementing rear. The dequeue operation removes an element from the front by incrementing front.

The getFront and getRear operations return values using their respective indices. Finally, isEmpty checks if both front and rear are -1, indicating an empty queue.

Example Usage:

Let’s look at an example to understand how to use the queue data structure in C++:

#include 

int main() {
  Queue q(5); // Create a queue of size 5

  q.enqueue(10);
  q.enqueue(20);
  q.enqueue(30);
  q.enqueue(40);
  q.enqueue(50);

  std::cout << "Front element: " << q.getFront() << std::endl;
  std::cout << "Rear element: " << q.getRear() << std::endl;

  while (!q.isEmpty()) {
    std::cout << "Dequeued element: " << q.getFront() << std::endl;
    q.dequeue();
  }

  return 0;
}

In this example, we create a queue of size 5 using the constructor. We then enqueue five elements and display the front and rear elements.

Finally, we dequeue and print all the elements until the queue becomes empty.

Conclusion:

In conclusion, a queue is a fundamental data structure in C++ that follows the FIFO principle. It can be implemented using arrays or linked lists, providing essential operations such as enqueue, dequeue, getFront, getRear, isEmpty, and isFull.

Understanding queues and their implementation is crucial for solving various programming problems efficiently.