Saturday, September 21, 2024

Priority Queue

Priority queue:- It is a special type of queue which stores group of elements. Each element has a priority number associated with it. Priority queue is an ADT (Abstract Data Type) which is like a regular queue or data structure but it will provide services on the basis of priority of an element.

यह एक विशेष प्रकार का क्यू होता है जो एलिमेंट्स का समूह रखता है। प्रत्येक एलिमेंट से एक प्रायोरिटी नंबर संलग्न होता है। प्रायोरिटी क्यू एक ADT है जो एक सामान्य क्यू या डाटा स्ट्रक्चर के समान है परंतु यह एलिमेंट की प्रायोरिटी (प्राथमिकता) के आधार पर सुविधा प्रदान करता है।

Rules of Priority Queue-
प्रायोरिटी क्यू के नियम-
1. Element which has higher priority will be inserted and deleted before other elements which has lower priority.
वह एलिमेंट जिसकी प्रायोरिटी अधिक होती है अन्य कम प्रायोरिटी एलिमेंट्स की तुलना में पहले इन्सर्ट एवं डिलीट किया जावेगा।

2. If two or more element has same priority then we follow FCFS (first come first serve) approach in which elements are deleted in order of their insertion in queue.
यदि दो या अधिक एलिमेंट की प्रायोरिटी एकसमान है तब हम FCFS(फर्स्ट कम फर्स्ट सर्व) युक्ति का प्रयोग करते है अर्थात जिस क्रम में एलिमेंट क्यू में इन्सर्ट होता है उसी क्रम में डिलीट होगा।

Operations performed in Priority Queue - 
प्रायोरिटी क्यू पर किये जाने वाले आपरेशन निम्न है-
1. Insertion with priority (इंसर्शन विथ प्रायोरिटी):- add an element to the queue with an associated priority.
एक एलिमेंट को उसकी प्रायोरिटी के अनुसार क्यू में जोड़ना।

2. Delete highest priority element(डिलीट हाईएस्ट प्रायोरिटी एलिमेंट):- remove the element from queue that has the highest priority and written it.
सबसे उच्च प्रायोरिटी एलिमेंट को क्यू से निकलना एवं लिखना।

Example:- In computer system, a priority queue is maintained by long term and short term scheduler which is also known as process queue. Here each process will execute on the basis of its priority like first of all interrupt then system process then resource request and at the end normal user process will be executed.
उदाहरण:- कंप्यूटर साइंस में लांग टर्म एवं शार्ट टर्म शेड्यूलर द्वारा प्रायोरिटी क्यू तैयार किया जाता है। इसे प्रोसेस क्यू कहा जाता है, जिसके आधार पर प्रोसेस को एक्सीक्यूट किया जाता है। अर्थात सर्वप्रथम इनट्ररप्ट इसके पश्चात सिस्टम प्रोसेस उसके बाद रिसोर्स रिक्वेस्ट एवं अंत मे सामान्य यूजर प्रोसेस को रन किया जता है।

Priority queue is mainly used in binary search tree, heap data structure, bucket queue, Dijkstra's algorithm, Huffman coding, best first search algorithm and prim's algorithm for minimum spanning tree etc.
प्रायोरिटी क्यू का प्रयोग मुख्यतः बाइनरी सर्च ट्री , हीप डेटा स्ट्रक्चर, बकेट क्यू , डिजक्सट्रा अल्गोरिथम , हुफमन कोडिंग, ब्रेड्थ फर्स्ट सर्च अल्गोरिथम एवं मिनिमम स्पांनिंग ट्री की प्राइम अल्गोरिथम इत्यादि में किया जाता है।

C Program to implement Priority Queue:-

#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int pri_que[MAX];
int front=-1, rear=-1;

void insert_by_priority(int item){
    if (rear >= MAX - 1)
    {
        printf("overflow condition\n");
        getch();     
        return;
    }
    if ((front == -1) && (rear == -1))
    {
        front++;
        rear++;
        pri_que[rear] = item;
        return;
    } 
    else
        checkpriority(item);
    rear++;
}

/* Function to check priority of an item */
void checkpriority(int item)
{
    int i,j;

    for (i = 0; i <= rear; i++)
    {
        if (item >= pri_que[i])
        {
            for (j = rear + 1; j > i; j--)
            {
                pri_que[j] = pri_que[j - 1];
            }
            pri_que[i] = item;
            return;
        }
    }
    pri_que[i] = item;
}


void delete_by_priority(int item)
{
    int i;

    if ((front==-1) && (rear==-1))
    {
        printf("\nQueue is empty no elements to delete");
        return;
    }

    for (i = 0; i <= rear; i++)
    {
        if (item == pri_que[i])
        {
            for (; i < rear; i++)
            {
                pri_que[i] = pri_que[i + 1];
            }

        pri_que[i] = -99;
        rear--;

        if (rear == -1)
            front = -1;
        return;
        }
    }
    printf("\n%d not found in queue to delete", item);
}


void display_pqueue()
{
    if ((front == -1) && (rear == -1))
    {
        printf("\nQueue is empty");
        return;
    }

    for (; front <= rear; front++)
    {
        printf(" %d ", pri_que[front]);
    }

    front = 0;
}


