परिचय
मान लीजिए हम एक मैक्सिमम स्टैक (Maximum Stack) बनाना चाहते हैं, जो निम्नलिखित ऑपरेशन्स का समर्थन करता है:
- MaxStk() - मैक्सिमम स्टैक का नया इंस्टेंस बनाता है
- push(val) - val को स्टैक में डालता है
- top() - स्टैक से शीर्ष तत्व प्राप्त करता है
- max() - स्टैक से अधिकतम तत्व प्राप्त करता है
- pop() - स्टैक से शीर्ष तत्व हटाता है और वापस करता है
- popmax() - स्टैक से अधिकतम तत्व हटाता है और वापस करता है
अब मैक्सिमम स्टैक को MasStk() कॉल करके बनाएं, फिर तीन मान जैसे 5, 15, 10 डालें, फिर top(), max(), popmax(), max(), pop(), top() फंक्शन्स को क्रमशः कॉल करें। प्रारंभिक स्टैक स्थिति [5, 15, 10] होगी, और फंक्शन्स के लिए संबंधित आउटपुट: 10, 15, 15, 10, 10, 5
समाधान दृष्टिकोण
हम दो सेट (ऑर्डर्ड कंटेनर्स) का उपयोग करते हैं: एक इंसर्शन ऑर्डर के लिए (stk), एक वैल्यू ऑर्डर के लिए (aux)। प्रत्येक एलिमेंट का एक यूनिक पोजीशन इंडेक्स होता है।
उदाहरण कोड
#include <bits/stdc++.h>
using namespace std;
class MaxStk {
int pos_index = 0;
set<pair<int, int>, greater<>> stk, aux; // stk: (pos, val), aux: (val, pos)
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;
return 0;
}
इनपुट
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
निष्कर्ष
दो सेट्स का उपयोग करके सभी ऑपरेशन्स O(log n) समय में काम करते हैं। यह डिजाइन पैटर्न तब उपयोगी है जब आपको स्टैक ऑपरेशन्स के साथ-साथ मैक्सिमम क्वेरी की भी आवश्यकता हो। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
