Queues

‘Queue’ data structure is also known as ‘Last In Last Out’ (LILO) or ‘First In First Out’ (FIFO). Queue is an abstract data type where elements are kept in order on which following operations are performed:
 
i. Enqueue: adding an element to the queue from the rear terminal position
ii. Dequeue: removing element from the queue from the front terminal position
 
There is another function called ‘Peek’ can be used over queues. This function actually returns the element at the front terminal of the queue.
 
All these three functions have time complexity as O(1) since these functions act only at one end of the queue.
 
 

Following are other variants of queue:-

ii. Priority Queue
 
Queues can be implemented using:-
i. Doubly linked list (used more commonly since O(1) operations are possible at both the ends)
ii. Singly Linked list (little difficult implementation)
iii. Arrays
 
Applications of queue:
1. CPU scheduling
2. Job scheduling: First Come First Serverd
3. Inter-process asynchronous communication (data transfer): Pipes and Filters
4. Disk scheduling
5. Communications and Networking : network bridges, switches and routers in computer networks
 
Queue implementation using doubly linked list
 
Code:
 
#include "stdio.h"
#include "stdlib.h"
 
struct queue{
                int num;
                struct queue *next;
                struct queue *prev;
}*front, *rear;
 
int currentsize;
 
void Enqueue(){
                struct queue *ptr = (struct queue*)malloc(sizeof(struct queue));
                printf("\nEnter value to be enqueued into the queue: ");
                scanf("%d", &ptr->num);
                ptr->next = NULL;
                ptr->prev = NULL;
               
                if(front == NULL && rear == NULL){
                                /*queue is empty. hence front and rear pointers will be pointing to same element*/
                                front = ptr;
                                rear = ptr;
                }
                else{
                                /*queue is not empty. add element at the rear*/
                                ptr->next = rear;
                                rear->prev = ptr;
                                rear = ptr;
                }
                currentsize++;
}
 
void Dequeue(){
                if(front == NULL && rear == NULL){
                                /*queue is empty. cannot dequeue anything*/
                                printf("\nQueue is empty!!! Cannot perform dequeue opeartion");
                                return;
                }
                else{
                                /*queue is not empty.remove element from the front*/
                                if(front == rear){
                                                /*only one element in the queue*/
                                                printf("\n%d is dequeued from the queue", front->num);
                                                free(front);
                                                front = NULL;
                                                rear = NULL;
                                }
                                else{
                                                /*more than one element in the queue*/
                                                struct queue *temp = NULL;
                                                temp = front->prev;
                                                printf("\n%d is dequeued from the queue", front->num);
                                                free(front);
                                                front = temp;
                                                front->next = NULL;
                                }
                                currentsize--;
                }
}
 
void GetQueueData(){
                if(front == NULL && rear == NULL){
                                printf("\nError: queue is empty!!");
                }
                else{
                                struct queue *ptr = rear;
                                printf("\nQueue is as follows: \nREAR:");
                                while(ptr!=NULL){
                                                printf(" %d :", ptr->num);
                                                ptr = ptr->next;
                                }
                                printf(":FRONT");
                }
}
 
void Peek(){
                if(front == NULL && rear == NULL){
                                printf("\nError: queue is empty!!");
                }
                else{
                                printf("\nElement at the front of the queue is: %d", front->num);
                }
}
 
void main(){
               
                int option;
                char con, c;
               
                do{
                                struct queue *myqueue = NULL;
                                front = NULL;
                                rear = NULL;
                                currentsize = 0;
                               
                                do{
                                                printf("\n\nWhat do you want to do? : ");
                                                printf("\n1. Enqueue\n2. Dequeue\n3. Get size\n4. GetQueueData\n5. Peek\n6. Exit\nOption : ");
                                                scanf("%d", &option);
                                               
                                                switch(option){
                                                                case 1:
                                                                                Enqueue();
                                                                                break;
                                                                case 2:
                                                                                Dequeue();
                                                                                break;
                                                                case 3:
                                                                                printf("\nSize of the queue is %d", currentsize);
                                                                                break;
                                                                case 4:
                                                                                GetQueueData();
                                                                                break;
                                                                case 5:
                                                                                Peek();
                                                                                break;
                                                                case 6:
                                                                                goto exit;
                                                                                break;
                                                                default:
                                                                                break;  
                                                }             
                                }while(1);
                               
                                exit:      
                                printf("\nDo you want to continue (y/n) ?:");
                                getchar();
                                con = getchar();
                }while(con == 'y' || con == 'Y');
 
Output:
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 1
 
Enter value to be enqueued into the queue: 10
 
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 1
 
Enter value to be enqueued into the queue: 20
 
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 1
 
Enter value to be enqueued into the queue: 30
 
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 3
 
Size of the queue is 3
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 5
 
Element at the front of the queue is: 10
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 4
 
Queue is as follows:
REAR: 30 : 20 : 10 ::FRONT
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 2
 
10 is dequeued from the queue
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 4
 
Queue is as follows:
REAR: 30 : 20 ::FRONT
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 2
 
20 is dequeued from the queue
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 2
 
30 is dequeued from the queue
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 2
 
Queue is empty!!! Cannot perform dequeue opeartion
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 5
 
Error: queue is empty!!
 
What do you want to do? :
1. Enqueue
2. Dequeue
3. Get size
4. GetQueueData
5. Peek
6. Exit
Option : 6
 
Do you want to continue (y/n) ?:n

No comments :

Post a Comment