कतार को गैर-आदिम रैखिक डेटा संरचना के रूप में वर्णित किया जा सकता है, जो एफआईएफओ आदेश का पालन करता है जिसमें डेटा तत्वों को एक छोर (पीछे के छोर) से डाला जाता है और दूसरे छोर (सामने के छोर) से हटा दिया जाता है। कतार की अन्य विविधताएं हैं, परिपत्र कतार, दोगुनी समाप्त कतार और प्राथमिकता कतार।
तुलना चार्ट
| तुलना के लिए आधार | रैखिक कतार | वृत्ताकार कतार |
|---|---|---|
| बुनियादी | एक के बाद एक क्रम में डेटा तत्वों और निर्देशों को व्यवस्थित करता है। | परिपत्र पैटर्न में डेटा को व्यवस्थित करता है जहां अंतिम तत्व पहले तत्व से जुड़ा होता है। |
| कार्य निष्पादन का आदेश | कार्यों को उस क्रम में निष्पादित किया जाता है जिसे वे पहले (FIFO) में रखे गए थे। | किसी कार्य को निष्पादित करने का क्रम बदल सकता है। |
| सम्मिलन और विलोपन | नए तत्व को पीछे के छोर से जोड़ा जाता है और सामने से हटा दिया जाता है। | प्रविष्टि और विलोपन किसी भी स्थिति में किया जा सकता है। |
| प्रदर्शन | अप्रभावी | रैखिक कतार से बेहतर काम करता है। |
रैखिक कतार की परिभाषा
एक रेखीय कतार तर्कसंगत रूप से पहली बार पहली ऑर्डर की गई सूची में है। इसे रैखिक कहा जाता है क्योंकि यह एक सीधी रेखा से मिलता-जुलता है जहां तत्वों को एक के बाद एक तैनात किया जाता है। इसमें तत्वों का एक सजातीय संग्रह होता है जिसमें नए तत्वों को एक छोर पर जोड़ा जाता है और दूसरे छोर से हटा दिया जाता है। कतार की अवधारणा को थिएटर टिकट पाने के लिए टिकट काउंटर के बाहर इंतजार कर रहे दर्शकों की कतार के उदाहरण से समझा जा सकता है। इस कतार में, व्यक्ति टिकट लेने के लिए कतार के पीछे के छोर से जुड़ जाता है और कतार के अंतिम छोर पर टिकट जारी किया जाता है।
कतार में कई ऑपरेशन किए गए हैं
- सबसे पहले कतार को शून्य (यानी खाली) से आरंभ किया जाता है।
- निर्धारित करें कि कतार खाली है या नहीं।
- निर्धारित करें कि कतार भरी है या नहीं।
- पीछे के छोर (एन्क्यू) से नए तत्व का सम्मिलन।
- सामने के छोर (Dequeue) से तत्व का विलोपन।
कतार को दो शिष्टाचार में लागू किया जा सकता है
- सांख्यिकीय रूप से (सरणियों का उपयोग करके)
- गतिशील रूप से (संकेत का उपयोग करके)
रैखिक कतार की सीमा यह है कि यह एक ऐसा परिदृश्य बनाता है जहां कतार में कोई नया तत्व नहीं जोड़ा जा सकता है, भले ही कतार में रिक्त स्थान शामिल हों। यह उपरोक्त स्थिति नीचे दिए गए आंकड़े में चित्रित की गई है। यहां रियर अंतिम इंडेक्स की ओर इशारा कर रहा है जबकि सभी बॉक्स अभी भी खाली हैं, कोई नया तत्व नहीं जोड़ा जा सकता है।
परिपत्र कतार की परिभाषा
एक परिपत्र कतार रैखिक कतार का एक प्रकार है जो रैखिक कतार की सीमा को प्रभावी ढंग से समाप्त कर देती है। वृत्ताकार कतार में, यदि अंतिम स्थान है और स्थान उपलब्ध है, तो कतार के पहले स्थान पर नया तत्व जोड़ा जाता है। जब रैखिक कतार की बात आती है तो सम्मिलन केवल पीछे के छोर से किया जा सकता है और सामने के छोर से विलोपन किया जा सकता है। कतार में क्रमिक विलोपन की श्रृंखला के प्रदर्शन के बाद एक पूर्ण कतार में एक निश्चित स्थिति उत्पन्न होती है, जहां स्थान उपलब्ध होने पर भी कोई नया तत्व आगे नहीं जोड़ा जा सकता है क्योंकि अंडरफ़्लो स्थिति (रियर = अधिकतम - 1) अभी भी मौजूद है।
वृत्ताकार कतार एक संकेतक के माध्यम से दोनों सिरों को जोड़ती है जहां अंतिम तत्व के बाद पहला तत्व आता है। यह कुछ अतिरिक्त तर्क को लागू करके आगे और पीछे का ट्रैक भी रखता है ताकि यह उन तत्वों का पता लगा सके जिन्हें डाला और हटाया जाना है। इसके साथ, जब तक कतार वास्तविक में भरी नहीं होती है, तब तक परिपत्र कतार अतिप्रवाह स्थिति उत्पन्न नहीं करती है।
परिपत्र कतार के बाद कुछ शर्तें:
- फ्रंट को पहले एलिमेंट की ओर इशारा करना चाहिए।
- फ्रंट = रियर होने पर कतार खाली हो जाएगी।
- जब कोई नया तत्व जोड़ा जाता है तो मूल्य एक (रियर = रियर + 1) द्वारा कतार में वृद्धि की जाती है।
- जब एक तत्व कतार से हटा दिया जाता है तो सामने वाले को एक (सामने = सामने + 1) बढ़ा दिया जाता है।
रैखिक कतार और परिपत्र कतार के बीच महत्वपूर्ण अंतर
- रेखीय कतार एक क्रमबद्ध सूची है जिसमें डेटा तत्वों को क्रमबद्ध क्रम में व्यवस्थित किया जाता है। इसके विपरीत, परिपत्र कतार परिपत्र फैशन में डेटा संग्रहीत करती है।
- रेखीय कतार कार्य को निष्पादित करने के लिए FIFO आदेश का पालन करती है (पहली स्थिति में जोड़ा गया तत्व पहली स्थिति में हटा दिया जा रहा है)। इसके विपरीत, परिपत्र कतार में, एक तत्व पर किए गए संचालन का क्रम बदल सकता है।
- तत्वों का सम्मिलन और विलोपन रैखिक कतार में अर्थात पीछे के छोर से और सामने के छोर से हटाने के अलावा तय किया गया है। दूसरी ओर, परिपत्र कतार किसी भी बिंदु से तत्व को डालने और हटाने में सक्षम है जब तक कि वह निर्लिप्त न हो।
- रैखिक कतार मेमोरी स्पेस को बर्बाद करती है जबकि परिपत्र कतार अंतरिक्ष का कुशल उपयोग करती है।
रैखिक कतार का कार्यान्वयन
नीचे दिया गया एल्गोरिथ्म एक कतार में तत्वों के जोड़ को दिखाता है:
कतार को स्टोर करने के लिए एक सरणी सहित तीन डेटा चर की जरूरत है और सामने और पीछे की प्रारंभिक स्थिति को स्टोर करने के लिए अन्य -1 है।
सम्मिलित करें (आइटम, कतार, एन, रियर) {अगर (रियर == एन) तो "कतार अतिप्रवाह" प्रिंट करें; और {पीछे = पीछे + 1; कतार [पीछे] = आइटम; }} नीचे दिया गया एल्गोरिथ्म एक कतार में तत्वों के विलोपन को दर्शाता है:
Delete_circular (आइटम, कतार, पीछे, सामने) {अगर (रियर == सामने) तो "कतार अंडरफ्लो" प्रिंट करें; और {सामने = सामने + 1; आइटम = कतार [सामने]; }} वृत्ताकार कतार का कार्यान्वयन
परिपत्र कतार में तत्व के अतिरिक्त की व्याख्या करने के लिए एक एल्गोरिथ्म:
आवेषण_कार्युलर (आइटम, कतार, पीछे, सामने) {रियर = (रियर + 1) मॉड एन; यदि (सामने == पीछे) तो "कतार पूर्ण है" प्रिंट करें; और {कतार [पीछे] = आइटम; }} एल्गोरिथ्म परिपत्र कतार में तत्व को हटाने की व्याख्या करता है:
delete_circular (आइटम, कतार, पीछे, सामने) {अगर (सामने == पीछे) तो प्रिंट करें ("कतार खाली है"); और {सामने = सामने + 1; आइटम = कतार [सामने]; }} निष्कर्ष
रैखिक कतार कुछ मामलों में अक्षम है जहां सम्मिलन ऑपरेशन करने के लिए तत्वों को रिक्त स्थानों में स्थानांतरित करना आवश्यक है। यही कारण है कि यह भंडारण स्थान को बर्बाद करने के लिए जाता है जबकि परिपत्र कतार भंडारण स्थान का उचित उपयोग करता है क्योंकि तत्व किसी भी स्थिति में जोड़े जाते हैं यदि कोई खाली स्थान मौजूद है।
