Categories
28°C, New York
Home C++ Basic Operations on Circular Queue in C++

Basic Operations on Circular Queue in C++

Concept Behind Circular Queue

C++ Program to Implement Circular Queue Using Array

The basic operations of the circular queue are same as that of normal queue but the implementation is different. The following table list the basic operations in circular queue:

Operation

Description

Time Complexity

Space Complexity

Enqueue

This function is used to insert an element into the circular queue.

O(1)

O(1)

Dequeue

This function is used to delete an element from the circular queue.

O(1)

O(1)

Peek

Returns the front element of the queue.

O(1)

O(1)

IsFull

Returns true is the queue is full otherwise returns false.

O(1)

O(1)

IsEmpty

Returns true is the queue is empty otherwise returns false.

O(1)

O(1)

Representation of Circular Queue in C++

The circular queue in C++ can be represented as a class which contains the rear and front index pointers, array to store queue elements, and the member functions to provide the basic operations.

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

Implementation of isEmpty for Circular Queue

The queue is only empty when the front == rear pointer

Algorithm of isEmpty

if front is equal to rear
      return true
else
      return false

Implementation of isFull for Circular Queue

The queue will be full when the incremented rear pointer is equal to the front pointer.

Algorithm of isFull

if (rear + 1) % size is equal to front
      return true;
else
      return false;

Implementation of Enqueue for Circular Queue

We insert the new elements at the end of the queue using rear pointer. We first check if the queue is full or not.

Algorithm of Enqueue

if (isFull(queue)) {
      print "Queue Overflow"
      return
else
      rear = (rear + 1) % size
      arr[rear] = new_element

Implementation of Dequeue for Circular Queue

The elements are removed from the queue at the front of the queue. We first need to check whether queue is empty or not.

Algorithm of Enqueue

if (isEmpty(queue)) {
      print "Queue Underflow"
      return
else
      front = (front + 1) % size

C++ Program to Implement Circular Queue

In C++, Queues are a fundamental data structure in computer science which works on the principle of FIFO (First In, First Out). They can be implemented using both array and linked list. A circular queue is a type of queue in which the last element is connected to the first element, forming a circular structure. In this article, we’ll learn about circular queue, how to implement it in C++, and analyze its complexity.

Similar Reads

What is Circular Queue in C++?

In a circular queue is a queue where the last element of the queue is connected to the first element of the queue. As it is a queue, it follows the FIFO (First-In-First-Out) order of operation. It is also known as “Ring buffer” as the resulted data structure is logically circular....

Why we need Circular Queue in C++?

Circular queue concept is especially helpful when the queue is implemented using an array. In linear implementation, when the rear pointer reaches the end of the queue, we cannot insert new elements even if there are empty locations in the queue....

Concept Behind Circular Queue

There are two different concepts behind circular queue depending upon which data structure it is using in its implementation:...

Basic Operations on Circular Queue in C++

The basic operations of the circular queue are same as that of normal queue but the implementation is different. The following table list the basic operations in circular queue:...

C++ Program to Implement Circular Queue Using Array

C++ // C++ program to implement the circular queue using array #include // defining the max size of the queue #define MAX_SIZE 5 using namespace std; // class that represents queue class Queue { public: // index pointers and data array int front, rear; int arr[MAX_SIZE]; // constructor to initialize the index pointers Queue() { front = rear = 0; } // checking if queue is empty bool isEmpty() { if (front == rear) return true; return false; } // checking if the queue is full bool isFull() { if ((rear + 1) % MAX_SIZE == front) return true; return false; } // enqueue operation void enqueue(int val) { if (this->isFull()) { printf("Queue Overflow!\n"); return; } rear = (rear + 1) % MAX_SIZE; arr[rear] = val; } // dequeue operation void dequeue() { if (this->isEmpty()) { printf("Queue Underflow!\n"); return; } front = (front + 1) % MAX_SIZE; } // peek function int peek() { if (this->isEmpty()) { printf("Queue is Empty!\n"); return -1; } return arr[(front + 1) % MAX_SIZE]; } // utility to print queue void print() { if (this->isEmpty()) return; for (int i = (front + 1) % MAX_SIZE; i < rear; i = (i + 1) % MAX_SIZE) { printf("%d ", arr[i]); } cout << arr[rear]; } }; // driver code int main() { Queue q; q.enqueue(11); q.enqueue(11); q.enqueue(11); q.enqueue(11); q.enqueue(11); q.enqueue(11); q.dequeue(); q.dequeue(); q.enqueue(123); q.print(); return 0; }...

C++ Program for Circular Linked List Queue Implementation

This C++ program demonstrates the implementation of a queue using a circular linked list. It includes operations to enqueue (add) and dequeue (remove) elements, as well as check if the queue is empty or full. The circular nature of the linked list ensures efficient use of memory by reusing nodes, without the use of any extra concept like in the array implementation...

Tags:
#CPP-DSA #C++ #CPP

Concept Behind Circular Queue

C++ Program to Implement Circular Queue Using Array