 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 overflow
Print “Queue Overflow”
end Algorithm_Enqueue
end if
if (FRONT == -1)    //  Inserting in an Empty Queue
FRONT = REAR = 0
end if
else if (REAR == N - 1)   //  Inserting after the last element
REAR = 0
end if
else
REAR = REAR + 1   //  Increment REAR
end else
QUEUE [REAR]=  element
end Algorithm_Enqueue

Algorithm_Dequeue

if(FRONT == -1) //  Condition for underflow
Print “Queue Underflow”
end Dequeue
end if
Temp = QUEUE[FRONT] // Copy FRONT in a temporary variable
if(FRONT == REAR) // The queue contains only one node
FRONT = REAR   = -1
end if
else if (FRONT == N - 1) // If FRONT is the last node
front = 0 // Make FRONT as the first node
end if
else
FRONT = FRONT + 1 // Increment FRONT
end else
end 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;
else
return 0;
}

/* Function to check if the queue is empty */
int empty()
{
if(st.front == -1)
return 1;
else
return 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;
else
st.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 Queue
FRONT = REAR = newNode
end if
else
REAR -> next = newNode //  Inserting after the last element
REAR = newNode
end else
REAR -> next = FRONT
end Algorithm_Enqueue

Algorithm_Dequeue

if(FRONT == NULL) //  Condition for underflow
Print “Queue Underflow”
end Dequeue
end if

else if(FRONT == REAR) // The queue contains only one node
temp = FRONT -> data
free(temp)
FRONT = FRONT -> next
REAR -> next = FRONT
end if
else if (FRONT == N - 1) // If FRONT is the last node
front = 0 // Make FRONT as the first node
end if
end 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 node
rear -> next = front;
delete temp;
}
return x;
}

/* Function to check if the queue is empty */
int empty()
{
if(front == NULL)
{
return 1;
}
else
return 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());
else
printf("\nEMPTY QUEUE\n");
break;
case 3:
display();
break;
default: exit(0);
}}
return 0;
}

OUTPUT

Enqueue elements Display elements Dequeue elements POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

2    3