ধরুন আমরা ফ্রিকোয়েন্সিস্ট্যাক নামে একটি স্ট্যাক তৈরি করতে চাই, আমাদের ফ্রিকোয়েন্সিস্ট্যাকের দুটি ফাংশন রয়েছে -
-
append(x), এটি স্ট্যাকের উপরে একটি মান x যুক্ত করবে বা পুশ করবে।
-
pop(), এটি স্ট্যাকের সবচেয়ে ঘন ঘন উপাদানটিকে সরিয়ে দেবে এবং ফেরত দেবে। যদি একই ফ্রিকোয়েন্সি সহ একাধিক উপাদান থাকে, তাহলে স্ট্যাকের শীর্ষের নিকটতম উপাদানটি সরানো হয় এবং ফেরত দেওয়া হয়৷
সুতরাং, যদি ইনপুটটি 7, 9, 7, 9, 6, 7 এর মতো কিছু উপাদান যুক্ত করার মতো হয়, তারপরে চারবার পপ অপারেশন করুন, তাহলে আউটপুট হবে যথাক্রমে 7,9,7,6।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র সংজ্ঞায়িত করুন cnt
-
একটি মানচিত্র sts সংজ্ঞায়িত করুন
-
maxFreq :=0
-
একটি ফাংশন সংজ্ঞায়িত করুন (), এটি x,
লাগবে -
(cnt[x] 1 দ্বারা বৃদ্ধি করুন)
-
maxFreq :=সর্বাধিক maxFreq এবং cnt[x]
-
sts[cnt[x]]
-এ x ঢোকান -
একটি ফাংশন pop()
সংজ্ঞায়িত করুন -
maxKey :=maxFreq
-
x :=sts[maxKey]
এর শীর্ষ উপাদান -
sts[maxKey]
থেকে উপাদান মুছুন -
যদি sts[maxKey] এর আকার 0 এর মতো হয়, তাহলে −
-
sts থেকে maxKey মুছুন
-
(maxFreq 1 দ্বারা কমিয়ে দিন)
-
-
(1 দ্বারা cnt[x] হ্রাস করুন)
-
রিটার্ন x
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class FreqStack {
public:
unordered_map <int ,int > cnt;
unordered_map <int, stack <int> >sts;
int maxFreq = 0;
FreqStack() {
maxFreq = 0;
cnt.clear();
sts.clear();
}
void append(int x) {
cnt[x]++;
maxFreq = max(maxFreq, cnt[x]);
sts[cnt[x]].push(x);
}
int pop() {
int maxKey = maxFreq;
int x = sts[maxKey].top();
sts[maxKey].pop();
if(sts[maxKey].size() == 0){
sts.erase(maxKey);
maxFreq−−;
}
cnt[x]−−;
return x;
}
};
main(){
FreqStack ob;
ob.append(7);
ob.append(9);
ob.append(7);
ob.append(9);
ob.append(6);
ob.append(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
} ইনপুট
ob.append(7); ob.append(9); ob.append(7); ob.append(9); ob.append(6); ob.append(7); cout << (ob.pop()) << endl; cout << (ob.pop()) << endl; cout << (ob.pop()) << endl; cout << (ob.pop()) << endl;
আউটপুট
7 9 7 6
