মান লইয়া আমরা একটি ম্যাক্সিমাম স্ট্যাক বানাতে চাই, যেটি নিচের অপারেশনগুলো সাপোর্ট করে:
MaxStk()এটি ম্যাক্সিমাম স্ট্যাকের একটি নতুন ইনস্ট্যান্স কনস্ট্রাক্ট করবেpush(val)val স্টাকে ইনসার্ট করবেtop()স্ট্যাকের টপমোস্ট এলিমেন্ট পাবেmax()স্ট্যাক থেকে ম্যাক্সিমাম এলিমেন্ট পাবেpop()টপমোস্ট এলিমেন্ট রিমুভ করবে এবং রিটার্ন করবেpopmax()ম্যাক্সিমাম এলিমেন্ট রিমুভ করবে এবং রিটার্ন করবে
এখন MaxStk() কল করে ম্যাক্সিমাম স্ট্যাক কনস্ট্রাক্ট করুন, তারপর তিনটি ভ্যালু পুশ করুন 5, 15, 10, তারপর top(), max(), popmax(), max(), pop(), top() ফাংশনগুলো কল করুন। ইনিশিয়াল স্ট্যাক স্ট্যাটাস হবে [5, 15, 10], এবং ফাংশনগুলোর আউটপুট: 10, 15, 15, 10, 10, 5
এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:
- pos_index := 0
- একটি সেট stk এবং অন্যটি aux ডিফাইন করুন
- কনস্ট্রাক্টর ডিফাইন করুন, এটি কোনো স্পেশাল টাস্ক করে না
- push() ফাংশন ডিফাইন করুন, এটি val নেবে:
- (pos_index, val) stk-এ ইনসার্ট করুন
- (val, pos_index) aux-এ ইনসার্ট করুন
- pos_index++
- top() ফাংশন ডিফাইন করুন:
- যদি stk খালি থাকে, -1 রিটার্ন করুন
- stk-এর প্রথম আইটেমের সেকেন্ড ভ্যালু রিটার্ন করুন
- max() ফাংশন ডিফাইন করুন:
- যদি aux খালি থাকে, -1 রিটার্ন করুন
- aux-এর প্রথম আইটেমের ফার্স্ট ভ্যালু রিটার্ন করুন
- pop() ফাংশন ডিফাইন করুন:
- যদি stk খালি থাকে, -1 রিটার্ন করুন
- id := stk-এর প্রথম আইটেমের ফার্স্ট, ret := stk-এর প্রথম আইটেমের সেকেন্ড
- stk থেকে প্রথম এলিমেন্ট ডিলিট করুন
- aux থেকে (ret, id) ডিলিট করুন
- ret রিটার্ন করুন
- popmax() ফাংশন ডিফাইন করুন:
- যদি aux খালি থাকে, -1 রিটার্ন করুন
- ret := aux-এর প্রথম আইটেমের ফার্স্ট, id := aux-এর প্রথম আইটেমের সেকেন্ড
- aux থেকে প্রথম এলিমেন্ট ডিলিট করুন
- stk থেকে (id, ret) ডিলিট করুন
- ret রিটার্ন করুন
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class MaxStk {
int pos_index = 0;
set<pair<int, int>, greater<>> stk, aux;
public:
MaxStk() {}
void push(int val) {
stk.emplace(pos_index, val);
aux.emplace(val, pos_index);
pos_index++;
}
int top() {
if (stk.empty())
return -1;
return stk.begin()->second;
}
int max() {
if (aux.empty())
return -1;
return aux.begin()->first;
}
int pop() {
if (stk.empty())
return -1;
int id = stk.begin()->first, ret = stk.begin()->second;
stk.erase(stk.begin());
aux.erase({ret, id});
return ret;
}
int popmax() {
if (aux.empty())
return -1;
int ret = aux.begin()->first, id = aux.begin()->second;
aux.erase(aux.begin());
stk.erase({id, ret});
return ret;
}
};
int main(){
MaxStk max_stk;
max_stk.push(5);
max_stk.push(15);
max_stk.push(10);
cout << max_stk.top() << endl;
cout << max_stk.max() << endl;
cout << max_stk.popmax() << endl;
cout << max_stk.max() << endl;
cout << max_stk.pop() << endl;
cout << max_stk.top() << endl;
}
ইনপুট
max_stk.push(5) max_stk.push(15) max_stk.push(10) max_stk.top() max_stk.max() max_stk.popmax() max_stk.max() max_stk.pop() max_stk.top()
আউটপুট
10 15 15 10 10 5