void main()
{
    int n, ch;

    printf("\nPriority Queue Operations:- \n 1. Insert an element into queue\n2. Delete an element from queue\n3. Display queue elements\n4. Exit");
    while (1)
    {
        printf("\nEnter your choice : "); 
        scanf("%d", &ch);

        switch (ch)
        {
        case 1:
            printf("\nEnter value to be inserted : ");
            scanf("%d",&n);
            insert_by_priority(n);
            break;
        case 2:
            printf("\nEnter value to delete : ");
            scanf("%d",&n);
            delete_by_priority(n);
            break;
        case 3:
            display_pqueue();
            break;
        case 4:
            exit(0);
        default:
            printf("\nWrong Choice, Try Again !!");
        }
    }
}

Double Ended Queue or Dequeue or Deque or head tail linked list

Double ended queue:- It is a special type of queue in which user can perform insertion and deletion operation at both ends of queue. Double ended queue is also known as Deque/ Dequeue/ head-tail linked list. Double ended queue is ADT. It means operations performed on double ended queue are pre-defined(fixed).We can use array and linked list representation for double ended queue. Double ended queue is mainly used in job scheduling algorithm like Steal. 

यह क्यू का एक विशेष प्रकार है जिसमे यूजर इंसर्शन एवं डिलीशन ऑपरेशन क्यू के दोनों छोर से कर सकता है डबल एंडेड क्यू को डी क्यू / हेड-टेल लिंक्ड लिस्ट के नाम से भी जाना जाता है। डबल एंडेड क्यू एक ADT है, अर्थात इस पर किये जाने वाले आपरेशन पूर्व निर्धारित होते है। हम अरे या लिंक्ड लिस्ट रिप्रजेंटेशन का प्रयोग कर डबल एंडेड क्यू को मेमोरी में संग्रहित कर सकते है। यह मुख्यत: जॉब शेडूलींग अल्गोरिथम में प्रयुक्त किया जाता है जैसे - स्टील ।   






Double ended queue is of following two types-
डबल एंडेड क्यू दो प्रकार का होता है-
1. Input restricted dequeue (इनपुट रिस्ट्रिक्टेड डी क्यू)
2. Output restricted dequeue (आउटपुट रिस्ट्रिक्टेड डी क्यू)

1. Input restricted double ended queue:- a double ended queue in which deletion operation will performed on both ends of queue but insertion operation will performed at only one end (rear1) of queue is called input restricted double ended queue.
एक डबल एंडेड क्यू जिसमे डिलीशन ऑपरेशन क्यू के दोनों छोर से किया जा सकता है परन्तु इंसर्शन ऑपरेशन केवल एक छोर(rear1) से किया जा सकता है, इनपुट रिस्ट्रिक्टेड डी क्यू कहलाता है।






2. Output restricted double ended queue:- a double ended queue in which insertion operation will performed at both ends of queue, but deletion operation will performed at only one end (front1) of queue is called output restricted double ended queue.
एक डबल एंडेड क्यू जिसमे इंसर्शन ऑपरेशन क्यू के दोनों छोर से किया जा सकता है परन्तु डिलीशन ऑपरेशन केवल एक छोर(front1) से किया जा सकता है, आउटपुट रिस्ट्रिक्टेड डी क्यू कहलाता है।






Operations performed on Dequeue are as follows:-
डी क्यू पर किये जाने वाले ऑपरेशन निम्न है:- 
1. Insert element at back(rear)
2. Insert element at front
3. Remove last element
4. Remove first element
5. Examine last element
6. Examine first element

C Program to implement Dequeue:-

#include<stdio.h>
#include<conio.h>
#define N 100
int queue[N];
int rear =0, front =0;
void display();
void insertEnd(int);
void insertStart(int);
void insert(int);
int delStart();
int delEnd();
int main()
{
    char ch , a='y';
    int choice, c, item;
    printf("Enter your choice for which deque operation you want to perform operation \n");
     do
     {
          printf("\n1.Input-restricted deque \n");
          printf("2.output-restricted deque \n");
          printf("\nEnter your choice for the operation : ");
          scanf("%d",&c);
          switch(c)
          {
               case 1:
                    printf("\nDo operation in Input-Restricted c deque\n");
                    printf("1.Insert");
                    printf("\n2.Delete from end");
                    printf("\n3.Delete from begning");
                    printf("\n4.show or display");
                    do
                   {
                   printf("\nEnter your choice for the operation in c deque: ");
                   scanf("%d",&choice);
                   switch(choice)
                   { 
                       case 1: insertEnd(item);
                       display();
                       break;
                       case 2: item=delEnd();
                       printf("\nThe item deleted is %d",item);
                       display();     
                       break;
                       case 3: item=delStart();
                       printf("\nThe item deleted is %d",item);
                       display();
                       break;
                       case 4: display();
                       break;
                       default:printf("Wrong choice");
                       break;
                   }
                   printf("\nDo you want to continue(y/n) to do operation in input-restricted c deque: ");
                   ch=getch();
                   }       
                   while(ch=='y'||ch=='Y');
                   getch();
                   break;
    
               case 2 :
                   printf("\nDo operation in Output-Restricted c deque\n");
                   printf("1.Insert at the End");
                   printf("\n2.Insert at the begning");
                   printf("\n3.Delete the element");
                   printf("\n4.show or display");
                   do
                   {
                   printf("\nEnter your choice for the operation: ");
                   scanf("%d",&choice);
                   switch(choice)
                       { 
                       case 1: insertEnd(item);
                       display();
                       break;
                       case 2: insertStart(item);
                       display();
                       break;
                       case 3: item=delStart();
                       printf("\nThe item deleted is %d",item);
                       display();     
                       break;
                       case 4: display();
                       break;
                       default:printf("Wrong choice");
                       break;
                       }
                   printf("\nDo you want to continue(y/n):");
                   ch=getch();
                   }       
                   while(ch=='y'||ch=='Y');
                   getch();
                   break ;
          }
    
     printf("\nDo you want to continue(y/n):");
                   ch=getch();
                   }       
                   while(ch=='y'||ch=='Y');
                   getch();
}

