Linked Queue:-
Linked 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 Linked list representation to store linked queue in memory.
In linked list representation of Queue, we create a SLL node to store data element of queue which has two parts info part and link part.
लिंक्ड क्यू एक लीनियर डाटा स्ट्रक्चर है। यह क्रमबद्ध डाटा एलेमेंट्स का संग्रह है। इसे FIFO (फर्स्ट इन फर्स्ट आउट) या FCFS (फर्स्ट कम फर्स्ट सर्व) सिस्टम के नाम से भी जाना जाता है अर्थात लिंक्ड क्यू में यदि किसी एलिमेंट को सबसे पहले इन्सर्ट किया जाता है, तब उसे ही सबसे पहले डिलीट किया जाता है। यहाँ एलिमेंट का इंसर्शन लिंक्ड क्यू के रियर छोर पर तथा डिलीशन फ्रंट छोर से किया जाता है। हम लिंक्ड लिस्ट रिप्रजेंटेशन का प्रयोग कर मेमोरी में लिंक्ड क्यू तैयार कर सकते है।
क्यू के लिंक्ड लिस्ट रिप्रजेंटेशन में हम SLL के नोड की सहायता से क्यू के डाटा एलिमेंट को स्टोर करते है इस नोड में दो भाग होते है इन्फो पार्ट एवं लिंक पार्ट।
struct node{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *front=NULL,*rear=NULL,*n=NULL;
Here info part is used to store information related with node and link is a self referential pointer variable which is used to point next node of the SLL.
The address of first node and last node of SLL are stored in front and rear external pointer variable respectively.
n external pointer variable is used to get node from free memory pool(heap).if node is not allocated it returns null value.
यहाँ इन्फो पार्ट नोड से सम्बंधित जानकारी रखता है एवं लिंक पार्ट, एक सेल्फ रिफरेन्सीयल पॉइंटर वेरिएबल है जो SLL के अगले नोड का एड्रेस रखता है।
SLL के प्रथम एवं अंतिम नोड का एड्रेस क्रमशः फ्रंट एवं रियर एक्सटर्नल पॉइंटर वेरिएबल द्वारा रखा जाता है।
n नामक एक्सटर्नल पॉइंटर वेरिएबल का प्रयोग फ्री मेमोरी पूल (हीप) से नोड लेन के लिए किया जाता है। यदि नोड प्राप्त नहीं होता है तब यह नल वैल्यू रिटर्न करता है।
Linked queue or Dynamic queue is more efficient than normal queue because it minimizes overflow condition of queue and it utilizes memory space of the computer by modifying number of nodes at run time.
लिंक्ड क्यू या डायनामिक क्यू सामान्य क्यू की तुलना में अधिक विश्वसनीय होता है क्यूंकि यह ओवरफ्लो कंडीशन को बहुत कम कर देता है एवं रन टाइम पर नोड्स की संख्या में परिवर्तन कर, कंप्यूटर मेमोरी का प्रभावी प्रयोग करता है।
Operations performed on linked queue are as follows:-
लिंक्ड क्यू पर किये जाने वाले ऑपरेशन निम्न है:-
1. Insertion:- To add new element (node) in linked queue is called insertion operation. This work is done on rear of queue and rear is set as rear->link=n; rear=n;
If first element (node) is inserted in queue then set front=rear=n.
क्यू में किसी नए एलिमेंट (नोड) को जोड़ना, इंसर्शन ऑपरेशन कहलाता है। यह कार्य क्यू के रियर पर किया जाता है एवं रियर को rear->link=n; rear=n; पर सेट जाता है।
यदि क्यू में पहले एलिमेंट (नोड) का इंसर्शन किया जाता है तब front=rear=n सेट किया जाता है।
2.) Deletion:- To remove/ delete an element (node) from queue is called deletion. This work is done on front of queue and front is shifted to front=front->link; .
If last element is remained in queue i.e.. front=rear then set front=rear=NULL.
When front=NULL, It means queue is empty and we perform deletion operation then underflow condition will occur.
क्यू से किसी एलिमेंट (नोड) को हटाना/ निकालना , डिलीशन ऑपरेशन कहलाता है। यह कार्य क्यू के फ्रंट से किया जाता है एवं फ्रंट को एक से बढाया जाता है। यदि क्यू में अंतिम एलिमेंट(front=rear) का डिलीशन किया जाता है तब front=rear=NULL सेट किया जाता है। यदि front=NULL अर्थात क्यू खाली हो एवं डिलीशन ऑपरेशन किया जाये , तब अंडरफ्लो कंडीशन उत्पन्न होती है।
3. Traversing:- To visit/ print of all the elements (nodes) of queue is called traversing. This work is done from front to rear of queue. If front=NULL, it means queue is empty and then Traversing operation cant be performed.
क्यू में उपस्थित सभी एलिमेंट(नोड्स) को ट्रेवर्स/ विजिट/एक्सेस/प्रिंट करना, ट्रेवरसींग ऑपरेशन कहलाता है। यह कार्य front से rear तक किया जाता है। यदि front=NULL अर्थात क्यू खाली है, तब ट्रेवरसींग ऑपरेशन नहीं किया जा सकता है।
Linked Queue or Dynamic Queue Program:-
File Name:- linkedq.cpp
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct node{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *front=NULL,*rear=NULL,*n=NULL;
//Insertion function
void insertion(){
int item;
n= new NODE;
if(n==NULL){
cout<<"Overflow condition"<<endl;
getch();
return;
}
cout<<"Enter item to insert"<<endl;
cin>>item;
n->info=item;
n->link=NULL;
if(rear==NULL){
front=rear=n;
}
else{
rear->link=n;
rear=n;
}
cout<<"Insertion completed"<<endl;
getch();
return;
}
//Deletion function
void deletion(){
clrscr();
if(front==NULL){
cout<<"Underflow condition"<<endl;
getch();
return;
}
n=front;
if(front==rear){
front=rear=NULL;}
else{
front=front->link;}
cout<<"Deletion completed"<<endl;
delete n;
getch();
return;
}
void traversing(){
NODE *temp=front;
int i=0;
clrscr();
if(temp==NULL){
cout<<"Linked Queue is empty"<<endl;
getch();
return;
}
cout<<"Linked Queue is:-"<<endl;
while(temp!=NULL){
i++;
cout<<"Node no:- "<<i<<endl<<"info part= "<<temp->info<<endl<<"link part="<<temp->link<<endl;
temp=temp->link;
}
cout<<"Linked Queue traversed."<<endl<<i<<" node's are visited."<<endl<<"front= "<<front<<"rear= "<<rear<<endl;
getch();
return;
}
void main(){
int ch;
while(1){
clrscr();
cout<<"Linked Queue operations:-"<<endl<<"1.Insertion"<<endl<<"2.Deletion"<<endl<<"3.Traversing"<<endl<<"4. exit"<<endl<<"Enter 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 selected"<<endl;
getch();
}}}
File Name:-
linkedq.c
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node{
int info;
struct node *link;
};
typedef struct node
NODE;
NODE
*front=NULL,*rear=NULL,*n=NULL;
void insertion(){
int item;
n= malloc(sizeof(NODE));
if(n==NULL){
printf("Overflow
Condition\n");
getch();
return;
}
printf("Enter item
to insert\n");
scanf("%d",&item);
n->info=item;
n->link=NULL;
if(rear==NULL){
front=rear=n;
}
else{
rear->link=n;
rear=n;
}
printf("insertion
Completed\n");
getch();
return;
}
void deletion(){
clrscr();
if(front==NULL){
printf("Underflow
Condition\n");
getch();
return;
}
n=front;
if(front==rear){
front=rear=NULL;}
else{
front=front->link;}
printf("Deletion
Copleted");
free(n);
getch();
return;
}
void traversing(){
NODE *temp=front;
int i=0;
clrscr();
if(temp==NULL){
printf("Linked
Queue is Empty\n");
getch();
return;
}
printf("Linked
Queue is:-\n");
while(temp!=NULL){i++;
printf("Node
No:-%d\n info part= %d\nLink Part=%u\n",i,temp->info,temp->link);
temp=temp->link;
}
printf("Linked Queue
Traversed \n%d Node's are Visited.\nfront=%u and rear=%u",i,front,rear);
getch();
return;
}
void main(){
int ch;
while(1){
clrscr();
printf("Linked
Queue operations:-\n 1.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 selected\n");
getch();
}}}
No comments:
Post a Comment