Implementation of Queue
Implementation of queue: We can implement the queue through the array and linked list. An array is the easiest way to implement the queue.
When a queue is created with the help of an array, the number of its elements is declared before processing. The beginning of the array becomes its "front" end, and the end of the array becomes its "rear" end. The terms "front" and "rear" are used to describe the linear list when implemented as a queue.
The "Front" stores the index of the first element in the queue. The "rear" stores the index of the last element in the queue. At any given time, the number of elements in a queue can be calculated from the values ??of "front" and "rear".
if front = 0 then number of elements = 0 else no of elements = front – rear + 1.
Enqueue operation
When you insert an element in the queue, that operation is called enqueue.
Algorithm of insert the element of the queue
Step 1: Before adding elements, it is checked whether the queue is full or not. Step 2: If the queue is full, it will print the "overflow error" message, and the program will terminate. Step 3: If the queue is not full, the value of the "rear" end will be increased by 1, and a new element will be added to the queue-array.
Insertion in a queue implemented as an array
if rear = NULL then { rear = front = 0 Queue [0] = ITEM } else if rear = N – 1 then { print “Queue full, overflow” } else { Queue [rear + 1] = ITEM rear = rear + 1 } END
Dequeue operation
When you remove an element from the queue, that operation is called dequeue.
Algorithm of insert the element of the queue
Step 1: Before removing elements, it is checked whether the queue is empty or not. Step 2: If the queue is empty, it will print the "underflow error" message, and the program will terminate. Step 3: If the queue is not empty, the value of the "front" end will be increased by 1, and an element will be removed in the queue-array.
Deletion in a queue implemented as an array
if front = NULL then { print “quere empty, underflow” } else { ITME = Queue[front] if front = rear then { front = rear = NULL } else { front = front + 1 } } END
Queue program in C language:
#include<stdio.h> #include<stdlib.h> #define maxsize 5 void insert(); void delete(); void display(); int front = -1, rear = -1; int queue[maxsize]; void main () { int choice; while(choice != 4) { printf("\n1.insert of element\n2.Delete of element\n3.Display the queue\n4.Exit\n"); printf("\nenter your choice = "); scanf("%d",&choice); switch(choice) { case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: exit(0); break; default: printf("\nenter valid choice??\n"); } } } void insert() { int item; printf("\nenter the element\n"); scanf("\n%d",&item); if(rear == maxsize-1) { printf("\n OVERFLOW \n"); return; } if(front == -1 && rear == -1) { front = 0; rear = 0; } else { rear = rear+1; } queue[rear] = item; printf("\n value inserted "); } void delete() { int item; if (front == -1 || front > rear) { printf("\n UNDERFLOW \n"); return; } else { item = queue[front]; if(front == rear) { front = -1; rear = -1 ; } else { front = front + 1; } printf("\n value deleted "); } } void display() { int i; if(rear == -1) { printf("\n empty queue\n"); } else { printf("\n printing values \n"); for(i=front;i<=rear;i++) { printf("\n%d\n",queue[i]); } } }
Output:
1.insert of element 2.Delete of element 3.Display the queue 4.Exit enter your choice = 1 enter the element 1 Value inserted 1.insert of element 2.Delete of element 3.Display the queue 4.Exit enter your choice = 1 enter the element 2 Value inserted 1.insert of element 2.Delete of element 3.Display the queue 4.Exit enter your choice = 2 value deleted 1.insert of element 2.Delete of element 3.Display the queue 4.Exit enter your choice = 3 printing values 2 1.insert of element 2.Delete of element 3.Display the queue 4.Exit enter your choice = 4