রুবি স্ট্যাকসে দক্ষতা: নতুনদের জন্য ব্যাবহারিক ডেটা স্ট্রাকচার টেকনিকস

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

অথবা আপনি মনে করতে পারেন CS খুব অ্যাবস্ট্রাক্ট যাতে উপযোগী হয়…

অথবা রুবি ইতিমধ্যে সব কঠিন কাজ করে দিচ্ছে…

যে যাবে হোক…

হ্যাশ, স্ট্যাক এবং কিউ এর মতো ডেটা স্ট্রাকচারোর বেসিক বোঝা সহায়ক।

এই পোস্টে:

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

একটি ব্যাবহারিক কম্পিউটার সায়েন্স কনসেপ্ট যা আপনি এখনই প্র্যাকটিস করা শুরু করতে পারেন!

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

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

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

এখানে একটি ভিজুয়াল রিপ্রেজেন্টেশন।

খালি স্টাকে ৫ পুশ করুন:

৫

স্টাকে ৩ পুশ করুন:

৩
৫

স্টাকে ৯ পুশ করুন:

৯
৩
৫

স্ট্যাক থেকে একটি আইটেম নিন:

৩
৫

এখানে বড় জিনিসটি লক্ষ্য করুন যে নতুন আইটেমগুলো স্ট্যাকের টপে যোগ হয়। "লাস্ট-ইন ফার্স্ট-আউট" (LIFO) ফ্যাশনে। অর্থাৎ যখন আপনি স্ট্যাক থেকে একটি আইটেম নেন (পপ), সেটি হবে সবচেয়ে শেষে পুশ করা আইটেম।

এটিকে ভিজুয়ালাইজ করার আরেকটি উপায় হলো একের ওপর এক প্লেট রাখা ভাবা। আপনি নিচের প্লেটটি বের করতে পারবেন না উপরের প্লেটটি প্রথমে বের না করলে।

স্ট্যাকের সাথে আপনি শুধু এই করছেন, জিনিসগুলো টপে পুশ করছেন বা পপ করে বের করছেন। কোনো ইন্ডেক্সিং নেই।

চলুন কিছু কোড উদাহরণ দেখি কীভাবে এটি ব্যবহার করা যায়।

স্ট্যাক ব্যবহার করে অ্যারে ফ্ল্যাটেন করা

স্ট্যাকের একটি ক্লাসিক উদাহরণ হলো অ্যারে ফ্ল্যাটেন করতে ব্যবহার করা। অন্য কথায়, একটি মাল্টি-ডাইমেনশনাল অ্যারে কে এক-ডাইমেনশনাল অ্যারেতে রূপান্তর করা।

এখানে একটি উদাহরণ:

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

রুবিতে আমাদের flatten মেথড আছে যা এটি আপনার জন্য করে। কিন্তু যদি আপনার এই মেথডটি না থাকে? এবং এই মেথডটি কীভাবে কাজ করে?

এখানেই স্ট্যাক কাজে আসে!

রুবি push ও pop মেথড ইমপ্লিমেন্ট করে, তাই আমরা একটি অ্যারেকে একটি স্ট্যাকের মতো চেফতে পারি।

নোট: 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? দিয়ে শেষ করেছি। সেটি নিশ্চিত করার জন্য যে আমরা আনক্লোজড প্যারেনথেসিসের সাথে শেষ করছি না।

যদি সব প্যারেনথেসিস সঠিকভাবে ক্লোজড থাকে তবে স্ট্যাক খালি হওয়া উচিত 🙂

উদাহরণ ৩ (দিকনির্দেশনা)

আপনাকে বুঝতে পারার জন্য আরেকটি উদাহরণ।

এই কেসে আমাদের একটি ডিরেকশন সেট দেওয়া আছে এবং আমাদের বলা হয়েছে আমাদের এটি অপ্টিমাইজ করতে হবে আমাদের ট্রাভেলারের সময় বাঁচাতে।

এখানে একটি উদাহরণ সেট:

 ["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 

উপসংহার

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

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