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.
Data Structures and Algorithms (DSA) using C/C++
Everything about Data Structures and Algorithms (DSA) using C/C++ with Examples in Dual Language (Hindi / English)
Saturday, September 21, 2024
Priority Queue
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.
Applications of Queue
Queues are useful for following applications:-
Circular Queue Data Structure, C or C++ Program for Insertion, Deletion and Traversing Operations of Circular Queue.
Circular Queue:-
Circular Queue |
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.
Sunday, May 19, 2024
Applications of Stack Data Structure स्टैक डेटा स्ट्रक्चर के अनुप्रयोग
Stack is used to perform following task:-
Algorithm for evaluation of postfix expressions/notations with examples
Algorithm for evaluation of postfix expressions/notations:-
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 |
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 |
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 |
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 |
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...
-
Topics Covered Unit-01 Data structure Operations performed on Data structure Classification of Data structures Linear and Non Linear data st...
-
IMP QUESTIONS - Data Structures and Algorithms DSA using C/C++ Language. Unit:-1 1.Data structure( Operations performed on Data structure, C...