मान लीजिए कि हम फ्रीकस्टैक नामक एक स्टैक को लागू करना चाहते हैं, हमारे फ्रीकस्टैक के दो कार्य हैं -
-
push(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 push(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.push(7);
ob.push(9);
ob.push(7);
ob.push(9);
ob.push(6);
ob.push(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
} इनपुट
push elements 7, 9, 7, 9, 6, 7, then call pop() four times.
आउटपुट
7 9 7 6