मान लीजिए हम एक ऐसा स्टैक डिजाइन करना चाहते हैं जो निम्न ऑपरेशन्स को सपोर्ट करता है:
CustomStack(int maxSize) यह ऑब्जेक्ट को maxSize से इनिशियलाइज़ करता है जो स्टैक में एलिमेंट्स की अधिकतम संख्या है या कुछ नहीं करता अगर स्टैक maxSize तक पहुंच गया है।
void push(int x) यह x को स्टैक के टॉप पर इंसर्ट करता है अगर स्टैक maxSize तक नहीं पहुंचा है।
int pop() यह स्टैक के टॉप को डिलीट और लौटाता है या -1 अगर स्टैक खाली है।
void inc(int k, int val) यह स्टैक के बॉटम k एलिमेंट्स को val से बढ़ाता है। अगर स्टैक में k से कम एलिमेंट्स हैं, तो स्टैक के सभी एलिमेंट्स को बढ़ाएं।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
दो ऐरे st और inc डिफाइन करें, और एक इंटीजर टाइप डेटा cap बनाएं
इनिशियलाइज़र में, cap := N सेट करें और inc := साइज N + 10 का नया ऐरे सेट करें
push(x) मेथड के लिए, अगर स्टैक का साइज cap नहीं है, तो x को st में इंसर्ट करें।
pop() ऑपरेशन इस तरह काम करेगा:
अगर st खाली है, तो -1 लौटाएं
अन्यथा:
स्टैक का टॉप := स्टैक का टॉप + inc[स्टैक का टॉप इंडेक्स]
अगर स्टैक में कुछ एलिमेंट है, तो inc[st का साइज - 2] को inc[st का साइज - 1] से बढ़ाएं
inc[st का साइज - 1] := 0
x := st का लास्ट एलिमेंट
x लौटाएं
inc() मेथड इस तरह काम करेगा:
k को 1 से घटाएं
k := k और st का साइज - 1 का मिनिमम
अगर k < 0, तो लौट जाएं
inc[k] को val से बढ़ाएं।
उदाहरण (C++)
बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:
#include <bits/stdc++.h>
using namespace std;
class CustomStack {
public:
vector <int> st;
vector <int> inc;
int cap;
CustomStack(int N) {
cap = N;
inc = vector <int>(N + 10);
}
void push(int x) {
if(st.size() == cap) return;
st.push_back(x);
}
int pop() {
if(st.empty()) return -1;
else{
st.back() += inc[st.size() - 1];
if(st.size() - 1 > 0 ){
inc[st.size() - 2] += inc[st.size() - 1];
}
inc[st.size() - 1] = 0;
int x = st.back();
st.pop_back();
return x;
}
}
void increment(int k, int val) {
k--;
k = min(k, (int)st.size() - 1);
if(k < 0) return;
inc[k] += val;
}
};
int main(){
CustomStack ob(3);
ob.push(1);
ob.push(2);
cout << ob.pop() << endl;
ob.push(2);
ob.push(3);
ob.push(4);
ob.increment(5, 100);
ob.increment(2, 100);
cout << ob.pop() << endl;
cout << ob.pop() << endl;
cout << ob.pop() << endl;
cout << ob.pop() << endl;
}
इनपुट
मुख्य() फंक्शन देखें
आउटपुट
2 103 202 201 -1
