“हम कह सकते हैं कि हम चाहते हैं कि वेब दुनिया के एक ऐसे दृष्टिकोण को दर्शाए जहाँ सब कुछ लोकतांत्रिक रूप से किया जाता है। ऐसा करने के लिए, हम कंप्यूटरों को एक-दूसरे से इस तरह बातचीत करवाते हैं कि वह आदर्श बढ़ावा मिले।”

$\quad$ - टिम बर्नर्स-ली

4.1 कतार का परिचय

पिछले अध्याय में हमने एक डेटा संरचना स्टैक के बारे में सीखा, जो अंतिम-आया-पहले-बाहर (LIFO) सिद्धांत पर काम करता है। इस अध्याय में हम एक अन्य डेटा संरचना कतार के बारे में सीखेंगे जो पहले-आया-पहले-बाहर (FIFO) सिद्धांत पर काम करती है। कतार तत्वों की एक क्रमबद्ध रैखिक सूची है, जिसमें तत्वों को जोड़ने और हटाने के लिए अलग-अलग सिरे होते हैं।

चित्र 4.1: बैंक में लोगों की कतार

हमारे दैनिक जीवन में कतार के उदाहरणों में सुबह की सभा के लिए कतार में खड़े छात्र, बैंक में कैश काउंटर पर ग्राहकों की बनी कतार (चित्र 4.1), ईंधन पंपों पर वाहनों की कतार (चित्र 4.2) आदि शामिल हैं।

चित्र 4.2: पेट्रोल पंप पर कारों की कतार

4.1.1 पहले आया पहले बाहर (FIFO)

कतार (Queue) प्रथम आया प्रथम निकला (FIFO) के सिद्धांत का अनुसरण करती है, क्योंकि कतार में सबसे पहले प्रवेश करने वाला तत्व ही सबसे पहले बाहर निकलेगा। इस प्रकार, जो तत्व कतार में सबसे लंबे समय से है, वह पहले हटाया जाएगा। इसे प्रथम आया प्रथम सेवित (FCFS) दृष्टिकोण भी कहा जाता है। कतार एक ऐसी व्यवस्था है जिसमें नई वस्तुओं/आइटमों को हमेशा एक सिरे पर जोड़ा जाता है, जिसे आमतौर पर पिछला (REAR) कहा जाता है, और वस्तुओं/आइटमों को हमेशा दूसरे सिरे से हटाया जाता है, जिसे आमतौर पर कतार का सामने (FRONT) कहा जाता है। REAR को TAIL और FRONT को HEAD भी कहा जाता है।

4.1.2 कतार के अनुप्रयोग

(A) कतार की अवधारणा के वास्तविक जीवन में कई अनुप्रयोग हैं:

• यदि एक ट्रेन टिकट वेटिंग लिस्ट में है (जैसे W/L1), इसका अर्थ है कि टिकट उन टिकटों की कतार में है जो वेटिंग नंबर के बढ़ते क्रम के अनुसार पुष्टि की प्रतीक्षा कर रहे हैं। यदि कोई पुष्टिकृत टिकट रद्द हो जाता है, तो W/L1 नंबर वाला टिकट वेटिंग कतार के FRONT से हटाकर पुष्टि किया जाता है।
• कभी-कभी किसी ग्राहक सेवा केंद्र पर कॉल करने पर, इंटरैक्टिव वॉयस रिस्पॉन्स सिस्टम (IVRS) हमें तब तक प्रतीक्षा करने के लिए कहता है जब तक कोई सहायक व्यक्ति उपलब्ध न हो। यहाँ कॉल को उन ग्राहकों की कतार में डाला जाता है जो सेवा की प्रतीक्षा कर रहे हैं।
• कल्पना कीजिए कि एकल-पट्टी वाली एकतरफा सड़क है, तो वाहन जो पहले प्रवेश करता है वह पहले बाहर निकलेगा, कतार की अवधारणा का अनुसरण करते हुए। इसी प्रकार, राजमार्ग टोल टैक्स बूथ पर वाहनों को FIFO सिद्धांत के अनुसार सेवा दी जाती है।

