# Circular queue using arrays and Linked list | Circular queue data structure

A circular queue is similar to the simple queue except that, the last node is connected to the first node to make a circle. A circular queue also called as a Ring Buffer can be implemented using arrays and linked lists. Let us look at its implementation one by one.

## Algorithm for Insertion and deletion operation using arrays in a circular queue

### Algorithm_Enqueue

`if (((FRONT == 0) and (REAR == N - 1)) or (REAR == FRONT - 1)) //  Condition for overflowPrint “Queue Overflow”end Algorithm_Enqueueend ifif (FRONT == -1)    //  Inserting in an Empty QueueFRONT = REAR = 0end ifelse if (REAR == N - 1)   //  Inserting after the last elementREAR = 0end ifelse REAR = REAR + 1   //  Increment REARend elseQUEUE [REAR]=  element     end Algorithm_Enqueue`

### Algorithm_Dequeue

`if(FRONT == -1) //  Condition for underflowPrint “Queue Underflow”end Dequeueend ifTemp = QUEUE[FRONT] // Copy FRONT in a temporary variableif(FRONT == REAR) // The queue contains only one nodeFRONT = REAR   = -1end ifelse if (FRONT == N - 1)  // If FRONT is the last nodefront = 0   // Make FRONT as the first nodeend ifelseFRONT = FRONT + 1  //  Increment FRONTend elseend Dequeue`

## Program for implementation of circular queue using array in C

`#include <stdio.h>#include <stdlib.h># define N 5/* Structure for queue with array size and pointers */struct queue{int s[N];int front,rear;}st;/* Function to check if the queue is full */int full(){if(((st.front == 0) and (st.rear == N - 1)) or (st.rear == st.front -1))return 1;elsereturn 0;}/* Function to check if the queue is empty */int empty(){if(st.front == -1)return 1;elsereturn 0;}/* Function to insert elements in a queue */void enqueue(int num){if(full()){printf("\nQUEUE IS FULL\n");}else{if(st.front == -1){st.front = 0;}st.rear = ((st.rear + 1) % N);st.s[st.rear]=num;}}/* Function to delete elements in a queue */int dequeue(){int x;if(empty()){printf("\nQUEUE IS EMPTY\n");}else{x = st.s[st.front];if(st.front==st.rear)st.front=st.rear=-1;elsest.front = ((st.front + 1) % N);}printf("\nDequeued Element : %d",x);}/* Function to display the elements in the queue */void display(){int i;if(empty())printf("\nEMPTY QUEUE\n");else{printf("\nFRONT INDEX : %d ",st.front);printf("\nQUEUE ELEMENTS : ");for(i=st.front;i!=st.rear;i = ((i+1)%N))printf("%d ",st.s[i]);printf("%d ",st.s[i]);printf("\nREAR INDEX : %d \n",st.rear);}}/* Main function */int main(){int num,choice;st.front = st.rear = -1;while(1){printf("\n\nQUEUE OPERATIONS\n\n1.ENQUEUE\n2.DEQUEUE\n3.DISPLAY\n\n");scanf("%d",&choice);switch (choice){case 1:if(full()){printf("\nQUEUE IS FULL\n");}else{printf("\nEnter item : ");scanf("%d",&num);enqueue(num);}break;case 2:if (empty()){printf("\nEMPTY QUEUE\n");}else{dequeue();}break;case 3:display();break;default: exit(0);}}return 0;}`

OUTPUT

Enqueue elements

Display elements

Dequeue elements

Display elements

## Algorithm for Insertion and deletion operation using linked list in a circular queue

### Algorithm_Enqueue

`if (FRONT == NULL)    //  Inserting in an Empty QueueFRONT = REAR = newNodeend ifelse    REAR -> next = newNode   //  Inserting after the last elementREAR = newNode end elseREAR -> next = FRONTend Algorithm_Enqueue`

### Algorithm_Dequeue

`if(FRONT == NULL) //  Condition for underflowPrint “Queue Underflow”end Dequeueend ifelse if(FRONT == REAR) // The queue contains only one nodetemp = FRONT -> datafree(temp)FRONT = FRONT -> nextREAR -> next = FRONTend ifelse if (FRONT == N - 1)  // If FRONT is the last nodefront = 0   // Make FRONT as the first nodeend ifend Dequeue`

## Program for implementation of circular queue using linked list in C

`#include <stdio.h>#include <stdlib.h>/* Structure for creating node and pointer */struct node{int data;struct node *next;} *rear,*front,*temp,*newNode;/* Initialising the pointers in the linked list */void create(){front = rear = NULL;}/* Function to insert elements in a circular queue */void enqueue(int data){newNode = (struct node*) malloc(sizeof(struct node));newNode -> data = data;newNode -> next = NULL;if(front == NULL)front = rear = newNode;else{rear -> next = newNode;rear = newNode;}rear -> next = front;   // rear always points to the front}/* Function to delete an element from the circular queue */int dequeue(){int x;if (front == NULL){return -1; //for empty queue}else if (front == rear) // Queue has only a single node{x = front->data;delete front;front = rear = NULL;}else{node *temp = front;x = temp -> data;front = front -> next;// Make rear point to the front noderear -> next = front;delete temp;}return x;}/* Function to check if the queue is empty */int empty(){if(front == NULL){return 1;}elsereturn 0;}/* Function to print the elements in the circular queue */void display(){node *temp = front;printf("\nCIRCULAR QUEUE : ");do{printf("%d ",temp->data);temp = temp->next;}while (temp != front);}/* Main function */int main(){int num,choice;while(1){printf("\n\nQUEUE OPERATIONS\n\n1.ENQUEUE\n2.DEQUEUE\n3.DISPLAY\n\n");scanf("%d",&choice);switch (choice){case 1:printf("\nEnter item : ");scanf("%d",&num);enqueue(num);break;case 2:if(!(empty()))printf("\nDequeued element : %d",dequeue());elseprintf("\nEMPTY QUEUE\n");break;case 3:display();break;default: exit(0);}}return 0;}`

OUTPUT

Enqueue elements

Display elements

Dequeue elements

### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`