मान लीजिए हम एक अधिकतम स्टैक बनाना चाहते हैं, जो निम्नलिखित कार्यों का समर्थन करता है -
-
MaxStk() यह अधिकतम स्टैक का एक नया उदाहरण बनाएगा
-
पुश (वैल) स्टैक में वैल सम्मिलित करता है
-
शीर्ष () स्टैक से शीर्षतम तत्व प्राप्त करें
-
अधिकतम () स्टैक से अधिकतम तत्व प्राप्त करें
-
पॉप () स्टैक से सबसे ऊपरी तत्व को हटाता है और लौटाता है
-
पॉपमैक्स () स्टैक से अधिकतम तत्व को हटाता है और लौटाता है
अब MasStk () को कॉल करके अधिकतम स्टैक का निर्माण करें, फिर तीन मानों जैसे 5, 15, 10 को पुश करें, फिर क्रमशः टॉप (), मैक्स (), पॉपमैक्स (), मैक्स () पॉप (), टॉप () फ़ंक्शन को कॉल करें। तो प्रारंभिक स्टैक स्थिति [5, 15, 10] होगी, और कार्यों के लिए संबंधित आउटपुट:10, 15, 15, 10, 10, 5
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
pos_index :=0
-
एक सेट को दूसरे सेट ऑक्स को परिभाषित करें
-
कंस्ट्रक्टर को परिभाषित करें, यह कोई विशेष कार्य नहीं कर रहा है
-
फ़ंक्शन पुश () को परिभाषित करें, यह वैल लेगा,
-
pos_index , val को stk में डालें
-
ऑक्स में वैल, pos_index डालें
-
(pos_index को 1 से बढ़ाएं)
-
फ़ंक्शन को परिभाषित करें top()
-
अगर stk खाली है, तो -
-
वापसी -1
-
-
stk के पहले आइटम का दूसरा मान लौटाएं
-
एक फ़ंक्शन को परिभाषित करें अधिकतम ()
-
अगर ऑक्स खाली है, तो -
-
वापसी -1
-
-
ऑक्स के पहले आइटम का पहला मान लौटाएं
-
फ़ंक्शन पॉप को परिभाषित करें ()
-
अगर stk खाली है, तो -
-
वापसी -1
-
-
आईडी:=stk के पहले आइटम का पहला मान, ret =stk के पहले आइटम का दूसरा मान
-
stk से stk का पहला तत्व हटाएं
-
ऑक्स से जोड़ी (रिट, आईडी) हटाएं
-
वापसी रिट
-
फ़ंक्शन को परिभाषित करें पॉपमैक्स ()
-
अगर ऑक्स खाली है, तो -
-
वापसी -1
-
-
ret :=aux के पहले आइटम का पहला मान, id =aux के पहले आइटम का दूसरा मान
-
aux से aux का पहला तत्व हटाएं
-
stk से जोड़ी(id, 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