(B) कंप्यूटर विज्ञान में कतार के अनुप्रयोग के कुछ उदाहरण निम्नलिखित हैं:

• मान लीजिए एक वेब-सर्वर है जो परिणाम घोषित करने वाली वेब-साइट होस्ट कर रहा है। यह सर्वर अधिकतम 50 समवर्ती अनुरोधों को परिणाम देखने के लिए संभाल सकता है। इसलिए, हजारों उपयोगकर्ता अनुरोधों को सेवा देने के लिए, Queue सबसे उपयुक्त डेटा संरचना होगी।
• कुछ ऑपरेटिंग सिस्टम (OS) को कई कार्यों को संभालना होता है जिन्हें जॉब्स कहा जाता है, जो प्रोसेसर का उपयोग करना चाहते हैं। लेकिन हम जानते हैं कि एक प्रोसेसर एक समय में केवल एक कार्य को संभाल सकता है। इसलिए, एक बहु-कार्य ऑपरेटिंग सिस्टम में, जॉब्स को लाइन में लगाया जाता है (queued) और फिर किसी क्रम के अनुसार प्रोसेसर तक पहुंच दी जाती है। सबसे सरल तरीका यह है कि प्रोसेसर तक पहुंच FIFO आधार पर दी जाए, यानी उस क्रम में जिसमें जॉब्स प्रोसेसर के लिए अनुरोध के साथ आती हैं।
• जब हम एक ही कंप्यूटर से या विभिन्न कंप्यूटरों से साझा प्रिंटर का उपयोग करके कई फाइलों से प्रिंट कमांड भेजते हैं। OS इन प्रिंट अनुरोधों को एक queue में डालता है और उन्हें FIFO आधार पर एक-एक करके प्रिंटर को भेजता है।

4.2 QUEUE पर संचालन

FIFO दृष्टिकोण का अनुसरण करते हुए, डेटा संरचना queue निम्नलिखित संचालनों का समर्थन करती है:

• ENQUEUE: का उपयोग किसी नए तत्व को पंक्ति के पिछले सिरे पर डालने के लिए किया जाता है। हम तब तक पंक्ति में तत्व डालते रह सकते हैं जब तक उसमें और तत्व जोड़ने की जगह बची है। पंक्ति की क्षमता से अधिक तत्व डालने पर एक अपवाद उत्पन्न होगा—जिसे ओवरफ़्लो कहा जाता है।
• DEQUEUE: का उपयोग पंक्ति के सामने से एक-एक कर तत्व हटाने के लिए किया जाता है। हम तब तक तत्व हटा सकते हैं जब तक पंक्ति खाली नहीं हो जाती; खाली पंक्ति से तत्व हटाने का प्रयास करने पर एक अपवाद उत्पन्न होगा—जिसे अंडरफ़्लो कहा जाता है।

पंक्ति पर एनक्यू और डीक्यू को दक्षता से करने के लिए निम्नलिखित संचालन भी आवश्यक हैं:

• IS EMPTY: यह जांचने के लिए उपयोग होता है कि पंक्ति में कोई तत्व है या नहीं, ताकि डीक्यू संचालन करते समय अंडरफ़्लो अपवाद से बचा जा सके।

सोचिए और विचार कीजिए

वेब-सर्वर उदाहरण (परिणाम घोषणा) में मान लीजिए सर्वर को प्रशासक की ओर से किसी विद्यालय का परिणाम तत्काल देखने का अनुरोध प्राप्त होता है, साथ ही छात्रों की ओर से अपने-अपने परिणाम देखने के अन्य अनुरोध भी आ रहे हैं। क्या आप कोई ऐसी रणनीति सुझा सकते हैं जिससे सभी को उनकी तात्कालिकता के अनुसार सेवा मिल सके?

• PEEK: पंक्ति के सामने वाले तत्व को पंक्ति से हटाए बिना देखने के लिए उपयोग होता है।
• IS FULL: यह जांचने के लिए उपयोग होता है कि पंक्ति में और तत्व जोड़े जा सकते हैं या नहीं, ताकि एनक्यू संचालन करते समय ओवरफ़्लो अपवाद से बचा जा सके।