void display()
{
     int i;
     printf("\nThe queue elements are:");
     for(i=rear;i<front;i++)
     {
           printf("%d  ",queue[i]);
     }
}

void insertEnd(int item)
     char a;
     if(front==N/2)
      {
            printf("\nQueue full\nyou cant enter more elements at the end of c queue");
            return;
      }
      do
      {
            printf("\nEnter the item to be inserted:");
            scanf("%d",&item);
            queue[front]=item;
            front=front+1;
            printf("do you want to continue insertion Y/N");
            a=getch();
      }
      while(a=='y');
}

void insertStart(int item)
     char a;
     if(front==N/2)
      {
            printf("\nQueue full\nyou cant enter more elements at the start of queue");
            return;
      }
      do
      {
            printf("\nEnter the item to be inserted:");
            scanf("%d",&item);
            rear=rear-1;
            queue[rear]=item;
            printf("do you want to continue insertion Y/N");
            a=getch();
      }
      while(a=='y');
}

int delEnd()
{
     int t;
     if(front==rear)
     {
            printf("\nQueue empty");
            return 0;
     }
     front=front-1;
     t=queue[front+1];
     return t;
}

int delStart()
{
     int t;
     if(front==rear)
     {
            printf("\nQueue empty");
            return 0;
     }
     rear=rear+1;
     t=queue[rear-1];
     return t;
}

Applications of Queue

 Queues are useful for following applications:-

क्यू का प्रयोग, निम्न अनुप्रयोगो हेतु किया जाता है :-

1.) In network printer or printer server , A queue is used to schedule different printing jobs so that a job which is submitted earlier will be printed earlier. It provides services to all the nodes, connected in the network. So, It utilizes printing device and saving money of user.
नेटवर्क प्रिंटर या प्रिंटर सर्वर में क्यू का प्रयोग विभिन्न जॉब्स को शेडुल करने के लिए किया जाता है जिससे एक जॉब जो पहले क्यू में प्रवेश करती है पहले प्रिंट की जाती है। यह नेटवर्क से जुड़े सभी नोड को सुविधा प्रदान करने का कार्य करता है जिससे प्रिंटिंग डिवाइस  का प्रभावी उपयोग होता है एवं यूजर के पैसो की बचत होती है।     

2.) In simulation of Airport/ Railway station etc we can use different queues for passengers information, ticket reservation, seat allotment, flight/train information, runway/ track details etc. it requires 100% accuracy, which is not possible manually.
एअरपोर्ट एवं रेलवे स्टेशन के सिमुलेशन में अलग अलग जानकारियां रखने के लिए क्यू का प्रयोग किया जाता है जैसे - पैसेंजर की जानकारी, टिकेट रिजर्वेशन, सीट अलोटमेंट, फ्लाइट या ट्रेन की जानकारी, रनवे या ट्रैक की जानकारी इत्यादि। यहाँ 100% शुद्धता की आवश्यकता होती है जो व्यक्तिगत रूप से संभव नहीं है। 

3.) In Round Robin Scheduling , we use queue for scheduling different processes and allocate time slice of CPU to them for execution. In addition queue is used in-
राउंड रोबिन शेडुलिंग में हम क्यू का प्रयोग प्रोसेसेज को व्यवस्थित करने के लिए करते है जिससे उन्हें सी.पी.यू का टाइम स्लाइस प्रदान कर, रन किया जा सके।  इसके अतिरिक्त क्यू का प्रयोग-

4.) Breadth first search. ब्रेड्थ फर्स्ट सर्च, 
5.) Input Output Buffers, Keyboard buffer. इनपुट आउटपुट बफर, कीबोर्ड बफर, 
6.) CPU scheduling, Disk Scheduling. सी.पी.यू. शेडुलिंग, डिस्क शेडुलिंग, 
7.) In recognizing palindrome. पेलिंडरोम की जाँच, 
8.) In Shared resources management etc. शेयर्ड रिसोर्सेज के प्रबंधन इत्यादि में किया जाता है।  

Circular Queue Data Structure, C or C++ Program for Insertion, Deletion and Traversing Operations of Circular Queue.

 Circular Queue:-

