कैसे और क्यों दो स्टैक पर कतार लगाना है

नमस्कार, हेब्र!

यह पोस्ट ओलंपियाड प्रोग्रामिंग और नौसिखिया डेवलपर्स में शुरुआती लोगों के लिए लिखा गया था, जो एल्गोरिदमिक साक्षात्कार से गुजरने की तैयारी कर रहे हैं। बोनस पहेली के अंत में। अगर दिलचस्पी है, मैं एक बिल्ली के लिए पूछना :)

सबसे पहले, आइए मूल बातें याद करें:

अनेकता

स्टैक एलआईएफओ के सिद्धांत को लागू करता है (इंजी। अंतिम में - पहले बाहर, "आखिरी बार, पहले बाहर आओ")।

स्टैक के दो मुख्य ऑपरेशन हैं:

• धक्का - स्टैक पर एक आइटम धक्का
• पॉप - स्टैक से एक तत्व मिलता है

स्टैक आमतौर पर एक सरणी पर लागू किया जाता है (अभी भी एक लिंक्ड सूची पर संभव है)। आप स्टैक और इसके कार्यान्वयन के बारे में अधिक पढ़ सकते हैं ।

बारी

एक कतार FIFO तत्वों तक पहुंच के साथ एक डेटा संरचना है (पहली बार, पहले बाहर - "पहले आओ, पहले पाओ")

एक कतार के इंटरफ़ेस में दो मुख्य विधियाँ हैं:

• धक्का - कतार के अंत में एक आइटम रखो
• पॉप - कतार के सामने से एक तत्व प्राप्त करें

यहाँ नियमित कतार के बारे में अधिक पढ़ें।

आमतौर पर कतार के कार्यान्वयन के लिए दो बुनियादी तरीकों पर विचार करें:

1. सरणी पर
2. एक लिंक्ड सूची पर

लाइन से स्टैक कूलर क्यों है

कल्पना करें कि हमारी डेटा संरचना को संचालन के निम्नलिखित सेट का समर्थन करना चाहिए:

• न्यूनतम समर्थन (न्यूनतम)
• अधिकतम समर्थन (अधिकतम)
• Gcd समर्थन (अंग्रेजी का सबसे बड़ा सामान्य भाजक - सबसे बड़ा सामान्य भाजक)
• Lcm समर्थन (कम से कम सामान्य कई)

ये सभी ऑपरेशन एसोसिएटिव हैं (एक सेमीग्रुप बनाते हैं), लेकिन उनमें से किसी में एक व्युत्क्रम तत्व नहीं है (समूह नहीं बनता है)।

स्टैक के लिए, आप बस निम्न में से किसी भी ऑपरेशन का समर्थन कर सकते हैं: बस इसके शीर्ष पर एक जोड़े को स्टोर करें:

$$

$$(तत्व, OperationResult)$$

जहां युग्म का दूसरा तत्व स्टैक के सभी तत्वों पर लागू ऑपरेशन का परिणाम है।

नीचे पायथन में न्यूनतम स्टैक समर्थन कार्यान्वयन का एक उदाहरण है:

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

अब सोचें कि कतार के साथ एक ही चाल कैसे करें? यदि आप एक सरणी पर आयोजित क्लासिक कतार के साथ प्रयास करते हैं, तो यह संभावना नहीं है कि कुछ काम करेगा। यह इस तथ्य के कारण है कि न्यूनतम ऑपरेशन में उलटा ऑपरेशन नहीं होता है (जैसे अतिरिक्त ऑपरेशन में घटाव ऑपरेशन होता है, उदाहरण के लिए)। जैसा कि आपने अनुमान लगाया होगा, तब मैं दो स्टैक पर एक कतार के तथाकथित-क्लासिक कार्यान्वयन के बारे में बात करूंगा।

दो ढेर कतार

जो मुख्य शर्त पूरी की जानी चाहिए वह यह है कि सभी परिचालनों को परिशोधन O (1) के लिए किया जाना चाहिए।

दो स्टैक लें: एस 1 और एस 2।

पुश ऑपरेशन हमेशा s1 स्टैक पर किया जाएगा।

पॉप ऑपरेशन निम्नानुसार आयोजित किया जाएगा: यदि s2 स्टैक खाली है, तो हम पॉप और पुश करने के लिए क्रमिक कॉल द्वारा s1 से s2 तक सभी तत्वों को स्थानांतरित करते हैं। अब s2 स्टैक में रिवर्स ऑर्डर में तत्व शामिल हैं (सबसे ऊपरी तत्व हमारी बारी में डाला गया पहला तत्व है)।

यदि s2 खाली नहीं है, तो हम मूर्खता से तत्वों को बाहर निकालते हैं। जैसे ही s2 फिर से खाली होता है, हम उसी ऑपरेशन को दोहराते हैं।

पायथन कोड:

 class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

काम का समय

पुश ऑपरेशन : हम एस 1 स्टैक पर एक आइटम को बेवकूफ बनाते हैं। ऑपरेटिंग समय O (1)।

पॉप ऑपरेशन : प्रत्येक तत्व के लिए, हम स्टैक से स्टैक तक एक से अधिक स्थानांतरण नहीं करते हैं, इसलिए, परिशोधित कार्य समय ओ (1) होगा।

ऑपरेशन get_min : मिनीमा s1 और s2 स्टैक के लिए जाना जाता है, इसलिए हम मिनिमा से न्यूनतम लेते हैं। ऑपरेटिंग समय O (1)।

बोनस चुनौती

एन संख्याओं के अनुक्रम को देखते हुए। M <N दिया गया है। लंबाई M के एक खंड को खोजने के लिए रैखिक समय की आवश्यकता होती है, जिस पर उत्पाद न्यूनतम * अधिकतम होता है।

निष्कर्ष

अंत तक पढ़ने के लिए धन्यवाद!

यदि आप विषय में रुचि रखते हैं, तो आप पढ़ सकते हैं कि यहां दो स्टैक पर लगातार कतार कैसे बनाई जाए, या मेरे अगले विषय के जारी होने की प्रतीक्षा करें।

टिप्पणियों में लिखें कि दो स्टैक पर आपको कौन से कार्य साक्षात्कार या प्रतियोगिता में हल करने थे।