आकृति 4.3 एक साधारण पंक्ति के विभिन्न चरणों को दर्शाती है जिसमें वर्णमाला के अक्षर हैं। आकृति में पंक्ति का फ्रंट बाईं ओर तथा रियर दाईं ओर है।

चित्र 4.3: स्टैक संचालन के विभिन्न चरण

कतार को लागू करने के लिए सूची का उपयोग करते समय, हम सूची के किसी भी सिरे को कतार का अग्र भाग (Front) या पिछला भाग (Rear) निर्धारित कर सकते हैं। लेकिन हमें दोनों सिरों में से किसी एक सूचकांक index[0] या index[n-1] को अग्र भाग के रूप में निर्धारित करना होगा और विपरीत सिरे को पिछला भाग के रूप में निर्धारित करना होगा।

4.3 पायथन का उपयोग करके कतार का कार्यान्वयन

कई तरीके हैं जिनसे कतार को कंप्यूटर प्रोग्राम में लागू किया जा सकता है, एक तरीका पायथन के सूची डेटा प्रकार का उपयोग करना है। प्रोग्राम में कतार संरचना बनाने के लिए, निम्नलिखित फ़ंक्शनों को परिभाषित करने की आवश्यकता है:

• आइए एक कतार बनाएँ जिसका नाम myQueue है। हम इसे एक खाली सूची निर्धारित करके बना सकते हैं।

myQueue = list()

• एक फ़ंक्शन (enqueue) जो कतार के अंत में एक नया तत्व सम्मिलित करता है। इस फ़ंक्शन में दो पैरामीटर होते हैं - कतार का नाम और वह तत्व जिसे कतार में सम्मिलित किया जाना है।

def enqueue(myQueue, element):
$\quad$ myQueue.append(element)

नोट: append() फ़ंक्शन हमेशा सूची के अंत में एक तत्व जोड़ता है, इसलिए यह कतार के पिछले भाग (Rear) में जोड़ता है।

• हमें Is Full को लागू करने की आवश्यकता नहीं है, क्योंकि Python एक गतिशील भाषा है, यह निश्चित आकार की सूची बनाने की मांग नहीं करता। इसलिए, हमें कभी भी ऐसी स्थिति का सामना नहीं करना पड़ेगा जब कतार भरी हुई हो।
• एक फ़ंक्शन (isEmpty) जांचने के लिए, क्या कतार में कोई तत्व है या नहीं? यह कतार की लंबाई की जांच करके किया जा सकता है। फ़ंक्शन में एक पैरामीटर है – कतार का नाम और यदि कतार खाली है तो True लौटाता है अन्यथा False।

def isEmpty(myQueue):
$\quad$ if len(myQueue)==0:
$\qquad$ return True
$\quad$ else:
$\qquad$ return False

• एक फ़ंक्शन (dequeue) कतार के सामने से एक तत्व को हटाने के लिए। इसमें एक पैरामीटर है - कतार का नाम और हटाया गया तत्व लौटाता है। फ़ंक्शन पहले यह जांचता है कि कतार खाली है या नहीं, सफल हटाने के लिए।

def dequeue(myQueue):
$\quad$ if not (isEmpty(myQueue)):
$\qquad$ return myQueue.pop(0)
$\quad$ else :
$\qquad$ print(“Queue is empty”)

नोट: index[0] के साथ pop() फ़ंक्शन सूची की शुरुआत से तत्व को हटा देगा, इसलिए कतार का सामने।

• एक फ़ंक्शन (size) कतार में तत्वों की संख्या प्राप्त करने के लिए। हम Python की सूची के len() फ़ंक्शन का उपयोग करके कतार में तत्वों की संख्या ज्ञात कर सकते हैं। फ़ंक्शन में एक पैरामीटर है - कतार का नाम और कतार में तत्वों की संख्या लौटाता है।

def size(myQueue):
$\quad$ return len(myQueue)