Circular queue is a special type of queue in which last position and first position are assumed as adjacent position. It means in circular queue first position will occur after last position. It is a linear data structure. It is collection of ordered data elements. It is also known as FIFO system or FCFS system. It means an element which is inserted first will be deleted first. Here data elements will be inserted from one end of queue called rear and deleted from the other end called front. We can use Array or Linked list representation to store circular queue in memory.  Hence, we assume first and last position are adjacent in circular queue and resolve this problems of linear/static queue. It is more effective technique than physical queue.
सर्कुलर क्यू एक विशेष प्रकार का क्यू होता है जिसमे फर्स्ट और लास्ट पोजीशन को एक दुसरे के नजदीक(आस-पास) माना जाता है  अर्थात लास्ट पोजीशन के बाद हमेशा फर्स्ट पोजीशन आती है। यह एक लीनियर डाटा स्ट्रक्चर है। यह क्रमबद्ध डाटा एलेमेंट्स का संग्रह है। इसे FIFO (फर्स्ट इन फर्स्ट आउट) या FCFS (फर्स्ट कम फर्स्ट सर्व) सिस्टम के नाम से भी जाना जाता है अर्थात सर्कुलर क्यू में यदि किसी एलिमेंट को सबसे पहले इन्सर्ट किया जाता है, तब उसे ही सबसे पहले डिलीट किया जाता है। यहाँ एलिमेंट का इंसर्शन क्यू के रियर छोर पर तथा डिलीशन फ्रंट छोर से किया जाता है। हम अरे एवं लिंक्ड लिस्ट में से किसी एक का प्रयोग कर मेमोरी में सर्कुलर क्यू तैयार कर सकते है। सर्कुलर क्यू में मेमोरी का प्रभावी उपयोग होता है अत: फर्स्ट और लास्ट पोजीशन को एक दुसरे के नजदीक(आस-पास) मानकर, हम लीनियर क्यू की समस्या को हल कर सकते है। यह फिजिकल क्यू की तुलना में अधिक विश्वसनीय होता है।    
Circular Queue


Operations performed on circular queue are as follows:-
सर्कुलर क्यू पर किये जाने वाले ऑपरेशन निम्न है- 

1.) Insertion:- 
To add new element in cqueue is called insertion operation. This work is done on rear of circular queue. If front=0 and rear=N-1 or front=rear+1, It means cqueue is full and insertion operation is performed, then overflow condition will occur. If first element is inserted in cqueue then set front=rear=0. If rear=N-1 and front != 0, then we set rear=0 otherwise rear is increased by 1.
सर्कुलर क्यू में किसी नए एलिमेंट को जोड़ना, इंसर्शन ऑपरेशन कहलाता है। यह कार्य सर्कुलर क्यू के रियर पर किया जाता है यदि rear=N-1 अर्थात क्यू फुल हो एवं इंसर्शन ऑपरेशन किया जाये, तब ओवरफ्लो कंडीशन उत्पन्न होती है। यदि क्यू में पहले एलिमेंट का इंसर्शन किया जाता है तब front=rear=0 सेट किया जाता है। यदि rear=N-1 है एवं front !=0 तब rear=0 सेट किया जाता है अन्यथा रियर को एक से बढाया जाता है। 

2.) Deletion:- To remove/ delete an element from cqueue is called deletion. This work is done by front of queue. If front=-1 It means cqueue is empty and we perform deletion operation then underflow condition will occur. If last element (front=rear) is remained in queue then set front=rear= -1. if front=N-1 then set front=0 otherwise front is increased by 1.
सर्कुलर क्यू से किसी एलिमेंट को हटाना/ निकालना , डिलीशन ऑपरेशन कहलाता है। यह कार्य सर्कुलर क्यू के फ्रंट से किया जाता है। यदि front=-1 अर्थात सर्कुलर क्यू खाली हो एवं डिलीशन ऑपरेशन किया जाये, तब अंडरफ्लो कंडीशन उत्पन्न होती है। यदि क्यू में अंतिम एलिमेंट (front=rear) का डिलीशन किया जाता है तब front=rear=-1 सेट किया जाता है। यदि front=N-1 तब front=0 सेट किया जाता है अन्यथा फ्रंट को एक से बढाया जाता है।    

3.) Traversing:- To visit/ print of all elements of queue is called traversing. This work is done from front to rear of queue. If front= -1, it means queue is empty and then Traversing operation cant be performed.
क्यू में उपस्थित सभी एलिमेंट को ट्रेवर्स/ विजिट/एक्सेस/प्रिंट करना, ट्रेवरसींग ऑपरेशन कहलाता है। यह कार्य front से rear तक किया जाता है। यदि front=-1 अर्थात क्यू खाली है, तब ट्रेवरसींग ऑपरेशन नहीं किया जा सकता है। यदि front<=rear तब एक लूप i=front से i<=rear तक रन किया जाता है अन्यथा दो लूप रन किया जाता है जिसमे  पहला लूप  i=front से i<=N-1 तक तथा दूसरा लूप i=0 से i<=rear तक रन किया जाता है।  

Example Program:-

C++ or C Program for Insertion,Deletion,Traversing Operations of Circular Queue

File Name:- cqueue.cpp
#include<iostream.h>
#include<conio.h>
#define N 5
int cqueue[N],front=-1,rear=-1,item;
//insertion function
void cinsertion(){
if(((front==0)&&(rear==N-1))||(front==rear+1)){
cout<<"Overflow Condition"<<endl;
getch();
return;
}
cout<<"Enter an Item to insert"<<endl;
cin>>item;
if(rear==-1)
front=rear=0;
else{
if(rear==N-1){
rear=0;}
else{
rear++;
}
}
cqueue[rear]=item;
cout<<item<<" is inserted in circular queue"<<endl<<"insertion completed"<<endl;
getch();
return;
}

