Queue Data Structure
Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Operations on Queue :
Enqueue : Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue : Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition
Front : Get the front item from queue.
Rear : Get the last item from queue.
Applications of Queue :
Queue is used when things don’t have to be processed immediately, but have to be processed in First In First Out order like Breadth First Search
Queue is used when a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
Queue is used when data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO
Implementation of Queue using Array
For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front.
Time complexity of all operations like enqueue(), dequeue(), isFull(), isEmpty(), front() and rear() is O(1). There is no loop in any of the operations.
Program Explanation :
In the function insert(), firstly check if the queue is full. If it is, then print the output as “Queue Overflow”. Otherwise take the number to be inserted as input and store it in the variable add_item. Copy the variable add_item to the array queue_array[] and increment the variable rear by 1.
In the function delete(), firstly check if the queue is empty. If it is, then print the output as “Queue Underflow”. Otherwise print the first element of the array queue_array[] and decrement the variable front by 1
#include#define MAX 50 int queue_array[MAX]; int rear = - 1; int front = - 1; main() { int choice; while (1) { printf("1.Insert element to queue \n"); printf("2.Delete element from queue \n"); printf("3.Display all elements of queue \n"); printf("4.Quit \n"); printf("Enter your choice : "); scanf("%d", &choice); switch (choice) { case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: exit(1); default: printf("Wrong choice \n"); } /*End of switch*/ } /*End of while*/ } /*End of main()*/ insert() { int add_item; if (rear == MAX - 1) printf("Queue Overflow \n"); else { if (front == - 1) /*If queue is initially empty */ front = 0; printf("Inset the element in queue : "); scanf("%d", &add_item); rear = rear + 1; queue_array[rear] = add_item; } } /*End of insert()*/ delete() { if (front == - 1 || front > rear) { printf("Queue Underflow \n"); return ; } else { printf("Element deleted from queue is : %d\n", queue_array[front]); front = front + 1; } } /*End of delete() */ display() { int i; if (front == - 1) printf("Queue is empty \n"); else { printf("Queue is : \n"); for (i = front; i <= rear; i++) printf("%d ", queue_array[i]); printf("\n"); } } /*End of display() */
Implementation of Queue using Linked List
When creating an empty queue , initialise front and rear to null.
As above insertion into the queue is done using the rear pointer and enqueue(), deletion is done using the dequeue() and front pointer.
#include
#include struct node { int info; struct node *ptr; }*front,*rear,*temp,*front1; int frontelement(); void enq(int data); void deq(); void empty(); void display(); void create(); void queuesize(); int count = 0; void main() { int no, ch, e; printf("\n 1 - Enque"); printf("\n 2 - Deque"); printf("\n 3 - Front element"); printf("\n 4 - Empty"); printf("\n 5 - Exit"); printf("\n 6 - Display"); printf("\n 7 - Queue size"); create(); while (1) { printf("\n Enter choice : "); scanf("%d", &ch); switch (ch) { case 1: printf("Enter data : "); scanf("%d", &no); enq(no); break; case 2: deq(); break; case 3: e = frontelement(); if (e != 0) printf("Front element : %d", e); else printf("\n No front element in Queue as queue is empty"); break; case 4: empty(); break; case 5: exit(0); case 6: display(); break; case 7: queuesize(); break; default: printf("Wrong choice, Please enter correct choice "); break; } } } /* Create an empty queue */ void create() { front = rear = NULL; } /* Returns queue size */ void queuesize() { printf("\n Queue size : %d", count); } /* Enqueing the queue */ void enq(int data) { if (rear == NULL) { rear = (struct node *)malloc(1*sizeof(struct node)); rear->ptr = NULL; rear->info = data; front = rear; } else { temp=(struct node *)malloc(1*sizeof(struct node)); rear->ptr = temp; temp->info = data; temp->ptr = NULL; rear = temp; } count++; } /* Displaying the queue elements */ void display() { front1 = front; if ((front1 == NULL) && (rear == NULL)) { printf("Queue is empty"); return; } while (front1 != rear) { printf("%d ", front1->info); front1 = front1->ptr; } if (front1 == rear) printf("%d", front1->info); } /* Dequeing the queue */ void deq() { front1 = front; if (front1 == NULL) { printf("\n Error: Trying to display elements from empty queue"); return; } else if (front1->ptr != NULL) { front1 = front1->ptr; printf("\n Dequed value : %d", front->info); free(front); front = front1; } else { printf("\n Dequed value : %d", front->info); free(front); front = NULL; rear = NULL; } count--; } /* Returns the front element of queue */ int frontelement() { if ((front != NULL) && (rear != NULL)) return(front->info); else return 0; } /* Display if queue is empty or not */ void empty() { if ((front == NULL) && (rear == NULL)) printf("\n Queue empty"); else printf("Queue not empty"); }
Priority Queue
Priority Queue is an extension of queue with following properties. Every item has a priority associated with it. An element with high priority is dequeued before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
Priority queue supports following operations.
insert(item, priority) : Inserts an item with given priority. It can be implemented by adding an item at end of array in O(1) time
getHighestPriority() : Returns the highest priority item. Operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time
deleteHighestPriority() : Removes the highest priority item. Operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back
Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time