• एक फ़ंक्शन (peek) जो केवल पढ़ता है, लेकिन कतार के सामने वाले तत्व को हटाता नहीं। इसके लिए हम कतार के index[0] पर मौजूद तत्व को पढ़ सकते हैं। इस फ़ंक्शन में एक पैरामीटर होता है - कतार का नाम और यदि कतार खाली नहीं है तो Front पर मौजूद तत्व का मान लौटाता है, अन्यथा None।

def peek(myQueue):
$\quad$ if isEmpty(myQueue):
$\qquad$ print(‘Queue is empty’)
$\quad$ return None
$\quad$ else:
$\qquad$ return myQueue[0]

सोचिए और विचार कीजिए

क्या आप tuple या dictionary का उपयोग करके queue डेटा संरचना को लागू कर सकते हैं? ऊपर दिए गए फ़ंक्शनों के नाम चुनते समय queue के संदर्भ में सामान्य नामकरण परंपरा का पालन किया गया है। चूंकि ये उपयोगकर्ता-परिभाषित फ़ंक्शन हैं, कोई अन्य नाम भी उपयोग किया जा सकता है।

आइए एक ऐसी कतार का उदाहरण लें जो लोग बैंक के कैश काउंटर पर प्रतीक्षा करते समय बनाते हैं। आमतौर पर, कतार में निम्नलिखित घटनाएं होती हैं:

गतिविधि 4.1

आप एक खाली कतार को प्रिंट करने का प्रयास करते समय None को प्रिंट होने से कैसे रोक सकते हैं?

• दो दोस्त साथ आते हैं और कैश काउंटर पर जाते हैं, अर्थात वे एक कतार बनाते हैं – enqueue ऑपरेशन दो बार किया जाता है।
• जैसे ही सामने वाले व्यक्ति की सेवा हो जाती है, उसे कतार से हटा दिया जाता है – इस प्रकार dequeue ऑपरेशन किया जाता है। कैशियर अगले व्यक्ति को बुलाता है जो अब कतार के सामने है।
• कैशियर कतार की लंबाई जानना चाहता है – कतार का आकार जांचा जाता है।
• इस बीच, कुछ और लोग बैंक में आते हैं, और उनमें से तीन कैश काउंटर पर कतार में शामिल होते हैं, अर्थात enqueue 3 बार होता है।
• एक और व्यक्ति की सेवा हो जाती है और वह काउंटर छोड़ देता है, अर्थात dequeue किया जाता है। कैशियर अगले व्यक्ति को बुलाता है।
• अगले तीन लोगों की एक के बाद एक सेवा होती है, अर्थात dequeue तीन बार किया जाता है।
• कैशियर अगले को बुलाता है और महसूस करता है कि सेवा के लिए कोई और व्यक्ति नहीं बचा है – अंडरफ़्लो स्थिति होती है।

अब, आइए उपरोक्त बैंक के परिदृश्य के लिए कोड लिखें।

गतिविधि 4.2

यदि पूरी कतार की सामग्री को सूचीबद्ध करना हो तो क्या होगा? इसके लिए एक फ़ंक्शन लिखें।

प्रोग्राम 4-1

myQueue = list()
#प्रत्येक व्यक्ति को P1, P2, P3,… के रूप में कोड दिया जाएगा
element = input(“enter person’s code to enter in queue :”)
enqueue(myQueue,element)
element = input(“enter person’s code for insertion in queue :”)
enqueue(myQueue,element)
print(“person removed from queue is:”, dequeue(myQueue))
print(“Number of people in the queue is :”,size(myQueue))
element = input(“enter person’s code to enter in queue :”)
enqueue(myQueue,element)
element = input(“enter person’s code to enter in queue :”)
enqueue(myQueue,element)
element = input(“enter person’s code to enter in queue :”)
enqueue(myQueue,element)
print(“Now we are going to remove remaining people from the
queue”)
while not isEmpty(myQueue):
$\quad$ print(“person removed from queue is “,
$\quad$ dequeue(myQueue))

आउटपुट