//deletion function
void cdeletion(){
if(front==-1){
cout<<"underflow Condition"<<endl;
getch();
return;
}
item=cqueue[front];
if(front==rear){
front=rear=-1;
}
else
{if(front==N-1){
front=0;
}
else{
front++;
}
}
cout<<item<<" is deleted from circular queue"<<endl<<"deletion completed"<<endl;
getch();
return;
}
//traversing function
void ctraversing(){
int i;
if(front==-1){
cout<<"circular queue is empty"<<endl;
getch();
return;
}
cout<<"Circular Queue is: "<<endl;
if(rear>=front){
for(i=front;i<=rear;i++){
cout<<cqueue[i]<<" ";
}
}
else{
for(i=front;i<=N-1;i++){
cout<<cqueue[i]<<" ";
}
for(i=0;i<=rear;i++){
cout<<cqueue[i]<<" ";
}
}
cout<<endl<<"front= "<<front<<" and rear= "<<rear<<endl<<"traversing completed"<<endl;
getch();
return;
}
//main function
void main(){
int ch;
while(1){
clrscr();
cout<<"Circular Queue Operation:\n1.INSERTION\n2.DELETION\n3.TRAVERSING\n4.EXIT\nenter your choice"<<endl;
cin>>ch;
switch(ch){
case 1: cinsertion();break;
case 2: cdeletion();break;
case 3: ctraversing();break;
case 4: exit();
defaul: cout<<Wrong Choice"<<endl; 
getch();
}}}

File Name:- cqueue.c
#include<stdio.h>
#include<conio.h>
#define N 5
int cqueue[N],front=-1,rear=-1,item;
void cinsertion(){
if(((front==0)&&(rear==N-1))||(front==rear+1)){
printf("Overflow Condition\n");
getch();
return;
}
printf("Enter an Item to insert\n");
scanf("%d",&item);
if(rear==-1)
front=rear=0;
else{
if(rear==N-1){
rear=0;}
else{
rear++;
}
}
cqueue[rear]=item;
printf("%d is inserted\ninsertion completed\n",item);
getch();
return;
}
void cdeletion(){
if(front==-1){
printf("underflow Condition\n");
getch();
return;
}
item=cqueue[front];
if(front==rear){
front=rear=-1;
}
else
{if(front==N-1){
front=0;
}
else{
front++;
}
}
printf("%d is deleted\nDeletion completed\n",item);
getch();
return;
}
void ctraversing(){
int i;
if(front==-1){
printf("circular queue is Empty\n");
getch();
return;
}
printf("Circular Queue is:");
if(rear>=front){
for(i=front;i<=rear;i++){
printf("%d ",cqueue[i]);
}
}
else{
for(i=front;i<=N-1;i++){
printf("%d ",cqueue[i]);
}
for(i=0;i<=rear;i++){
printf("%d ",cqueue[i]);
}
}
printf("\nfront=%d and rear=%d\n",front,rear);
printf("Traversing completed");
getch();
return;
}
void main(){
int ch;
while(1){
clrscr();
printf("cqueue Operation:-\n1.INSERTION\n2.DELETION\n3.TRAVERSING\n4.EXIT\nEnter your choice\n");
scanf("%d",&ch);
switch(ch){
case 1: cinsertion();break;
case 2: cdeletion();break;
case 3: ctraversing();break;
case 4: exit();
default:
printf("Wrong Choice\n");
getch();
}}}

Disadvantage of Linear / Static Queue and Its Solution

Disadvantage of Linear/Static Queue- 

लीनियर/स्टेटिक क्यू की हानियाँ:-

We know that when any element is inserted in linear queue then rear will be increased by 1. Let, assume after insertion operations rear is shifted to last position(N-1) in queue. It means, now queue is full. Now if a new element is inserted then overflow condition will occur. Now, if we delete some elements from queue then front will be increased by 1. After deletion memory space occupied by those elements will be blank and it should be reused by other new element. But it cannot possible because rear is still pointing to the last position(N-1). Hence, we cannot able to reuse free memory space present in linear/static queue and memory is not effectively used. To solve this problem following two types are used.

हमे ज्ञात है कि जब लीनियर क्यू में किसी नए एलिमेंट को इन्सर्ट किया जाता है तब रियर को एक से बढाया जाता है। माना कि कई इंसर्शन ऑपरेशन के पश्चात् रियर अभी लास्ट पोजीशन(N-1) पर है अर्थात क्यू फुल है और अब इंसर्शन ऑपरेशन करने पर ओवरफ्लो कंडीशन उत्पन्न होती है। अब यदि क्यू से कुछ एलिमेंट को डिलीट किया जाता है तब फ्रंट को एक से बढाया जाता है। कुछ डिलीशन ऑपरेशन के पश्चात् क्यू में जगह रिक्त हो जाती है जिसका प्रयोग नए एलिमेंट के इंसर्शन में किया जाना चाहिए परन्तु यह संभव नहीं हो पता है क्यूंकि रियर अभी भी लास्ट पोजीशन(N-1) पर है। अत: लीनियर क्यू में मेमोरी का प्रभावी उपयोग नहीं हो पाता है। इस समस्या को निम्न दो तरीको से हल किया जा सकता है- 


