使用C ++设计带有增量操作的堆栈

假设我们要设计一个支持以下操作的堆栈。

• CustomStack（int maxSize）这将使用maxSize初始化对象，该maxSize是堆栈中元素的最大数量；如果堆栈达到maxSize，则不执行任何操作。

• void push（int x）如果堆栈尚未达到maxSize，则将x插入堆栈的顶部。

• intpop()这将删除并返回栈顶；如果栈为空，则返回-1。

• void inc（int k，int val）这将堆栈的底部k个元素递增val。如果堆栈中的元素少于k，则只需增加堆栈中的所有元素。

为了解决这个问题，我们将遵循以下步骤-

• 定义两个数组st和inc，并创建一个整数类型数据上限

• 在初始化程序中，设置cap：= N并设置inc：=一个大小为N + 10的新数组

• 对于push(x)方法，如果堆栈大小不是上限，则将x插入st。

• 该pop()操作会像-

• 如果st为空，则返回-1

• 除此以外

• 堆栈顶部：=堆栈顶部+ inc [堆栈顶部索引]

• 如果堆栈中包含某些元素，则将inc [st-2]的大小增加inc [st-1的大小]

• inc [s的大小-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;
   }
};
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

输出结果

2
103
202
201
-1