enter person’s code to enter in queue :P1
enter person’s code to enter in queue :P2
person removed from the queue is :p1
number of people in the queue is :1
enter person’s code to enter in queue :P3
enter person’s code to enter in queue :P4
enter person’s code to enter in queue :P5
Now we are going to remove remaining people from the queue
person removed from the queue is :p2
person removed from the queue is :p3
person removed from the queue is :p4
person removed from the queue is :p5
Queue is empty

4.4 डेक का परिचय

डेक (उच्चारण “डेक”) एक ऐसी व्यवस्था है जिसमें तत्वों की जोड़ी और हटाना किसी भी सिरे से हो सकता है, अर्थात् सिर/सामने या पूंछ/पीछे। यह डेटा संरचना किसी भी ओर से तत्वों की जोड़ी/हटाने पर कोई प्रतिबंध नहीं लगाती, इसलिए इसे प्रोग्राम में स्टैक या क्यू को लागू करने के लिए उपयोग किया जा सकता है। इसे डबल एंडेड क्यू भी कहा जाता है, क्योंकि यह किसी भी सिरे से सम्मिलन, विलोपन संचालन की अनुमति देता है।

चित्र 4.4: डेक की मूल संरचना जो सिर और पूंछ को दिखाती है ताकि स्टैक या क्यू लागू किया जा सके।

4.4.1 डेक के अनुप्रयोग

• एक ट्रेन टिकट खरीदने वाले काउंटर पर, टिकट खरीदने के लिए लोगों की एक सामान्य कतार बनती है। सामने वाले व्यक्ति ने टिकट खरीदा और काउंटर छोड़ दिया। कुछ देर बाद वे कुछ पूछने के लिए वापस काउंटर पर आते हैं। चूँकि वे पहले ही टिकट खरीद चुके हैं, उन्हें कतार में सामने से शामिल होने का विशेषाधिकार हो सकता है।

• हाईवे टोल टैक्स बूथ पर वाहनों को कतार के सिद्धांत के अनुसार सेवा दी जाती है। यदि टोल गेट पर समानांतर बूथ हैं तो कई कतारें होती हैं। यदि किसी बूथ के सभी वाहनों की सेवा हो जाती है तो अन्य बूथ(ों) के वाहनों को खाली बूथ के सामने कतार बनाने को कहा जाता है। इसलिए, उन कतारों के अंत में खड़े वाहन वर्तमान बूथ को छोड़ देंगे (जिस छोर से कतार में शामिल हुए थे उस छोर से हटा दिए जाएंगे) और खाली बूथ पर कतार में शामिल हो जाएंगे।

गतिविधि 4.3

एक डेक में, यदि तत्वों को समान छोर से सम्मिलित और हटाया जाता है, तो यह व्यवहार करेगा

1. कतार
2. स्टैक
3. सूची
4. उपरोक्त में से कोई नहीं

निम्नलिखित कुछ उदाहरण हैं जहां डेटा संरचना डेक का उपयोग कंप्यूटर विज्ञान में किया जा सकता है:

• ब्राउज़र इतिहास (URL) को बनाए रखने के लिए, आमतौर पर एक स्टैक का उपयोग किया जाता है, क्योंकि जब कोई टैब बंद किया जाता है और यदि आप ctrl+shift+T दबाते हैं, तो सबसे हाल ही में बंद किया गया URL पहले खुलता है। चूंकि इतिहास में संग्रहीत किए जा सकने वाले URL की संख्या निश्चित होती है, इसलिए जब URL की यह सूची बड़ी हो जाती है, तो सूची के अंत से URL (अर्थात् जो सबसे कम देखे गए थे) हटा दिए जाते हैं।

• किसी भी टेक्स्ट एडिटर में Do और Undo विकल्प प्रदान करने में भी यही होता है।

