मान लीजिए कि हम फ़्रीक्वेंसीस्टैक नामक एक स्टैक का निर्माण करना चाहते हैं, हमारे फ़्रिक्वेंसीस्टैक के दो कार्य हैं -
-
एपेंड (x), यह एक मान x को स्टैक पर जोड़ देगा या धकेल देगा।
-
पॉप (), यह स्टैक में सबसे अधिक बार आने वाले तत्व को हटा देगा और वापस कर देगा। यदि समान आवृत्ति वाले एक से अधिक तत्व हैं, तो स्टैक के शीर्ष के निकटतम तत्व को हटा दिया जाता है और वापस कर दिया जाता है।
इसलिए, यदि इनपुट 7, 9, 7, 9, 6, 7 जैसे कुछ तत्वों को जोड़ने जैसा है, तो पॉप ऑपरेशन चार बार करें, फिर आउटपुट क्रमशः 7,9,7,6 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक मानचित्र को परिभाषित करें
-
एक नक्शा एसटीएस परिभाषित करें
-
मैक्सफ्रीक:=0
-
फंक्शन एपेंड () को परिभाषित करें, इसमें x लगेगा,
-
(cnt[x] 1 से बढ़ाएं)
-
maxFreq :=अधिकतम अधिकतम फ़्रीक और cnt[x]
-
एसटीएस में एक्स डालें [सीएनटी [एक्स]]
-
फ़ंक्शन पॉप को परिभाषित करें ()
-
maxKey :=maxFreq
-
x :=sts का शीर्ष तत्व [maxKey]
-
एसटीएस से तत्व हटाएं [मैक्सकी]
-
यदि sts[maxKey] का आकार 0 के समान है, तो -
-
मैक्सकी को एसटीएस से हटाएं
-
(maxFreq को 1 से घटाएं)
-
-
(cnt[x] 1 से घटाएं)
-
वापसी 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
