queue data structure c with illustration
चित्रण के साथ C ++ में कतार का संक्षिप्त परिचय।
कतार एक स्टैक की तरह एक बुनियादी डेटा संरचना है। LIFO दृष्टिकोण का उपयोग करने वाले स्टैक के विपरीत, कतार FIFO (पहली बार, पहली आउट) दृष्टिकोण का उपयोग करती है। इस दृष्टिकोण के साथ, कतार में जोड़ा जाने वाला पहला आइटम कतार से निकाला जाने वाला पहला आइटम है। स्टैक की तरह, कतार भी एक रैखिक डेटा संरचना है।
बिक्री के बिंदु के लिए आईपैड का उपयोग करना
एक वास्तविक दुनिया सादृश्य में, हम एक बस कतार की कल्पना कर सकते हैं जहां यात्री एक कतार या एक पंक्ति में बस की प्रतीक्षा करते हैं। लाइन में पहला यात्री पहले बस में प्रवेश करता है क्योंकि यात्री वह होता है जो पहले आया था।
=> लोकप्रिय सी ++ प्रशिक्षण श्रृंखला के माध्यम से यहां पढ़ें।
आप क्या सीखेंगे:
कतार में C ++
सॉफ्टवेयर शब्दों में, कतार को नीचे दिखाए गए तत्वों के एक सेट या संग्रह के रूप में देखा जा सकता है। तत्वों को रैखिक रूप से व्यवस्थित किया जाता है।
हमारे पास दो छोर हैं यानी कतार के 'सामने' और 'पीछे'। जब कतार खाली होती है, तो दोनों बिंदु -1 पर सेट हो जाते हैं।
'रियर' एंड पॉइंटर वह जगह है जहां से तत्वों को कतार में डाला जाता है। कतार में तत्वों को जोड़ने / सम्मिलित करने के ऑपरेशन को 'एन्क्यू' कहा जाता है।
'फ्रंट' एंड पॉइंटर वह जगह है जहां से तत्वों को कतार से हटाया जाता है। कतार से तत्वों को हटाने / हटाने के लिए ऑपरेशन को 'dequeue' कहा जाता है।
जब रियर पॉइंटर मान आकार -1 होता है, तो हम कहते हैं कि कतार भरी हुई है। जब सामने वाला अशक्त होता है, तब कतार खाली होती है।
बुनियादी संचालन
कतार डेटा संरचना में निम्नलिखित ऑपरेशन शामिल हैं:
- एनक्यूयू: किसी आइटम को कतार में जोड़ता है। किसी आइटम को कतार में जोड़ना हमेशा कतार के पीछे किया जाता है।
- DeQueue: कतार से एक आइटम निकालता है। एक आइटम को हमेशा कतार के सामने से हटाया या हटा दिया जाता है।
- खाली है: जाँच करता है कि कतार खाली है या नहीं।
- पूर्ण है: जाँच करता है कि कतार भरी हुई है या नहीं।
- झांकना: इसे हटाए बिना कतार के सामने एक तत्व प्राप्त होता है।
कतारबद्ध करें
इस प्रक्रिया में, निम्न चरणों का पालन किया जाता है:
- जाँच करें कि कतार भरी हुई है या नहीं।
- यदि पूर्ण है, तो अतिप्रवाह त्रुटि और बाहर निकलें।
- एल्स, इंक्रीमेंट 'रियर'।
- 'रियर' द्वारा बताए गए स्थान पर एक तत्व जोड़ें।
- सफलता लौटाओ।
विपंक्ति
Dequeue कार्रवाई में निम्न चरण होते हैं:
- जांचें कि क्या कतार खाली है।
- यदि रिक्त है, तो एक अंडरफ़्लो त्रुटि प्रदर्शित करें और बाहर निकलें।
- इसके अलावा, पहुंच तत्व को 'सामने' द्वारा इंगित किया गया है।
- अगले पहुँच योग्य डेटा को इंगित करने के लिए 'सामने' बढ़ाएँ।
- सफलता लौटाओ।
अगला, हम कतार में सम्मिलन और विलोपन कार्यों का एक विस्तृत चित्रण देखेंगे।
चित्रण
यह एक खाली कतार है और इस प्रकार हमारे पास -1 और रियर सेट -1 है।
अगला, हम कतार में 1 जोड़ते हैं और परिणामस्वरूप, रियर पॉइंटर एक स्थान से आगे बढ़ता है।
अगले आंकड़े में, हम पीछे के पॉइंटर को एक और वृद्धि द्वारा आगे बढ़ाकर तत्व 2 को कतार में जोड़ते हैं।
निम्नलिखित आकृति में, हम तत्व 3 जोड़ते हैं और रियर पॉइंटर को 1 से आगे बढ़ाते हैं।
इस बिंदु पर, रियर पॉइंटर का मूल्य 2 है जबकि फ्रंट पॉइंटर 0 पर हैवेंस्थान।
अगला, हम सामने वाले पॉइंटर द्वारा बताए गए तत्व को हटाते हैं। जैसा कि फ्रंट पॉइंटर 0 पर है, डिलीट किया गया तत्व 1 है।
इस प्रकार कतार में प्रवेश किया गया पहला तत्व अर्थात 1 कतार से हटा दिया गया पहला तत्व होता है। नतीजतन, पहले छल के बाद, अब सामने वाला पॉइंटर आगे के स्थान पर t0 से आगे चला जाएगा जो कि 1 है।
कतार के लिए ऐरे कार्यान्वयन
आइए हम C ++ का उपयोग करके कतार डेटा संरचना को लागू करते हैं।
#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }
आउटपुट:
कतार खाली है !!
कतार बनाई गई:
१० २० ३० ४० ५०
कतार भरी है !!
सामने = ०
कतार तत्व: 10 20 30 40 50
रियर = 4
नष्ट कर दिया => 10 myqueue से
मोर्चा = १
कतार तत्व: 20 30 40 50
रियर = 4
उपरोक्त कार्यान्वयन एक सरणी के रूप में प्रदर्शित कतार को दर्शाता है। हम सरणी के लिए max_size निर्दिष्ट करते हैं। हम इस्क्यू और डीक्यू ऑपरेशंस के साथ-साथ आइसफुल और इस्मिप ऑपरेशंस को भी परिभाषित करते हैं।
नीचे कतार डेटा संरचना का जावा कार्यान्वयन है।
// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println('
Element ' + queue.dequeue() + ' dequeued from queue
'); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }
आउटपुट:
कतार इस प्रकार बनाई गई:
१० २० ३० ४०
तत्व 10 कतार से हटा दिया गया
फ्रंट आइटम 20 है
रियर आइटम 40 है
उपरोक्त कार्यान्वयन C ++ कार्यान्वयन के समान है।
अगला, आइए हम एक लिंक की गई सूची का उपयोग करके C ++ में कतार को लागू करते हैं।
कतार के लिए सूचीबद्ध सूची कार्यान्वयन:
#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : ' आउटपुट:
निर्मित कतार:
१० २० ३० ४० ५०
कतार से हटाया गया तत्व है: 10
एक विलोपन के बाद कतार:
२० ३० ४० ५०
कैसे जावा में एक सरणी की नकल करने के लिए
स्टैक बनाम। पंक्ति
ढेर और कतारें माध्यमिक डेटा संरचनाएं हैं जिनका उपयोग डेटा को संग्रहीत करने के लिए किया जा सकता है। उन्हें प्राथमिक डेटा संरचनाओं जैसे सरणियों और लिंक्ड सूचियों का उपयोग करके प्रोग्राम किया जा सकता है। दोनों डेटा संरचनाओं के बारे में विस्तार से चर्चा करने के बाद, इन दो डेटा संरचनाओं के बीच मुख्य अंतर पर चर्चा करने का समय है।
ढेर कतारों LIFO (लास्ट इन, फर्स्ट आउट) दृष्टिकोण का उपयोग करता है। एफआईएफओ (फर्स्ट इन, फर्स्ट आउट) दृष्टिकोण का उपयोग करता है। स्टैक के 'टॉप' नामक केवल एक छोर से आइटम जोड़े या हटाए जाते हैं। आइटम कतार के 'रियर' छोर से जोड़े जाते हैं और कतार के 'सामने' से हटा दिए जाते हैं। स्टैक के लिए मूल संचालन 'पुश' और 'पॉप' हैं। एक कतार के लिए बुनियादी संचालन 'enqueue' और 'dequeue' हैं। हम स्टैक के शीर्ष तक पहुंचने के लिए केवल एक पॉइंटर को बनाए रखकर स्टैक पर सभी ऑपरेशन कर सकते हैं। कतारों में, हमें दो बिंदुओं को बनाए रखने की जरूरत है, एक कतार के सामने तक पहुंचने के लिए और दूसरा कतार के पीछे पहुंचने के लिए। ढेर का उपयोग ज्यादातर पुनरावर्ती समस्याओं को हल करने के लिए किया जाता है। आदेशित प्रसंस्करण से संबंधित समस्याओं को हल करने के लिए कतारों का उपयोग किया जाता है।
कतार के अनुप्रयोग
नीचे कतार डेटा संरचना के विभिन्न अनुप्रयोगों पर चर्चा करते हैं।
- कतार डेटा संरचना का उपयोग विभिन्न CPU और डिस्क शेड्यूलिंग में किया जाता है। यहां हमारे पास एक ही समय में सीपीयू या डिस्क की आवश्यकता वाले कई कार्य हैं। सीपीयू या डिस्क समय प्रत्येक कार्य के लिए एक कतार का उपयोग करके निर्धारित किया जाता है।
- कतार का उपयोग प्रिंट स्पूलिंग के लिए भी किया जा सकता है जिसमें प्रिंट नौकरियों की संख्या को एक कतार में रखा जाता है।
- वास्तविक समय प्रणालियों में व्यवधानों की हैंडलिंग एक कतार डेटा संरचना का उपयोग करके की जाती है। उनके आने के क्रम में व्यवधानों को नियंत्रित किया जाता है।
- चौड़ाई-पहली खोज जिसमें अगले स्तर पर आगे बढ़ने से पहले एक पेड़ के पड़ोसी नोड का पता लगाया जाता है, कार्यान्वयन के लिए एक कतार का उपयोग करता है।
- कॉल सेंटर फ़ोन सिस्टम कॉल का उपयोग तब तक करने के लिए कतारों का उपयोग करते हैं जब तक कि वे सेवा प्रतिनिधियों द्वारा उत्तर नहीं दिए जाते हैं।
सामान्य तौर पर, हम यह कह सकते हैं कि कतार डेटा संरचना का उपयोग तब किया जाता है जब हमें संसाधनों या वस्तुओं की आवश्यकता होती है ताकि वे जिस क्रम में आते हैं यानी फर्स्ट आउट।
निष्कर्ष
कतार एक FIFO (फर्स्ट इन, फर्स्ट आउट) डेटा संरचना है जो ज्यादातर उन संसाधनों में उपयोग की जाती है जहां शेड्यूलिंग की आवश्यकता होती है। इसमें दो बिंदुओं पर पीछे और पीछे दो बिंदु होते हैं और इनका उपयोग किसी तत्व को सम्मिलित करने और क्रमशः कतार से / से एक तत्व निकालने के लिए किया जाता है।
हमारे अगले ट्यूटोरियल में, हम कतार के कुछ एक्सटेंशन जैसे प्राथमिकता कतार और परिपत्र कतार के बारे में जानेंगे।
=> पूर्ण सी ++ ट्यूटोरियल सूची देखने के लिए यहां देखें।
अनुशंसित पाठ
- चित्रण के साथ C ++ में प्राथमिकता कतार डेटा संरचना
- एसटीएल में प्राथमिकता कतार
- चित्रण के साथ C ++ में स्टैक डेटा संरचना
- चित्रण के साथ C ++ में परिपत्र लिंक्ड सूची डेटा संरचना
- सी + + में चित्र संरचना के साथ लिंक्ड सूची डेटा संरचना
- संदेह के साथ सी ++ में संदिग्ध रूप से सूचीबद्ध डेटा संरचना
- C ++ में डेटा स्ट्रक्चर्स का परिचय
- JMeter डेटा परिशोधन उपयोगकर्ता परिभाषित चर का उपयोग कर