मैं यह कैसे पूरा करने के लिए सोच रहा हूँ:जावा ढेर तुलना
केवल Stack के लिए push, pop और isEmpty तरीकों उपलब्ध है।
मैं कोडिंग सहायता की तुलना में सैद्धांतिक सहायता के लिए और अधिक देख रहा हूं, लेकिन किसी भी अंतर्दृष्टि की सराहना की जाएगी।
प्रत्यावर्तन यह हमेशा 2 भागों, एक "सेटअप" और एक पुनरावर्ती मज़ा के रूप में यह सोचने के लिए मदद करता है के साथ
boolean compareStacks(a, b) {
if (a.isEmpty() != b.isEmpty()) return false; // check if one is empty
if (a.isEmpty() && b.isEmpty()) return true; // check if both are empty
element_a = a.pop(); // grab elements and compare them
element_b = b.pop();
if (((element_a==null) && (element_b!=null)) || !element_a.equals(element_b)) {
a.push(element_a); // if they are not equal, restore them and return false
b.push(element_b);
return false;
}
result = compareStacks(a, b); // compare shortened stacks recursively
a.push(element_a); // restore elements
b.push(element_b);
return result; // return result from recursive call
}
दो शीर्ष ढेर समान हैं यदि उनके शीर्ष स्तर के तत्व समान हैं, और शेष ढेर समान हैं (अर्थात्, पुनरावर्ती स्थिति)।
अब, सोचें कि विधि कॉल से लौटने से पहले क्या करना है, ताकि स्टैक को उसी तरह से छोड़ दिया जा सके जहां वे आमंत्रण समय पर दिए गए थे।
--- संपादित करें ---
काम कर जावा कोड (मार्कस ए समाधान से ली गई है, लेकिन "अंततः" का एक दिलचस्प उपयोग के साथ और जेनरिक के साथ):
static <T> boolean compareStacks(Stack<T> a, Stack<T> b) {
if (a.isEmpty() != b.isEmpty()) return false;
if (a.isEmpty() && b.isEmpty()) return true;
T element_a = a.pop();
T element_b = b.pop();
try {
if (((element_a==null) && (element_b!=null)) || (!element_a.equals(element_b)))
return false;
return compareStacks(a, b);
} finally { // restore elements
a.push(element_a);
b.push(element_b);
}
}
मुझे पता है कि विधि में प्रवेश करने के लिए, आपको तुलना करने के लिए प्रत्येक स्टैक के शीर्ष तत्व को पॉप करना होगा ... तो कहें कि वे बराबर हैं ...तो आपको विधि को दोबारा कॉल करना होगा ... और अगले दो ... आदि को पॉप करें ... लेकिन फिर आप सभी तत्वों से गुजरने के बाद दो रिक्त स्टैक के साथ छोड़े गए हैं ... – user
आप तत्वों को कैसे दबाएंगे ताकि वे उसी क्रम में वापस जाएं ??? – user
उन्हें एक और ढेर पर पुश करें। – Oswald
: छद्म कोड में, आप कुछ इस तरह कर सकता है ction। आपका सेटअप उचित स्थिति बनाएगा (दो ढेर बनाएं, उन्हें पास करें, आदि) और फिर रिकर्सिव विधि को कॉल करें और जब रिकर्सिव विधि पूरी की जाती है, तो परिणामों की रिपोर्ट करें।
आपके मामले में आप शायद "पुनरावर्ती" विधि के लिए इस हस्ताक्षर हैं:
public boolean compareStacks(Stack one, Stack two)
कि विधि पॉप & तुलना ढेर के शीर्ष टो तत्वों, यह सही तो झूठे लौट सकते हैं (वे कह डॉन तुलना नहीं करते हैं)। यदि वे करते हैं, तो अब आपके पास दो ढेर हैं, प्रत्येक एक से पहले छोटा है। आप पहले से ही जानते हैं कि उन दो ढेरों की तुलना कैसे करें, ठीक है (आपने बस ऐसा करने के लिए विधि लिखी है!)।
अंत में आप लौटने से पहले अपने पिछले तत्व को पुनर्स्थापित करने के लिए प्रत्येक स्टैक पर अपने तत्व को "पुश" कर सकते हैं।
उस मामले में स्टैक को बहाल करने में थोड़ी सी चाल होगी जहां उनकी तुलना नहीं की जा रही है, और यह सुनिश्चित करना कि यदि तुलना स्टैक आप कॉल करते हैं तो यह ठीक हो जाता है कि यह पिछले राज्य तक ठीक से गुजरता है, भले ही "वर्तमान" तुलनास्टैक सफल होता है, लेकिन वे कार्यान्वयन के विवरण हैं - बस सोचा कि मैं उनको जिक्र करूँगा ताकि आप उन्हें नजरअंदाज न करें।
कोशिश/आखिरकार (कोई पकड़ नहीं है, अंत में स्टैक पर वापस धक्का दें) के साथ एक प्यारा समाधान है जो कोड को बहुत चिकना कर देगा, लेकिन इसके बिना यह काफी आसान है।
मुझे विश्वास है कि यह काम करता है। – user
सुंदर ... कमाल ... आप गंभीर रूप से आदमी हैं। – user
@user: मेरा सुधार देखें - कोशिश करें/अंत में आप डुप्लिकेट कोड से बचें जो स्टैक राज्यों को पुनर्स्थापित करता है। –