1. To convert static/linear queue into physical queue:- 

लीनियर/स्टेटिक क्यू को फिजिकल क्यू में बदल कर :-

In Linear Queue, Let us assume rear=N-1, it means rear is pointing to last position of Queue and front is always pointing to first position (front=0) of Queue, It wont be increased by 1. Now, For each deletion operation, we need to shift all the remaining elements one-by-one towards first position due to which last position will automatically left blank and we can insert new element on it. It is called Physical Queue and It utilizes memory space. In daily life, a queue of students or customers at counter where students and customers are shifting towards the counter.

लीनियर क्यू में, माना कि rear=N-1 अर्थात रियर लास्ट पोजीशन पर है एवं फ्रंट सदैव फर्स्ट पोजीशन(front=0) पर रहेगा, इसे बढाया नहीं जायेगा। अब प्रत्येक डिलीशन ऑपरेशन के लिए, सभी शेष एलिमेंट को एक-एक करके ,एक पोजीशन आगे की ओर शिफ्ट किया जाता है जिससे लास्ट पोजीशन स्वत : ही रिक्त हो जाती है एवं नए एलिमेंट का इंसर्शन रियर पर हो जाता है,  इसे फिजिकल क्यू कहा जाता है। इसमें मेमोरी का प्रभावी उपयोग होता है। दैनिक जीवन में - काउंटर पर स्टूडेंट्स या कस्टमर की कतार जिसमे काउंटर आगे नहीं बढ़ता है स्टूडेंट्स या कस्टमर ,उसकी ओर बढ़ते है। 


Physical queue is an effectively technique for small queue,but if a queue has large number of elements then a single deletion operation of an element requires many swapping process for shifting all other elements of physical queue which is a time consuming process and CPU spends more time in swapping values. Due to which execution of program is getting slower. So, we use circular queue for large elements queue instead of physical queue.

फिजिकल क्यू छोटे क्यू के लिए एक सफल युक्ति है परन्तु यदि किसी क्यू में एलिमेंट की संख्या अधिक हो तब एक डिलीशन ऑपरेशन के लिए कई स्वैपिंग ऑपरेशन करने की आवश्यकता होगी, जो कि अधिक समय खर्च करने वाली प्रक्रिया है एवं इसमें सी.पी.यू का अत्यधिक समय, एलिमेंट के डिलीशन के स्थान पर, कई एलिमेंट की स्वैपिंग में खर्च होता है जिससे प्रोग्राम का एक्सीक्यूशन धीमा हो जाता है अत: अधिक एलिमेंट वाले क्यू के लिए फिजिकल क्यू के स्थान पर सर्कुलर क्यू का प्रयोग किया जाता है।          


2. To convert static/linear queue into circular queue

लीनियर/स्टेटिक क्यू को सर्कुलर क्यू में बदल कर


C++ or C program for Insertion, Deletion, Traversing operations of Linear or Static Queue

File Name:- queue.cpp

#include<iostream.h>

#include<conio.h>

#define N 5

int queue[N],front=-1,rear=-1,item;

//insertion function

void insertion(){

if(rear==N-1){

cout<<"Overflow Condition"<<endl;

getch();

return;

}

cout<<"Enter an Item to insert"<<endl;

cin>>item;

if(rear==-1){

front=rear=0;

}

else{

rear++;

}

queue[rear]=item;

cout<<"Insertion completed"<<endl<<item<<" is inserted in queue"<<endl;

getch();

return;

}

//deletion function

void deletion(){

if(front==-1){

cout<<"underflow Condition"<<endl;

getch();

return;

}

item=queue[front];

if(front==rear){

front=rear=-1;

}

else

{

front++;

}

cout<<"Deletion completed"<<endl<<item<<" is deleted from queue"<<endl;

getch();

return;

}

//traversing function

void traversing(){

int i;

if(front==-1){

cout<<"Queue is Empty"<<endl;

getch();

return;

}

cout<<"Linear Queue is: ";

for(i=front;i<=rear;i++){

cout<<queue[i]<<" ";

}

cout<<endl<<"front= "<<front<<" and rear= "<<rear<<endl<<"Traversing completed"<<endl;

getch();

return;

}

//main function

void main(){

int ch;

while(1){

clrscr();

cout<<"Queue Operation:-\n1.INSERTION\n2.DELETION\n3.TRAVERSING\n4.EXIT\nenter your choice"<<endl;

cin>>ch;

switch(ch){

case 1: insertion();break;

case 2: deletion();break;

case 3: traversing();break;

case 4: exit();

default: cout<<"Wrong Choice"<<endl;

getch();

}

}

}


File Name:- queue.c

#include<stdio.h>

#include<conio.h>

#define N 5

int queue[N],front=-1,rear=-1,item;

void insertion(){

if(rear==N-1){

printf("Overflow Condition\n");

getch();

return;

}

printf("Enter an Item to insert\n");

scanf("%d",&item);

if(rear==-1){

front=rear=0;

}

else{

rear++;

}

queue[rear]=item;

printf("insertion completed\n");

getch();

return;

}