• यह जाँचने के लिए कि दिया गया स्ट्रिंग पैलिन्ड्रोम है या नहीं? स्ट्रिंग को बाएँ से दाएँ (अक्षर दर अक्षर) प्रोसेस करें और उसे डेक की पूंछ/रियर से सामान्य कतार की तरह डालें। एक बार पूरी स्ट्रिंग प्रोसेस हो जाने (यानी डेक में डाल दिए जाने) के बाद हम दोनों सिरों से एक-एक अक्षर निकालेंगे (हटाएँगे) और उनकी मिलान तब तक करते रहेंगे जब तक कोई अक्षर बचा न हो या डेक में केवल एक अक्षर बचा हो। इनमें से किसी भी स्थिति में स्ट्रिंग पैलिन्ड्रोम है।

गतिविधि 4.4

एक डेक में, यदि तत्वों का समावेश और विलोप विपरीत सिरों से किया जाए, तो वह व्यवहार करेगा

1. Queue
2. Stack
3. List
4. None of the above

4.4.2 डेक पर संचालन

• INSERTFRONT: यह संचालन डेक के सामने एक नया तत्व डालने के लिए प्रयोग होता है।
• INSERTREAR: यह संचालन सामान्य कतार के समान है, यानी डेक के पिछले भाग में नया तत्व डालना।
• DELETIONFRONT: यह संचालन सामान्य कतार के समान है, यानी डेक के सामने से एक तत्व हटाना।
• DELETIONREAR: यह संचालन डेक के पिछले भाग से एक-एक तत्व हटाने के लिए प्रयोग होता है।

उपरोक्त संचालनों को डेक पर दक्षता से करने के लिए हमें सामान्य कतार में प्रयोग होने वाले सभी सहायक संचालनों—जैसे Is Empty, Peek, Size—की आवश्यकता होगी।

आइए समझें कि ये संचालन एक स्ट्रिंग के पैलिन्ड्रोम होने की जाँच करने के लिए, निम्नलिखित एल्गोरिद्म के माध्यम से डेक का उपयोग करते हुए कैसे काम करते हैं।

एल्गोरिद्म 4.1

चरण 1: स्ट्रिंग (madam) को बाएँ ओर से एक-एक अक्षर के हिसाब से घूमना शुरू करें।

चरण 2: अक्षर को सामान्य कतार की तरह INSERTREAR का उपयोग करके डेक में डालें।

चरण 3: स्ट्रिंग (madam) के सभी वर्णों के लिए चरण 1 और चरण 2 को दोहराएँ

चित्र 4.5: चौथी पुनरावृत्ति के बाद डेक की स्थिति

चरण 4: डेक के सामने से एक वर्ण और पिछले सिरे से एक वर्ण को DELETIONFRONT और DELETIONREAR का उपयोग करके हटा सकते हैं।

चित्र 4.6: दोनों सिरों से एक-एक वर्ण हटाने के बाद डेक की स्थिति

चरण 5: इन दोनों हटाए गए वर्णों की तुलना करें।

चरण 6: यदि वे समान हैं तो

चरण 4 और 5 को तब तक दोहराएँ जब तक डेक खाली न हो जाए या केवल एक वर्ण शेष न रह जाए, अंततः स्ट्रिंग पैलिंड्रोम है

अन्यथा रुक जाएँ क्योंकि स्ट्रिंग पैलिंड्रोम नहीं है

4.5 पायथन का उपयोग करके डेक का कार्यान्वयन

कतार की तरह, डेक भी एक क्रमबद्ध रैखिक सूची है, इसलिए हम अपने कार्यक्रम में डेक बनाने के लिए सूची डेटा प्रकार का उपयोग करते हैं। कार्यक्रम में निम्नलिखित फ़ंक्शन/कथन परिभाषित होने चाहिए:

• एक डेक बनाने के लिए एक कथन, जिसका नाम myDeque है।
  myDeque = list()

• एक फ़ंक्शन insertFront(), डेक के सामने एक तत्व डालने के लिए जिसमें दो पैरामीटर होते हैं — डेक का नाम और डाला जाने वाला तत्व। चूँकि तत्व शुरुआत में डालना है, हम इसके लिए index 0 के साथ insert() का उपयोग करेंगे।

def insertFront(myDeque, element):
$\quad$ myDeque.insert(0,element)

