Give an interface definition for an abstract data type 'Queue'. The queue is to be implemented in an array in a circular fashion. Give algorithms for each function defined in the interface of the queue.

I. Introduction

A Queue is an abstract data type (ADT) that follows a First-In-First-Out (FIFO) methodology for the operations performed on it. This means that the element that is added first will be the one to be removed first.

A circular queue is a type of queue in which the last element points to the first element making a circular link. It is also called 'Ring Buffer'. In a normal Queue, we can insert elements until the queue becomes full. But once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. This problem is overcome by using a circular queue.

II. Interface Definition

The interface for the Queue ADT is defined as follows:

1. enqueue(int data): This function is used to add an element to the end of the queue.
2. dequeue(): This function is used to remove an element from the front of the queue.
3. isFull(): This function checks if the queue is full.
4. isEmpty(): This function checks if the queue is empty.
5. peek(): This function returns the element at the front of the queue without removing it.

III. Algorithms for each function

1. enqueue(int data):

   • Step 1: Check if the queue is full. If (rear + 1) % size == front, then the queue is full. Return an error message.
   • Step 2: If the queue is not full, add the new element at the end of the queue. rear = (rear + 1) % size; queue[rear] = data;
   • Step 3: If the front pointer is -1, then change the front pointer to 0. if(front == -1) front = 0;

2. dequeue():

   • Step 1: Check if the queue is empty. If front == -1, then the queue is empty. Return an error message.
   • Step 2: If the queue is not empty, remove the element at the front of the queue. int temp = queue[front];
   • Step 3: If the front pointer is equal to the rear pointer, reset the front and rear pointers to -1. if(front == rear) front = rear = -1;
   • Step 4: Else, move the front pointer to the next position. else front = (front + 1) % size;
   • Step 5: Return the removed element. return temp;

3. isFull():

   • Return true if (rear + 1) % size == front, else return false.

4. isEmpty():

   • Return true if front == -1, else return false.

5. peek():

   • Return the element at the position pointed by the front pointer. return queue[front];

IV. Program Implementation

Here is a simple implementation of a circular queue in C++:

class Queue {
   int size;
   int front;
   int rear;
   int* queue;

   public:
   Queue(int size) {
      front = -1;
      rear = -1;
      this->size = size;
      queue = new int[size];
   }

   void enqueue(int data) {
      if((rear + 1) % size == front) {
         cout << "Queue is Full\n";
         return;
      }
      else {
         rear = (rear + 1) % size;
         queue[rear] = data;
         if(front == -1) {
            front = 0;
         }
      }
   }

   int dequeue() {
      if(front == -1) {
         cout << "Queue is Empty\n";
         return -1;
      }
      else {
         int temp = queue[front];
         if(front == rear) {
            front = rear = -1;
         }
         else {
            front = (front + 1) % size;
         }
         return temp;
      }
   }

   bool isFull() {
      return (rear + 1) % size == front;
   }

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

   int peek() {
      if(front != -1) {
         return queue[front];
      }
      else {
         return -1;
      }
   }
};

V. Examples

Here are some examples of how each function in the interface can be used:

int main() {
   Queue q(5);

   // Enqueue elements
   q.enqueue(1);
   q.enqueue(2);
   q.enqueue(3);
   q.enqueue(4);
   q.enqueue(5);

   // Dequeue elements
   cout << q.dequeue() << "\n";
   cout << q.dequeue() << "\n";

   // Check if the queue is full
   if(q.isFull()) {
      cout << "Queue is full\n";
   }
   else {
      cout << "Queue is not full\n";
   }

   // Check if the queue is empty
   if(q.isEmpty()) {
      cout << "Queue is empty\n";
   }
   else {
      cout << "Queue is not empty\n";
   }

   // Peek at the front element
   cout << "Front element: " << q.peek() << "\n";

   return 0;
}

This program will output:

1
2
Queue is not full
Queue is not empty
Front element: 3

Summary

A Queue is an abstract data type (ADT) that follows a First-In-First-Out (FIFO) methodology for the operations performed on it. This means that the element that is added first will be the one to be removed first. A circular queue is a type of queue in which the last element points to the first element making a circular link. It is also called 'Ring Buffer'. The interface for the Queue ADT includes functions like enqueue, dequeue, isFull, isEmpty, and peek. The enqueue function adds an element to the end of the queue, the dequeue function removes an element from the front of the queue, the isFull function checks if the queue is full, the isEmpty function checks if the queue is empty, and the peek function returns the element at the front of the queue without removing it.

Analogy

A queue is like a line of people waiting for a bus. The person who arrives first gets on the bus first, and the person who arrives last gets on the bus last. A circular queue is like a carousel ride at an amusement park. The last person in line gets on the ride and then comes back to the front of the line to ride again.