void deletion(){

if(front==-1){

printf("underflow Condition\n");

getch();

return;

}

item=queue[front];

if(front==rear){

front=rear=-1;

}

else

{

front++;

}

printf("Deletion completed\n");

printf("%d is deleted\n",item);

getch();

return;

}

void traversing(){

int i;

if(front==-1){

printf("Queue is Empty\n");

getch();

return;

}

printf("Linear Queue is:");

for(i=front;i<=rear;i++){

printf(" %d ",queue[i]);

}

printf("front=%d and rear=%d\n",front,rear);

printf("Traversing completed");

getch();

return;

}

void main(){

int ch;

while(1){

clrscr();

printf("Queue Operation:-\n1.INSERTION\n2.DELETION\n3.TRAVERSING\n4.EXIT\nenter your choice\n");

scanf("%d",&ch);

switch(ch){

case 1: insertion();break;

case 2: deletion();break;

case 3: traversing();break;

case 4: exit();

default:

printf("Wrong Choice\n");

getch();

}

}

}

Queue / Linear Queue / Static Queue Data Structure, Insertion, Deletion and Traversing Operations of Queue

Linear queue:- queue is a linear data structure. It is collection of ordered data elements. It is also known as FIFO system or FCFS system. It means an element which is inserted first will be deleted first. Here data elements will be inserted from one end of queue called rear and deleted from the other end called front. We can use Array or Linked list representation to store queue in memory.Daily life examples of queue are Students line at fees counter, Passengers line at bus stand/railway station/airport,  Viewers line at movie ticket counter etc.

लीनियर/ स्टेटिक क्यू एक लीनियर डाटा स्ट्रक्चर है। यह क्रमबद्ध डाटा एलेमेंट्स का संग्रह है। इसे FIFO (फर्स्ट इन फर्स्ट आउट) या FCFS (फर्स्ट कम फर्स्ट सर्व) सिस्टम के नाम से भी जाना जाता है अर्थात क्यू में यदि किसी एलिमेंट को सबसे पहले इन्सर्ट किया जाता है, तब उसे ही सबसे पहले डिलीट किया जाता है। यहाँ एलिमेंट का इंसर्शन क्यू के रियर छोर पर तथा डिलीशन फ्रंट छोर से किया जाता है। हम अरे एवं लिंक्ड लिस्ट में से किसी एक का प्रयोग कर मेमोरी में क्यू तैयार कर सकते है। दैनिक जीवन में क्यू के उदाहरण है -  फीस काउंटर के बाहर छात्रों की पंक्ति , बस स्टैंड / रेलवे स्टेशन/ एयरपोर्ट में पैसेंजर की लाइन, मूवी टिकेट काउंटर के बाहर व्यूअरस की कतार इत्यादि।
Queue is mainly of five types-
क्यू मुख्यत: पांच प्रकार का होता है- 
1. Linear/static queue (लीनियर/ स्टेटिक क्यू)
2. Physical queue (फिजिकल क्यू)
3. Circular queue (सर्कुलर क्यू)
4. Double ended queue (डबल एंडेड क्यू)
5. Priority queue (प्रायोरिटी क्यू)

Operations performed on queue are as follows:-

1. Insertion:- To add new element in queue is called insertion operation. This work is done on rear of queue and rear is increased by 1. If first element is inserted in queue then set front=rear=0. If(rear=N-1) It means queue is full and insertion operation is performed, then overflow condition will occur.
क्यू  में किसी नए एलिमेंट को जोड़ना, इंसर्शन ऑपरेशन कहलाता है। यह कार्य क्यू के रियर पर किया जाता है एवं रियर को एक से बढाया जाता है। यदि क्यू में पहले एलिमेंट का इंसर्शन किया जाता है तब front=rear=0 सेट किया जाता है। यदि rear=N-1 अर्थात क्यू फुल हो एवं इंसर्शन ऑपरेशन किया जाये , तब ओवरफ्लो कंडीशन उत्पन्न होती है।    
Algorithm / Function for Insertion operation-

void insertion(){
if(rear==N-1){
printf("Overflow Condition\n");
getch();
return;
}
printf("Enter an Item to insert\n");
scanf("%d",&item);
if(rear==-1){
front=rear=0;
}
else{
rear++;
}
queue[rear]=item;
printf("insertion completed\n");
getch();
return;
}

2. Deletion:- To remove/ delete an element from queue is called deletion. This work is done on front of queue and front is increased by 1. If last element is remained in queue i.e.. front=rear then set front=rear= -1. When front=-1, It means queue is empty and we perform deletion operation then underflow condition will occur.
क्यू से किसी एलिमेंट को हटाना/ निकालना , डिलीशन ऑपरेशन कहलाता है। यह कार्य क्यू के फ्रंट से किया जाता है एवं फ्रंट को एक से बढाया जाता है। यदि क्यू में अंतिम एलिमेंट(front=rear) का डिलीशन किया जाता है तब front=rear=-1 सेट किया जाता है। यदि front=-1 अर्थात क्यू खाली हो एवं डिलीशन ऑपरेशन किया जाये , तब अंडरफ्लो कंडीशन उत्पन्न होती है।    
Algorithm / Function for Deletion operation-

void deletion(){
if(front==-1){
printf("underflow Condition\n");
getch();
return;
}
item=queue[front];
if(front==rear){
front=rear=-1;
}
else
{
front++;
}
printf("Deletion completed\n");
printf("%d is deleted\n",item);
getch();
return;
}

