समस्याओं को हल करने के लिए रूबी में ढेर का उपयोग कैसे करें

यदि आपके पास सीएस (कंप्यूटर साइंस) की डिग्री नहीं है तो आपको ऐसा लग सकता है कि आप कुछ खो रहे हैं…

या आप ऐसा महसूस कर सकते हैं कि सीएस उपयोगी होने के लिए बहुत सारगर्भित है…

या कि रूबी पहले से ही आपके लिए पूरी मेहनत कर रही है…

किसी भी तरह से…

हैश, स्टैक और क्यू जैसी डेटा संरचनाओं की बुनियादी बातों को समझना उपयोगी है।

इस पोस्ट में :

आप रूबी में स्टैक का उपयोग करने का तरीका जानेंगे।

एक व्यावहारिक कंप्यूटर विज्ञान अवधारणा जिसे आप अभी से अमल में लाना शुरू कर सकते हैं!

रूबी में स्टैक को समझना

रूबी में स्टैक क्या है?

स्टैक एक डेटा संरचना है जिसे आप "टू-डू" सूची के रूप में उपयोग कर सकते हैं। आप स्टैक से तत्वों को लेते रहते हैं और स्टैक के खाली होने तक उन्हें संसाधित करते रहते हैं।

यहाँ एक दृश्य प्रतिनिधित्व है।

5 को एक खाली स्टैक में धकेलें :

5

स्टैक में 3 पुश करें :

3
5

9 को स्टैक में धकेलें :

9
3
5

स्टैक से एक आइटम लें :

3
5

यहां ध्यान देने वाली बड़ी बात यह है कि नए आइटम स्टैक के शीर्ष में जोड़े जाते हैं . "लास्ट-इन फर्स्ट-आउट" (LIFO) फैशन में। इसका मतलब है कि जब आप स्टैक से कोई आइटम (पॉप) लेते हैं, तो वह आखिरी आइटम होगा जिसे उसमें धकेला गया था।

यह कैसे काम करता है, इसकी कल्पना करने का एक और तरीका प्लेटों के ढेर के बारे में सोचकर है। यदि आप एक प्लेट को दूसरे के ऊपर रखते हैं तो आप नीचे की प्लेट को पहले ऊपर की प्लेट को निकाले बिना नहीं निकाल सकते।

स्टैक के साथ आप बस इतना ही कर रहे हैं, चीजों को ऊपर की ओर धकेल रहे हैं या चीजों को बाहर निकाल रहे हैं। कोई अनुक्रमण नहीं है ।

आइए कुछ कोड उदाहरण देखें कि इसका उपयोग कैसे किया जा सकता है।

स्टैक का उपयोग करके किसी सरणी को कैसे समतल करें

ढेर का एक उत्कृष्ट उदाहरण एक सरणी को समतल करने के लिए उनका उपयोग करना है। दूसरे शब्दों में, एक बहु-आयामी सरणी को एक-आयामी सरणी में परिवर्तित करें।

यहां एक उदाहरण दिया गया है :

arr = [1,2,3,[4,5],6]

arr.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

निष्कर्ष

मुझे आशा है कि आपने कुछ नया सीखा है और आप प्रोग्रामिंग चुनौतियों को हल करने के लिए स्टैक का उपयोग करने के तरीकों की तलाश शुरू कर रहे हैं।

इस पोस्ट को शेयर करना न भूलें ताकि और लोग इसे पढ़ सकें!