সমস্যা সমাধানের জন্য রুবিতে স্ট্যাকগুলি কীভাবে ব্যবহার করবেন

আপনার যদি CS (কম্পিউটার সায়েন্স) ডিগ্রি না থাকে তাহলে আপনার মনে হতে পারে আপনি কিছু মিস করছেন...

অথবা আপনার মনে হতে পারে যে CS ব্যবহার করার জন্য খুবই বিমূর্ত…

অথবা রুবি ইতিমধ্যে আপনার জন্য সমস্ত কঠোর পরিশ্রম করে ফেলেছে...

যেভাবেই হোক...

হ্যাশ, স্ট্যাক এবং সারিগুলির মতো ডেটা স্ট্রাকচারের মৌলিক বিষয়গুলি বোঝার জন্য এটি সহায়ক৷

এই পোস্টে :

আপনি রুবিতে স্ট্যাকগুলি কীভাবে ব্যবহার করবেন তা আবিষ্কার করবেন।

একটি ব্যবহারিক কম্পিউটার বিজ্ঞান ধারণা যা আপনি এখনই অনুশীলন শুরু করতে পারেন!

রুবিতে স্ট্যাক বোঝা

রুবিতে স্ট্যাক কি?

স্ট্যাক হল একটি ডেটা স্ট্রাকচার যা আপনি "টু-ডু" তালিকা হিসাবে ব্যবহার করতে পারেন। আপনি স্ট্যাক থেকে উপাদানগুলি গ্রহণ করতে থাকুন এবং স্ট্যাকটি খালি না হওয়া পর্যন্ত সেগুলি প্রক্রিয়াকরণ করতে থাকুন৷

এখানে একটি ভিজ্যুয়াল উপস্থাপনা।

একটি খালি স্ট্যাকের মধ্যে 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

উপসংহার

আমি আশা করি আপনি নতুন কিছু শিখেছেন এবং আপনি প্রোগ্রামিং চ্যালেঞ্জগুলি সমাধান করার জন্য স্ট্যাকগুলি ব্যবহার করার উপায় খুঁজতে শুরু করেছেন৷

এই পোস্টটি শেয়ার করতে ভুলবেন না৷ যাতে আরো মানুষ এটি পড়তে পারে!