C++ में इंक्रीमेंट ऑपरेशन के साथ एक स्टैक डिज़ाइन करें

मान लीजिए कि हम एक स्टैक डिजाइन करना चाहते हैं जो निम्नलिखित कार्यों का समर्थन करता है।

CustomStack(int maxSize) यह ऑब्जेक्ट को maxSize के साथ इनिशियलाइज़ करता है जो स्टैक में तत्वों की अधिकतम संख्या है या यदि स्टैक maxSize तक पहुँच गया है तो कुछ भी नहीं करें।
शून्य पुश (int x) यदि स्टैक अधिकतम आकार तक नहीं पहुंचा है तो यह स्टैक के शीर्ष पर x सम्मिलित करता है।
इंट पॉप () यह स्टैक के शीर्ष को हटाता है और लौटाता है या यदि स्टैक खाली है तो -1 देता है।
शून्य इंक (इंट के, इंट वैल) यह स्टैक के निचले के तत्वों को वैल द्वारा बढ़ाता है। यदि स्टैक में k से कम तत्व हैं, तो स्टैक के सभी तत्वों को बढ़ाएँ।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

दो सरणियों st और inc को परिभाषित करें, और एक पूर्णांक प्रकार का डेटा कैप बनाएं
प्रारंभकर्ता में, कैप सेट करें:=एन और सेट इंक:=आकार की एक नई सरणी एन + 10
पुश (x) विधि के लिए, यदि स्टैक का आकार कैप नहीं है, तो x को सेंट में डालें।
पॉप () ऑपरेशन इस तरह होगा -
अगर सेंट खाली है, तो -1 पर लौटें
अन्यथा
- स्टैक का शीर्ष:=स्टैक का शीर्ष + inc [स्टैक का शीर्ष सूचकांक]
- यदि स्टैक में कुछ तत्व हैं, तो inc [st - 2 का आकार] inc [st – 1 का आकार]
  बढ़ाएं
- inc [s - 1 का आकार] :=0
- x :=सेंट का अंतिम तत्व
- वापसी x
इंक () विधि इस प्रकार काम करेगी -
k को 1 से घटाएं
k :=k का न्यूनतम और st – 1 का आकार
अगर के <0, तो वापस लौटें
वैल द्वारा इंक [के] बढ़ाएं।

उदाहरण (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;
   }
};
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;
}

इनपुट

See the main() in the program

आउटपुट