What Is Queue Data Structure?

What Is Queue Data Structure?

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. It is an ordered collection of elements in which an element is inserted at one end called the rear and removed from the other end called the front. The element that is inserted first will be the first one to be removed.

Operations on a Queue:

A queue supports two main operations:

• Enqueue: It adds an element to the rear of the queue.
• Dequeue: It removes an element from the front of the queue.

In addition to these, there are a few more commonly used operations on a queue:

• Front: It returns the value of the front element without removing it.
• Rear: It returns the value of the rear element without removing it.
• IsEmpty: It checks whether the queue is empty or not. Returns true if empty, false otherwise.
• IsFull: It checks whether the queue is full or not. Returns true if full, false otherwise.

The Implementation of Queue Data Structure:

A queue can be implemented using various data structures like arrays and linked lists. Here, we will discuss how to implement a queue using an array.

To define a queue data structure in C++, you can use either static or dynamic arrays. A static array has a fixed size defined at compile-time, while a dynamic array can grow or shrink in size during runtime.

Let’s see the implementation of a queue using an array:

class Queue {
    private:
        static const int MAX_SIZE = 100;
        int arr[MAX_SIZE];
        int front, rear;
    
    public:
        Queue() {
            front = -1;
            rear = -1;
        }

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

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

        void enqueue(int value) {
            if (isFull()) {
                cout << "Queue is full. Overflow condition!\n";
                return;
            }
            
            if (isEmpty()) {
                front = 0;
                rear = 0;
            } else {
                rear++;
            }
            
            arr[rear] = value;
        }

        void dequeue() {
            if (isEmpty()) {
                cout << "Queue is empty. Underflow condition!\n";
                return;
            }
            
            if (front == rear) { // Only one element in the queue
                front = -1;
                rear = -1;
            } else {
                front++;
            }
        }

        int getFront() {
          if (isEmpty()) {
              cout << "Queue is empty.\n";
              return -1; // or any other appropriate value
          }
          
          return arr[front];
      }

      int getRear() {
          if (isEmpty()) {
              cout << "Queue is empty.\n";
              return -1; // or any other appropriate value
          }
          
          return arr[rear];
      }
};

Now you have a basic understanding of what a queue data structure is and how to implement it using an array. You can start using queues in your programs to efficiently manage data that follows the FIFO principle.

Conclusion:

In summary, a queue is a data structure that allows adding elements at one end and removing elements from the other end, following the FIFO principle. It is commonly used in various applications such as process scheduling, printer spooling, and breadth-first search algorithms. Understanding queues and their implementation will help you solve problems efficiently in your programming journey.