• एक फ़ंक्शन insertRear(), डेक के पिछले हिस्से में एक तत्व डालने के लिए। इसका कार्यान्वयन सामान्य क्यू की enqueue() जैसा होगा और इसमें भी insertFront() जैसे ही दो पैरामीटर होंगे।
• एक फ़ंक्शन isEmpty(), डेक में तत्वों की उपस्थिति की जाँच करने के लिए, जो सामान्य क्यू के लिए परिभाषित समान नाम वाले फ़ंक्शन के समान होगा।
• एक फ़ंक्शन deletionRear(), डेक के पिछले हिस्से से एक तत्व हटाने के लिए। इसे केवल डेक का नाम चाहिए होता है और यह हटाया गया तत्व लौटाता है। हम डेक के अंतिम तत्व को हटाने के लिए बिना पैरामीटर के pop() का उपयोग करेंगे।

def deletionRear(myDeque):
$\quad$ if not (isEmpty()):
$\qquad$ return myDeque.pop()
$\quad$ #removing data from end of list
$\quad$ else :
$\qquad$ print(“Deque empty”)

• एक फ़ंक्शन deletionFront(), डेक के सामने से एक तत्व हटाने के लिए। इसका कार्यान्वयन सामान्य क्यू की dequeue() जैसा होगा।
• एक फ़ंक्शन getFront(), डेक के सामने से मान पढ़ने के लिए, बिना उसे कतार से हटाए, जब कतार खाली न हो। यह पैरामीटर के रूप में डेक का नाम लेता है और मान की एक प्रति लौटाता है।

def getFront(mydeque):
$\quad$ if not (isEmpty()):
$\qquad$ return mydeque[0]
$\quad$ else :
$\qquad$ print(“ Queue empty”)

• एक फंक्शन getRear(), डेक के रियर से मान पढ़ने के लिए, बिना उसे डेक से हटाए।
  यह फंक्शन डेक को आर्गुमेंट के रूप में लेता है और जब क्यू खाली न हो तो मान की कॉपी लौटाता है।

def getRear(mydeque):
$\quad$ if not (isempty()):
$\qquad$ return mydeque[len(mydeque)-1]
$\quad$ else :
$\qquad$ print(“ Deque empty”)

आइए एक main() फंक्शन लिखें जो विभिन्न डेक फंक्शन्स को इनवोक करे:

प्रोग्राम 4-2 पायथन में डेक का इम्प्लीमेंटेशन

def insertFront(myDeque,element):
$\quad$ myDeque.insert(0,element)

def getFront(myDeque):
$\quad$ if not (isEmpty(myDeque)):
$\qquad$ return myDeque[0]
$\quad$ else:
$\qquad$ print(“Queue underflow”)

def getRear(myDeque):
$\quad$ if not (isEmpty(myDeque)):
$\qquad$ return myDeque[len(myDeque)-1]
$\quad$ else:
$\qquad$ print (“Queue underflow”)

def insertRear(myDeque,element):
$\quad$ myDeque.append(element)

def isEmpty(myDeque):
$\quad$ if len(myDeque) == 0:
$\qquad$ return True
$\quad$ else:
$\qquad$ return False

def deletionRear(myDeque):
$\quad$ if not isEmpty(myDeque):
$\qquad$ return myDeque.pop()
$\quad$ else:
$\qquad$ print(“Queue underflow”)

def deletionFront(myDeque):
$\quad$ if isEmpty(myDeque):
$\qquad$ print(“Queue underflow”)
$\quad$ else:
$\qquad$ return myDeque.pop(0)

def main():
    dQu = list()
    choice = int(input('enter 1 to use as normal queue 2 otherwise : '))
    if choice == 1:
        element = input("data for insertion at rear ")
        insertRear(dQu,element)
        element = getFront(dQu)
        print("data at the beginning of queue is ", element)
        element = input("data for insertion at front ")
        insertRear(dQu,element)
        print('data removed from front of queue is ', deletionFront(dQu))
        print('data removed from front of queue is ', deletionFront(dQu))

आउटपुट