3. Traversing:- To visit/ print of all elements of queue is called traversing. This work is done from front to rear of queue. If front= -1 or rear= -1, it means queue is empty and then Traversing operation cant be performed.
क्यू में उपस्थित सभी एलिमेंट को ट्रेवर्स/ विजिट/एक्सेस/प्रिंट करना, ट्रेवरसींग ऑपरेशन कहलाता है। यह कार्य front से rear तक किया जाता है। यदि  front=-1 अर्थात क्यू खाली है, तब ट्रेवरसींग ऑपरेशन नहीं किया जा सकता है।   
Algorithm/ Function for Traversing Operation:-

void traversing(){
int i;
if(front==-1){
printf("Queue is Empty\n");
getch();
return;
}
printf("Linear Queue is:");
for(i=front;i<=rear;i++){
printf(" %d ",queue[i]);
}
printf("front=%d and rear=%d\n",front,rear);
printf("Traversing completed");
getch();
return;
}

Sunday, May 19, 2024

Applications of Stack Data Structure स्टैक डेटा स्ट्रक्चर के अनुप्रयोग

 Stack is used to perform following task:-

स्टैक का प्रयोग निम्न कार्यो को पूर्ण करने के लिए किया जाता है:-
 
1. Stack is used to store intermediate data (context) which is occurred in recursion process when recursion function ends all the elements of stack popped in one by one manner and evaluated then we provide result to the user. Hence stack must required in every recursive program.
स्टैक का प्रयोग रिकर्शन प्रक्रिया में पारायुक्त किये जाने वाले इंटरमीडिएट डाटा (कॉन्टेक्स्ट) को रखने के लिए किया जाता है। जब रिकर्शन कॉल समाप्त होती है, तब एक के बाद एक क्रम से सभी एलिमेंट को पॉप कर लिया जाता है एवं उनकी गणना की जाती है जिससे परिणामी हल प्राप्त होता है। अत: रिकर्सिव फंक्शन के लिए स्टैक डाटा स्ट्रक्चर अनिवार्य है।    

2. Stack is used in evaluation process of each arithmetic and logical expression. First of all infix expression of program is converted into postfix expression using stack. After that postfix expression is evaluate by CPU and stack must required to complete this process.
स्टैक का प्रयोग सभी गणितीय एवं तार्किक एक्सप्रेशन के मूल्यांकन में किया जाता है। सर्वप्रथम इन्फ़िक्स एक्सप्रेशन को पोस्टफिक्स एक्सप्रेशन में बदला जाता है इसके पश्चात् पोस्टफिक्स एक्सप्रेशन का मूल्यांकन किया जाट अहिया एवं हल प्राप्त किया जाता है।    

Algorithm for evaluation of postfix expressions/notations with examples

 Algorithm for evaluation of postfix  expressions/notations:-


(1) Add right parenthesis ')' at the end of postfix expression P.
(2) Scan P from left to right and repeat steps (3) and (4) until right parenthesis occurred. 
(3) If an operand encountered then push it into the stack.
(4) If an operator encountered then operate top two elements of stack as follows:-
(a) Evaluate BoA where A is top element and B is next top element. 
(b) Push the result into the stack.
(5)If right parenthesis ')' encountered then pop the final result from the stack, it means evaluation is completed.
(6) Exit.

Examples:-

1.) P = 52/42^3*+
solve :- given expression P = 52/42^3*+
s.no.
Scanned symbol
Stack
1
5
5
2
2
5,2
3
/
2
4
4
2, 4
5
2
2, 4, 2
6
^
2, 16
7
3
2, 16, 3
8
*
 2, 48
9
+
50
answer is 50.

2.) P = AB*C/DE*F/-
where A=5, B=2, C=7, D=4, E=1 AND F=3
Solve :- given expression P = 52*7/41*3/-
s.no.
Scanned symbol
Stack
1
5
5
2
2
5, 2
3
*
10
4
7
 10, 7
5
/
1
6
4
1, 4
7
1
1, 4, 1
8
*
1, 4
9
3
1, 4, 3
10
/
1, 1
11
-
0
Answer is 0.

3.) P = 1273-/215+*+
solve :- given expression P = 1273-/215+*+
s.no.
Scanned symbol
Stack
1
1
1
2
2
1, 2
3
7
1, 2, 7
4
3
1, 2, 7, 3
5
-
1, 2, 4
6
/
1, 2
7
2
1, 2, 2
8
1
1, 2, 2, 1
9
5
1, 2, 2, 1, 5
10
+
1, 2, 2, 6
11
*
1, 2, 12
12
+
15
Answer is 15.

4.) P = 35+64-*41-2^+
solve :- given expression,
P = 35+64-*41-2^+
S.no.
Scanned symbol
Stack
1
3
3
2
5
3, 5
3
+
8
4
6
8, 6
5
4
8, 6, 4
6
-
8, 2
7
*
16
8
4
16, 4
9
1
16, 4, 1
10
-
16, 3
11
2
16, 3, 2
12
^
16, 9
13
+
25
Answer is 25

Priority Queue

Priority queue:-  It is a special type of queue which stores group of elements. Each element has a priority number associated with it. Prior...