Problem Analysis
A collection is defined for users with a set of specific operations that can be performed on data elements. Queue is a collection of data elements having a specified set of operations.Grouping of a variable number of data elements that may or may not be related with each other but grouped together to solve a specific problem and operations performed on these data elements is done using a specific technique is called collection.
In queue data elements are stored in a sequence. Addition of new elements in a queue is done at one end and deletion of elements in a queue is done at the other end.
The end at which data elements are added is called Rear or rear of the queue and the end at which data elements are removed is called Front or front of the queue.
When a new element is added to the rear of the queue it is said that operation enqueue operation is performed. When an element is deleted from the queue at the the front of the queue it is said that operation dequeue is performed.
Queue is a data structure that has a special technique of addition and deletion of elements. This technique is termed as first-in-first-out (FIFO) data structure. The data structure that follows FIFO technique performs operation in the following manner – the element which is added first to the queue will be the first element to be deleted from the queue. A queue is implemented using linear data structure and elements are stored in a sequence.
An example of a queue is a line of people taking tickets at the ticket window. There exists three different types of queues:
- Circular Queue
- Priority Queue
- Double ended queue
Circular Queue
In a circular queue the last element is added to the first element of the queue. Circular queue is used to achieve efficient memory utilization. In a circular queue an element can be inserted into the queue even if the last position is full and the first element is empty.
Priority Queue
In the priority queue each element is given a priority. Operation in priority queue is done on the basis of associated priority to each element. Operation on higher priority elements is done first as compared to lower priority elements. Operation on elements having the same priority is done in the order in which they appear in the queue.
Deque (Double Ended Queue)
In double ended queue operation insertion and deletion can be performed from either end that is from the front of the queue and rear of the queue. That is it does not follow the FIFO (First In First Out) order.
Problem Description
Queue in C language can be implemented using Array or Linked List. In the solution to the problem Simple Queue, Circular Queue and Priority Queue are implemented using arrays.
Implementation of simple queue using array
Simple queue is implemented using an array and has three user denied functions – one for inserting an element, one for deleting an element and one for displaying an element of the queue.
When an element is inserted into the queue it checks for the condition that the element is full or not. If the array is full then an “array overflow” message is displayed to the user, otherwise rear is incremented and an element is inserted into the queue. If the front is at zero index then it is set to index.
To delement an element from the queue delete operation is performed or in program delete function is called. In delete operation the value of the front is checked. If the front is at 0 index then “Queue Underflow message is displayed” otherwise the queue element is deleted by incrementing the value of front. If only one element exists in the queue then after deleting it variable rear and front is set to 0.
Elements of queue are displayed to the user by using a for loop.
Implementation of Circular Queue using array
Circular queue is implemented using an array by declaring three user defined functions – one for inserting an element, one for deleting an element and one for displaying an element.
An element is inserted into the queue using the insert function. The value of front and rear is used to check the condition of overflow. Since it is a circular queue, a queue overflow condition is encountered when the value of front and rear is the same or when the value of front is 0 and value of rear is 9.
Being a circular queue the value of rear is set to 0 when the value of rear is 9(rear pointing to last index) otherwise value of rear is incremented and an element is inserted into the array.
To delete an element from the circular queue value of front is checked to check the condition of Underflow. If the front is pointing to the last element of the array then front is set to 0 otherwise front is incremented.
Elements of the array are displayed by display function. Being a circular queue front and rear can be pointing at different index positions denoting different conditions of the circular queue. These conditions are tackled in display function.
Implementing priority queue using array
Priority queue is implemented using two arrays – data queue array and priority queue array. Data queue array is used to store values and priority queue array is used to store priority for each element of the data queue.
In the priority queue the condition of overflow and underflow is checked as it is checked in a simple queue. The only difference in the simple queue and priority queue lies in the insertion and deletion operation. Insertion and deletion operation in priority queue is performed by checking priority associated to each element of the queue.
Solution to Problem
Following is the program to implement a simple queue using arrays.
C program to implement simple queue using array
#include<stdio.h> int qq[10]; int Q_rear = 0; int Q_front = 0; void Q_Insert(); void Q_Delete(); void Q_Display(); void Q_Insert() { int chh; printf("\n Please enter queue element :"); scanf("%d", &chh); if(Q_rear < 10) { Q_rear ++; qq[Q_rear] = chh ; if(Q_front == 0) Q_front = 1; } else printf("\n Queue Overflow encountered"); } void Q_Delete() { if (Q_front == 0) { printf("\n Queue Underflow Encountered"); return ; } else { printf("\n Queue Element deleted"); } if(Q_front == Q_rear) { Q_front = 0; Q_rear = 0; } else Q_front = Q_front + 1; } void Q_Display() //char q[]) { int i; if (Q_front == 0) return; for(i = Q_front ; i <= Q_rear; i++) printf(" %d ", qq[i]); } int main() { int kk = 0; int choice_1; do { printf("\n"); printf("1. Insert"); printf("\n"); printf("2. Delete"); printf("\n"); printf("3. Quit"); printf("\n"); printf("\nInput the choice : "); scanf("%d", &choice_1); switch(choice_1) { case 1 : Q_Insert(); printf("\n"); printf("\n Displaying Queue after inserting element "); Q_Display(); printf("\n"); break; case 2 : Q_Delete(); printf("\n"); printf("\n Displaying Queue content after deleteion : \n"); Q_Display(); break; case 3: printf("Quitting"); kk = 1; } } while(!kk); return 0; }
Output 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :10 Displaying Queue after inserting element 10 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :20 Displaying Queue after inserting element 10 20 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :30 Displaying Queue after inserting element 10 20 30 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :40 Displaying Queue after inserting element 10 20 30 40 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :50 Displaying Queue after inserting element 10 20 30 40 50 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :60 Displaying Queue after inserting element 10 20 30 40 50 60 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :70 Displaying Queue after inserting element 10 20 30 40 50 60 70 1. Insert 2. Delete 3. Quit Input the choice : 1 Please enter queue element :80 Displaying Queue after inserting element 10 20 30 40 50 60 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 20 30 40 50 60 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 30 40 50 60 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 40 50 60 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 50 60 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 60 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 70 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 80 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Element deleted Displaying Queue content after deletion : 1. Insert 2. Delete 3. Quit Input the choice : 2 Queue Underflow Encountered Displaying Queue content after deletion : 1. Insert 2. Delete 3. Quit Input the choice : 3 Quitting
Code Analysis Queue is a linear data structure. In Queue manipulation operations such as insertion and deletion are performed at either ends of the Queue. End at which insertion is performed is termed as “Rear” of Queue and end at which deletion is performed is termed as “Front” of Queue. Queue follows First In First Out (FIFO) order, that is, the First element to be inserted will be the first element to be deleted. Queue has two variables: Rear: It points to that end of Queue from where an element will be inserted into the Queue. Front: It points to that end of Queue from where an element will be deleted from the Queue. The above code uses three functions to perform three operations - insert, delete and display. These operations are performed using switch statements. This code asks the user to input a choice to perform operation insert, delete, and display. As per the choice of the user, a particular operation is performed using switch statements. Global variables Q_front and Q_rear are used to point to the first and last element of the Queue. Function void Q_Insert(); is used to insert elements in the Queue. Element is inserted by checking whether Queue is full or not, if it is full then message “Queue Overflow Encountered” is displayed. If Queue has space then a new element is added to Queue at the rear. Function void Q_Delete(); is used to delete elements from the Queue. Element deletion is done by checking three conditions - Queue is empty: This condition is checked by following programming instructions : if (Q_front == 0) Queue has one element: This condition is checked by following programming instructions: if(Q_front == Q_rear) Queue has more than one element: This condition is checked by else part of if(Q_front == Q_rear) and executed by following programming instructions: Q_front = Q_front + 1;
C Program to implement Circular Queue using array |
# include<stdio.h> int C_Q_arr[10]; int Q_front = -1; int Q_rear = -1; void Q_insert(int Q_item) { if((Q_front == 0 && Q_rear == 9) || (Q_front == Q_rear+1)) { printf("Queue Encountered Overflow \n"); return; } if (Q_front == -1) { Q_front = 0; Q_rear = 0; } else { if(Q_rear == 9) Q_rear = 0; else Q_rear = Q_rear+1; } C_Q_arr[Q_rear] = Q_item ; } void Q_del() { if (Q_front == -1) { printf("Queue Encountered Underflow\n"); return ; } printf("Element that will be deleted from queue is : %d\n",C_Q_arr[Q_front]); if(Q_front == Q_rear) { Q_front = -1; Q_rear=-1; } else { if(Q_front == 9) Q_front = 0; else Q_front = Q_front+1; } } void Q_display() { int Q_front_position = Q_front, Q_rear_position = Q_rear; if(Q_front == -1) { printf("Queue is Empty \n"); return; } printf("Queue elements are :\n"); if( Q_front_position <= Q_rear_position ) while(Q_front_position <= Q_rear_position) { printf("%d ",C_Q_arr[Q_front_position]); Q_front_position++; } else { while(Q_front_position <= 9) { printf("%d ",C_Q_arr[Q_front_position]); Q_front_position++; } Q_front_position = 0; while(Q_front_position <= Q_rear_position) { printf("%d ",C_Q_arr[Q_front_position]); Q_front_position++; } } printf("\n"); } int main() { int choice_1, Q_item; do { printf("1.Press 1 to Insert \n"); printf("2.Press 2 to Delete \n"); printf("3.Press 3 to Display\n"); printf("4.Press 4 to Quit\n"); printf("Please enter your choice : "); scanf("%d",&choice_1); switch(choice_1) { case 1 : printf("Enter element to insert in queue : "); scanf("%d", &Q_item); Q_insert(Q_item); break; case 2 : Q_del(); break; case 3: Q_display(); break; case 4: break; default: printf("You have entered wrong choice\n"); } }while(choice_1!=4); return 0; }
Output 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 10 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 20 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 30 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 40 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 50 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 60 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 70 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 80 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 1 Enter element to insert in queue : 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 10 20 30 40 50 60 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 10 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 20 30 40 50 60 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 20 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 30 40 50 60 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 30 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 40 50 60 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 40 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 50 60 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 50 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 60 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 60 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 70 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 70 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 80 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 80 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue elements are : 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 2 Element that will be deleted from queue is : 90 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 3 Queue is Empty 1.Press 1 to Insert 2.Press 2 to Delete 3.Press 3 to Display 4.Press 4 to Quit Please enter your choice : 4
Code Analysis The main difference between linear queue and circular queue is that in linear queue elements are inserted from the rear pointer only and deleted from front on the other hand in circular queue elements can be inserted and deleted from both the ends since the last element in circular queue is linked to the first element. Circular queue is more efficient than a linear queue. The condition that convert linear queue to circular queue is:
if(Q_rear == 9) Q_rear = 0; To insert an element in circular queue function Q_insert(int Q_item) is called. Queue overflow condition is checked using the following programming instructions: if((Q_front == 0 && Q_rear == 9) || (Q_front == Q_rear+1)) { printf("Queue Encountered Overflow \n"); return; } If the value of the queue front variable is 0 and queue rear variable is 9 or value of queue front variable is equal to queue rear variable than Queue is said to be overflow. If the queue is not initialized then the value of the front variable of the queue will be -1. If it is -1 then the queue variable front and queue variable raer will be set to 0, that is the first index of the array. Following is the programming instructions: if (Q_front == -1) { Q_front = 0; Q_rear = 0; } If the queue is initialized then the value of the queue variable rear is checked if its value is 9 (maximum index of the array) then the rear value is again set to 0. This is done since we are implementing a circular queue. If the value of queue variable rear value is not the maximum index of the array then it is not 9 then the rear is incremented and value is inserted into the array. This is done by following programming instructions: if(Q_rear == 9) Q_rear = 0; else Q_rear = Q_rear+1; C_Q_arr[Q_rear] = Q_item ; In the above program an element is deleted from the queue by calling the queue delete function. In the delete function queue underflow condition is checked by checking the value of queue variable front. If the variable front has value -1 then the queue is underflow. Programming instructions to check queue underflow condition is: if (Q_front == -1) { printf("Queue Encountered Underflow\n"); return ; } When it is found that the circular queue is not empty then it is checked that the circular queue has only one element. To check one element condition in a circular queue, the value of the queue variable front and rear is checked, if they are equal then there is only one element in the queue and the queue variable front and rear is set to -1. Programming instruction to achieve this is: if(Q_front == Q_rear) { Q_front = -1; Q_rear=-1; } If there is more than one element in the circular queue then the value of the queue variable front is checked if its value is maximum array size in this program 9 then front is set to the first element of the array this is done since we are implementing a circular queue. If the value of the queue variable is not 9 that is the maximum size of the array then the value of front is incremented. Following is the programming instructions to achieve this: else { if(Q_front == 9) Q_front = 0; else Q_front = Q_front+1; } To display all the elements of the queue display function is called. In the display function it is checked that Queue is empty or not. This is done by checking the value of the front variable, if the value of front is -1 then the circular queue is not initialized. This is done by executing following programming instructions: if(Q_front == -1) { printf("Queue is Empty \n"); return; } If the circular queue is not empty then using While loop queue elements are displayed. If the value of queue variable front is less than queue variable rear then it means that few elements are deleted from the circular queue and variable front has moved from array maximum index in the above program value 9 towards its lowest index size that is 0. This done by executing following programming instructions: if( Q_front_position <= Q_rear_position ) while(Q_front_position <= Q_rear_position) { printf("%d ",C_Q_arr[Q_front_position]); Q_front_position++; } If the value of the queue variables font is smaller than the maximum index of the array that is 9 then all the elements of the array are displayed till the queue variable front is equal to 9. When it is at 9 then the while loop terminates and since we are implementing circular queue queue variable front is set to 0. This is done by exciting following programming instructions: while(Q_front_position <= 9) { printf("%d ",C_Q_arr[Q_front_position]); Q_front_position++; } Q_front_position = 0; If queue variable front is less than queue variable rear than array elements are displayed using following programming instructions: while(Q_front_position <= Q_rear_position) { printf("%d ",C_Q_arr[Q_front_position]); Q_front_position++; }
C program to implement Priority Queue using array
#include<stdio.h> #define Num 40 int Priority_Q[Num],Pr_Q[Num]; int rr = -1,ff = -1; void Priority_Q_Insert(int data_1,int Q_p) { int h; if((ff==0)&&(rr==Num-1)) printf("Queue Overflow"); else { if(ff==-1) { ff = rr = 0; Pr_Q[rr] = data_1; Priority_Q[rr] = Q_p; } else if(rr == Num-1) { for(h=ff;h<=rr;h++) { Priority_Q[h-ff] = Priority_Q[h]; Pr_Q[h-ff] = Pr_Q[h]; rr = rr-ff; ff = 0; for(h = rr;h>ff;h--) { if(Q_p>Pr_Q[h]) { Priority_Q[h+1] = Priority_Q[h]; Pr_Q[h+1] = Pr_Q[h]; } else break; Priority_Q[h+1] = data_1; Pr_Q[h+1] = Q_p; rr++; } } } else { for(h = rr;h>=ff;h--) { if(Q_p>Pr_Q[h]) { Priority_Q[h+1] = Priority_Q[h]; Pr_Q[h+1] = Pr_Q[h]; } else break; } Priority_Q[h+1] = data_1; Pr_Q[h+1] = Q_p; rr++; } } } void Priority_Q_print() { int e; for(e=ff;e<=rr;e++) { printf("\nQueue Element = %d\tPriority of Queue Element = %d",Priority_Q[e],Pr_Q[e]); } } void Priority_Q_dequeue() { if(ff == -1) { printf("Queue Underflow"); } else { printf("Queue deleted Element is = %d\t Deleted element Priority = %d",Priority_Q[ff],Pr_Q[ff]); if(ff==rr) ff = rr = -1; else ff++; } } int main() { int option,nn,y,data_1,Q_p; printf("Please enter your choice:-"); do{ printf("\n\n1. Please press 1 to Insert the Data in Priority Queue\n\n2. Please press 2 to display Priority Queue Data \n\n3. Please Press 3 to Delete the data from the Priority Queue\n\n4. Please Press 0 to Exit\n"); scanf("%d",&option); switch(option){ case 1: printf("\nEnter the number of data to be inserted in the Priority Queue"); scanf("%d",&nn); printf("\nEnter Priority Queue data and its Priority "); y=0; while(y<nn) { printf("\n"); printf("Enter Priority Queue Data"); scanf("%d", &data_1); printf("\n"); printf("Enter Priority level of Priority Queue Data"); scanf("%d",&Q_p); printf("\n"); Priority_Q_Insert(data_1,Q_p); y++; } break; case 2: Priority_Q_print(); break; case 3: Priority_Q_dequeue(); break; case 0: printf("Quitting..."); break; default: printf("\nYou have entered incorrect choice"); } }while(option!=0); return 0; }
Output Please enter your choice:- 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 1 Enter the number of data to be inserted in the Priority Queue 1 3 Enter Priority Queue data and its Priority Enter Priority Queue Data10 Enter Priority level of Priority Queue Data1 Enter Priority Queue Data12 Enter Priority level of Priority Queue Data3 Enter Priority Queue Data14 Enter Priority level of Priority Queue Data2 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 1 Priority of Queue Element = 10 Queue Element = 12 Priority of Queue Element = 3 Queue Element = 14 Priority of Queue Element = 2 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue deleted Element is = 1 Deleted element Priority = 10 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 1 Enter the number of data to be inserted in the Priority Queue3 Enter Priority Queue data and its Priority Enter Priority Queue Data12 Enter Priority level of Priority Queue Data1 Enter Priority Queue Data13 Enter Priority level of Priority Queue Data2 Enter Priority Queue Data14 Enter Priority level of Priority Queue Data3 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 12 Priority of Queue Element = 3 Queue Element = 14 Priority of Queue Element = 3 Queue Element = 14 Priority of Queue Element = 2 Queue Element = 13 Priority of Queue Element = 2 Queue Element = 12 Priority of Queue Element = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 12 Priority of Queue Element = 3 Queue Element = 14 Priority of Queue Element = 3 Queue Element = 14 Priority of Queue Element = 2 Queue Element = 13 Priority of Queue Element = 2 Queue Element = 12 Priority of Queue Element = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue deleted Element is = 12 Deleted element Priority = 3 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 14 Priority of Queue Element = 3 Queue Element = 14 Priority of Queue Element = 2 Queue Element = 13 Priority of Queue Element = 2 Queue Element = 12 Priority of Queue Element = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue deleted Element is = 14 Deleted element Priority = 3 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 14 Priority of Queue Element = 2 Queue Element = 13 Priority of Queue Element = 2 Queue Element = 12 Priority of Queue Element = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue deleted Element is = 14 Deleted element Priority = 2 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 13 Priority of Queue Element = 2 Queue Element = 12 Priority of Queue Element = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue deleted Element is = 13 Deleted element Priority = 2 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 12 Priority of Queue Element = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue deleted Element is = 12 Deleted element Priority = 1 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 0 Priority of Queue Element = 0 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 3 Queue Underflow 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 2 Queue Element = 0 Priority of Queue Element = 0 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 4 You have entered incorrect choice 1. Please press 1 to Insert the Data in Priority Queue 2. Please press 2 to display Priority Queue Data 3. Please Press 3 to Delete the data from the Priority Queue 4. Please Press 0 to Exit 0 Quitting...
Code Analysis In the Priority Queue each data element has its own priority. Queue operations such as insert and delete are done on the basis of priority associated with each data element. Highest priority data is placed over lower priority data. In case of deletion, the element having highest priority is deleted first than lower priority data is deleted. For insertion operation in Priority Queue insertion function is called, the user is asked to enter data and its priority. In the insertion function to check the condition of overflow the value of front and rear is checked. If front is at 0 and rear at maximum array index then priority queue is overflow. This is done by executing following programming instructions:
if((ff==0)&&(rr==Num-1)) printf("Queue Overflow"); If the priority queue is not initialized then the value of front is -1 in this case priority queue variable front and rear are set to 0 and data element and priority value is inserted into the priority queue. This is done by executing following programming instructions: if(ff==-1) { ff = rr = 0; Pr_Q[rr] = data_1; Priority_Q[rr] = Q_p; } If in the priority queue data element already exists than new element is inserted into the priority queue by comparing its priority with the priorities already exists in the priority queue. If the variable rear is at maximum array index then the next element to be inserted will be on the basis of its priority. This is done by comparing priority in the if condition and shuffling the priority using the for loop. This is done by executing the following programming instructions:
if(rr == Num-1) { for(h=ff;h<=rr;h++) { Priority_Q[h-ff] = Priority_Q[h]; Pr_Q[h-ff] = Pr_Q[h]; rr = rr-ff; ff = 0; for(h = rr;h>ff;h--) { if(Q_p>Pr_Q[h]) { Priority_Q[h+1] = Priority_Q[h]; Pr_Q[h+1] = Pr_Q[h]; }
If the rear is not at maximum array index then shuffling of priority is done using for and if condition following which new data element is inserted. This is done by executing the following programming instructions:
for(h = rr;h>=ff;h--) { if(Q_p>Pr_Q[h]) { Priority_Q[h+1] = Priority_Q[h]; Pr_Q[h+1] = Pr_Q[h]; } else break; } Priority_Q[h+1] = data_1; Pr_Q[h+1] = Q_p; rr++;
Deletion in the priority queue is done by calling dequeue( ) function. In the dequeue function the value of variable front is checked if it is -1 than priority queue is empty. If the variable rear is not at -1 then the element from the priority is deleted. If only one element exists in the priority queue then it is checked using the if condition if(ff==rr) otherwise the element is deleted and the variable front is incremented. This is done by executing the following programming instructions:
if(ff == -1) { printf("Queue Underflow"); } else { printf("Queue deleted Element is = %d\t Deleted element Priority = %d",Priority_Q[ff],Pr_Q[ff]); if(ff==rr) ff = rr = -1; else ff++; }
Conclusion
The objective was to develop a C program to implement Queue using Array. The objective is achieved by developing a C program to implement a queue using arrays. Three type of queues are implemented – first, simple queue, second, circular queue and third, priority queue.
The difference between Simple Queue, Circular Queue and Priority Queue is given below.
Difference between Linear Queue, Circular Queue and Priority Queue | ||
Linear Queue | Circular Queue | Priority Queue |
Elements are inserted in the linear order one after another. | Elements are inserted in circular order so that the last element is linked to the first element. | Each element is given a priority. |
Insertion takes place at rear pointer only and deletion takes place from front pointer only. | Insertion and deletion can be performed at both ends of the queue. | Insertion and deletion takes place on the basis of priority associated with each element. |
Efficiency order of LInear Queue, Circular Queue and Priority Queue is as follows:
Circular Queue > Priority Queue > Linear Queue
Leave a Reply