enter 1 to use as normal queue 2 otherwise : 1
data for insertion at rear 23
data at the beginning of queue is 23
data for insertion at rear 45
data removed from front of queue is 23
data removed from front of queue is 45
Queue underflow
data removed from front of queue is None

enter 1 to use as normal queue 2 otherwise : 2
data for insertion at front 34
data at the end of queue is 34
data for insertion at front 56
data removed from rear of queue is 34
data removed from rear of queue is 56
Queue underflow
data removed from rear of queue is None

सारांश

• कतार एक क्रमबद्ध रैखिक डेटा संरचना है, जो FIFO रणनीति का पालन करती है।
• फ्रंट और रियर का उपयोग कतार की शुरुआत और अंत को दर्शाने के लिए किया जाता है।
• Python में, पूर्वनिर्धारित विधियों के उपयोग से फ्रंट और रियर का ध्यान रखा जाता है।
• कतार में सम्मिलन रियर छोर पर होता है। विलोपन फ्रंट पर होता है।
• सम्मिलन संचालन को एनक्यू कहा जाता है और विलोपन संचालन को डीक्यू कहा जाता है।
• एनक्यू और डीक्यू संचालनों का समर्थन करने के लिए, isEmpty, isfull और peek संचालनों का उपयोग किया जाता है
• डेक कतार का एक संस्करण है, जो दोनों छोरों पर सम्मिलन और विलोपन की अनुमति देता है।
• एक डेक स्टैक और कतार दोनों संचालनों का समर्थन कर सकता है।
• डेक द्वारा समर्थित अन्य संचालन हैं insertfront, insertrear, deletefront, deleterear, getfront, getrear, isempty और isfull।

अभ्यास

1. रिक्त स्थान भरें

क) _____________ एक रैखिक सूची है जिसमें तत्वों को भिन्न-भिन्न सिरों से सम्मिलित और हटाया जाता है।
ख) कतार पर संचालन _____________ क्रम में किए जाते हैं।
ग) कतार में सम्मिलन संचालन को कहा जाता है और कतार में विलोपन संचालन को _____________ कहा जाता है।
घ) तत्वों का विलोपन कतार के _____________ सिरे से किया जाता है।
ङ) कतार में तत्व ‘A’, ‘S’, ‘D’ और ‘F’ मौजूद हैं और उन्हें एक-एक करके हटाया जाता है, तो _____________ तत्व प्राप्त होने का क्रम है।
च) _____________ एक ऐसा डेटा संरचना है जिसमें तत्वों को या तो सिरे से जोड़ा या हटाया जा सकता है, पर बीच से नहीं।
छ) एक डेक में ‘z’, ‘x’, ‘c’, ‘v’ और ‘b’ हैं। विलोपन के बाद प्राप्त तत्व ‘z’, ‘b’, ‘v’, ‘x’ और ‘c’ हैं। _____________ डेक पर किए गए विलोपन संचालनों का क्रम है।

2. कतार और स्टैक की तुलना और विरोधाभास कीजिए।

3. FIFO कतार का वर्णन कैसे करता है?

4. कतार का उपयोग करते हुए एक मेनू-चालित पायथन प्रोग्राम लिखिए जो शटलकॉक के बॉक्स में उसकी गति को लागू करता है।

5. कतार डेटा प्रकार डेक डेटा प्रकार से किस प्रकार भिन्न है?

6. प्रत्येक संचालन के बाद कतार की स्थिति दिखाइए
enqueue (34)
enqueue (54)
dequeue ( )
enqueue (12)
dequeue( )
enqueue (61)
peek( )
dequeue( )
dequeue( )
dequeue( )
dequeue( )
enqueue (1)

7. प्रत्येक संचालन के बाद डेक की स्थिति दिखाइए
peek ( )
insertFront (12)
insertRear (67)
deletionFront ( )
insertRear (43)
deletionRear( )
deletionFront ( )
deletionRear( )

8. एक पायथन प्रोग्राम लिखें जो दी गई स्ट्रिंग पैलिंड्रोम है या नहीं, डेक का उपयोग करके जाँच करे। (संकेत: एल्गोरिद्म 4.1 देखें)