यदि आपके पास CS (कंप्यूटर साइंस) डिग्री नहीं है तो आपको ऐसा लग सकता है कि आप कुछ चूक रहे हैं...
या आप महसूस कर सकते हैं कि CS बहुत अमूर्त है उपयोगी होने के लिए...
या रूबी पहले से ही आपके लिए सारा कठिन काम करता है...
किसी भी तरह...
हैश, स्टैक्स और क्यू जैसी डेटा संरचनाओं की बुनियादी बातों को समझना उपयोगी है।
इस पोस्ट में:
आप रूबी में स्टैक्स का उपयोग करना खोजेंगे।
एक व्यावहारिक कंप्यूटर विज्ञान अवधारणा जिसे आप अभी अभ्यास में लाना शुरू कर सकते हैं!
रूबी में स्टैक्स को समझना
रूबी में स्टैक क्या है?
एक स्टैक एक डेटा संरचना है जिसका उपयोग आप "टू-डू" सूची के रूप में कर सकते हैं। आप स्टैक से तत्व लेते रहते हैं और उन्हें प्रोसेस करते हैं जब तक स्टैक खाली न हो जाए।
यहां एक दृश्य प्रतिनिधित्व है।
खाली स्टैक में 5 पुश करें:
5
स्टैक में 3 पुश करें:
3
5
स्टैक में 9 पुश करें:
9
3
5
स्टैक से एक आइटम लें:
3
5
यहां ध्यान देने वाली बड़ी बात यह है कि नए आइटम्स को स्टैक के शीर्ष पर जोड़ा जाता है। "लास्ट-इन फर्स्ट-आउट" (LIFO) फैशन में। इसका अर्थ है कि जब आप स्टैक से कोई आइटम लेते हैं (पॉप), तो यह वह अंतिम आइटम होगा जिसे इसमें पुश किया गया था।
इसके काम करने का एक और तरीका प्लेट्स के स्टैक के बारे में सोचना है। यदि आप एक प्लेट को दूसरी के ऊपर रखते हैं तो आप शीर्ष प्लेट को पहले निकाले बिना नीचे की प्लेट को नहीं निकाल सकते।
यही सब आप स्टैक के साथ कर रहे हैं, चीजों को शीर्ष पर पुश करना या पॉप करना। वहां कोई इंडेक्सिंग नहीं है।
आइए देखें कि इसका उपयोग कैसे किया जा सकता है इसके कुछ कोड उदाहरण।
स्टैक का उपयोग करके सरणी को फ्लैट कैसे करें
स्टैक्स का एक क्लासिक उदाहरण सरणी को फ्लैट करने के लिए उनका उपयोग करना है। दूसरे शब्दों में, एक बहुआयामी सरणी को एक आयामी सरणी में परिवर्तित करना।
यहां एक उदाहरण है:
arr = [1,2,3,[4,5],6] arr.flatten
रूबी में हमारे पास flatten मेथड है जो आपके लिए यह करता है। लेकिन क्या होगा अगर आपके पास यह मेथड नहीं था? और यह मेथड कैसे काम करता है?
यहीं स्टैक काम आता है!
रूबी पुश और पॉप मेथड्स लागू करता है, इसलिए हम एक सरणी को स्टैक की तरह मान सकते हैं।
नोट: दोनों
pushऔर<<एक ही मेथड हैं। मैं अपने कोड उदाहरणों में<<का उपयोग करूंगा।
विचार हर तत्व पर जाने और जांचने का है कि क्या यह एक सरणी है या कुछ और। अगर यह एक सरणी है तो हम इस सरणी के अंदर के तत्वों को वापस स्टैक में push करेंगे।
क्या होता है कि हम सरणी की परतों को हटाते रहते हैं (प्याज की तरह) जब तक कोई नहीं बचती। यह हमें एक फ्लैट सरणी के साथ छोड़ देगा।
यहां कोड है:
arr = [1,2,3,[4,5],6] flat = [] arr.each do |thing| if thing.is_a? Array thing.each { |i| arr << i } else flat << thing end end p flat # [1, 2, 3, 6, 4, 5] आप देखेंगे कि इस कोड में कोई pop मेथड कॉल नहीं है।
ऐसा इसलिए है क्योंकि मैं each को स्टैक से आइटम लेने और उन्हें मेरे एल्गोरिदम को खिलाने का कठिन काम करने दे रहा हूं। यह भी ध्यान दें कि इस तरह से करने पर तत्वों का क्रम बनाए नहीं रखा जाता है।
until और empty? का उपयोग करने वाला एक अन्य संस्करण:
until arr.empty? thing = arr.pop if thing.is_a? Array thing.each { |i| arr << i } else flat << thing end end p flat # [6, 5, 4, 3, 2, 1] चूंकि हम अब pop का उपयोग कर रहे हैं, each को अपना काम करने देने के बजाय, हमें सही क्रम में फ्लैट सरणी मिल रही है... लेकिन रिवर्स में।
यह स्टैक्स का एक दिलचस्प गुण प्रकट करता है:
आप चीजों की जो भी सूची डालते हैं, वह उसी क्रम में वापस आएगी लेकिन रिवर्स में।
टिप:
Array#flattenमेथड एक आर्गुमेंट लेता है, जो आपको यह परिभाषित करने देता है कि आप नेस्टिंग की कितनी परतों को हटाना चाहते हैं (डिफ़ॉल्ट रूप से उन सभी को)।
संतुलित पैरेंथेसिस समस्या को हल करना
यहां एक और उदाहरण है और इसके लिए कोई समकक्ष रूबी मेथड नहीं है!
यह कंप्यूटर विज्ञान में एक और क्लासिक समस्या है...
नाम है:
संतुलित पैरेंथेसिस का मिलान।
विचार यह है कि आपको एक स्ट्रिंग दी जाती है और आपको यह मान्य करने की आवश्यकता है कि पैरेंथेसिस वैध हैं या नहीं।
उदाहरण के लिए, मान लें कि आप एक मैथ इवैल्यूएशन प्रोग्राम लिख रहे हैं। आप इसे प्रोसेस करने से पहले सुनिश्चित करना चाहते हैं कि इनपुट वैध है।
उदाहरण (वैध इनपुट):
input = "1 + (4 + 6) * 2"
उदाहरण (अवैध इनपुट):
input = "1 + (4 + 6 * 2"
आप स्टैक का उपयोग करके किसी भी पैरेंथेसिस को ट्रैक कर सकते हैं जो आपने इनपुट में पाया है और फिर जब आपको एक नया पैरेंथेसिस मिलता है तो आप स्टैक के शीर्ष की जांच करते हैं ताकि यह सुनिश्चित हो सके कि यह क्लोजिंग पैरेंथेसिस से मेल खाता है।
अगर कोई मेल नहीं है तो इसका मतलब है कि आपके पास अवैध इनपुट है।
उदाहरण:
PARENS = { "(" => ")", "{" => "}", "[" => "]" } OPENING_PARENS = PARENS.keys CLOSING_PARENS = PARENS.values def valid_parentheses(string) stack = [] string.each_char do |ch| if OPENING_PARENS.include?(ch) stack << ch elsif CLOSING_PARENS.include?(ch) ch == PARENS[stack.last] ? stack.pop : (return false) end end stack.empty? end p valid_parentheses("(){}[]") # true p valid_parentheses("[(])") # false एक और चीज़ जो आप देखेंगे वह यह है कि मैंने इस valid_parentheses मेथड को stack.empty? के साथ समाप्त किया। यह सुनिश्चित करने के लिए कि हम अनक्लोज्ड पैरेंथेसिस के साथ समाप्त नहीं होते।
यदि सभी पैरेंथेसिस सही ढंग से बंद हैं तो स्टैक खाली होना चाहिए 🙂
उदाहरण 3 (दिशाएं)
यह सुनिश्चित करने के लिए एक और उदाहरण कि आप समझते हैं कि इसे कैसे लागू किया जाए।
इस मामले में हमें दिशाओं का एक सेट दिया गया है और हमें बताया गया है कि हमें अपने यात्री का कुछ समय बचाने के लिए इसे अनुकूलित करने की आवश्यकता है।
यहां एक उदाहरण सेट है:
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
आप देखेंगे कि यदि आप उत्तर जाते हैं फिर दक्षिण तो आप उसी स्थान पर पहुंच जाएंगे (यह मानते हुए कि दोनों दिशाओं में दूरी समान है)। यही वह है जिसे हमें अनुकूलित करने की आवश्यकता है और हम स्टैक का उपयोग करके ऐसा कर सकते हैं।
उदाहरण:
input = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"] directions = [] opposites = { "NORTH" => "SOUTH", "SOUTH" => "NORTH", "EAST" => "WEST", "WEST" => "EAST" } input.each do |dir| opposites[dir] == directions.last ? directions.pop : directions << dir end p directions निष्कर्ष
मुझे आशा है कि आपने कुछ नया सीखा और आप प्रोग्रामिंग चुनौतियों को हल करने के लिए स्टैक्स का उपयोग करने के तरीकों की तलाश शुरू कर देंगे।
इस पोस्ट को शेयर करना न भूलें ताकि अधिक लोग इसे पढ़ सकें!
