ধরুন আমরা একটি স্ট্যাক ডিজাইন করতে চাই যা নিচের অপারেশনগুলো সাপোর্ট করে।
CustomStack(int maxSize) এটি maxSize দিয়ে অবজেক্ট ইনিশিয়ালাইজ করে যা স্ট্যাকের সর্বোচ্চ এলিমেন্ট সংখ্যা, বা কিছুই না করবে যদি স্ট্যাক maxSize-এ পৌঁছায়।
void push(int x) এটি x কে স্ট্যাকের টপে ইনসার্ট করবে যদি স্ট্যাক maxSize-এ না পৌঁছায়।
int pop() এটি স্ট্যাকের টপ ডিলিট করে রিটার্ন করবে অথবা -1 যদি স্ট্যাক খালি থাকে।
void inc(int k, int val) এটি স্ট্যাকের নিচের k টি এলিমেন্টকে val দিয়ে ইনক্রিমেন্ট করবে। যদি স্ট্যাকে k-র চেয়ে কম এলিমেন্ট থাকে, তবে সকল এলিমেন্ট ইনক্রিমেন্ট করুন।
সমাধানের ধাপগুলো:
দুটি অ্যারে st এবং inc ডিফাইন করুন, এবং একটি ইন্টিজার cap তৈরি করুন
ইনিশিয়ালাইজারে cap := N এবং inc := সাইজ N + 10-এর নতুন অ্যারে সেট করুন
push(x) মেথডে, যদি স্ট্যাকের সাইজ cap না হয়, তবে x st-এ ইনসার্ট করুন
pop() অপারেশন নিচের মতো হবে −
যদি st খালি হয়, তবে -1 রিটার্ন করুন
অন্যথায়
স্ট্যাকের টপ := স্ট্যাকের টপ + inc[স্ট্যাকের টপ ইন্ডেক্স]
যদি স্ট্যাকে কিছু এলিমেন্ট থাকে, তবে inc[st.size() - 2]-কে inc[st.size() – 1]-দিয়ে বাড়ান
inc[st.size() - 1] := 0
x := st-এর লাস্ট এলিমেন্ট
x রিটার্ন করুন
inc() মেথড নিচের মতো কাজ করবে −
k ১ কমান
k := min(k, st.size() - 1)
যদি k < 0 হয়, তবে রিটার্ন করুন
inc[k]-কে val দিয়ে বাড়ান।
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class CustomStack { public: vector <int> st; vector <int> inc; int cap; CustomStack(int N) { cap = N; inc = vector <int>(N + 10); } void push(int x) { if(st.size() == cap) return; st.push_back(x); } int pop() { if(st.empty()) return -1; else{ st.back() += inc[st.size() - 1]; if(st.size() - 1 > 0 ){ inc[st.size() - 2] += inc[st.size() - 1]; } inc[st.size() - 1] = 0; int x = st.back(); st.pop_back(); return x; } } void increment(int k, int val) { k--; k = min(k, (int)st.size() - 1); if(k < 0) return; inc[k] += val; } }; main(){ CustomStack ob(3); ob.push(1); ob.push(2); cout << ob.pop() << endl; ob.push(2); ob.push(3); ob.push(4); ob.increment(5, 100); ob.increment(2, 100); cout << ob.pop() << endl; cout << ob.pop() << endl; cout << ob.pop() << endl; cout << ob.pop() << endl; }
ইনপুট
main() ফাংশনে দেখুন
আউটপুট
2 103 202 201 -1
