使用 C++ 设计一个具有增量操作的堆栈

c++server side programmingprogramming

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

CustomStack(int maxSize) 这会使用 maxSize 初始化对象，maxSize 是堆栈中元素的最大数量，如果堆栈已达到 maxSize，则不执行任何操作。
void push(int x) 如果堆栈尚未达到 maxSize，则将 x 插入堆栈顶部。
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[顶部索引stack]
- 如果 stack 有某个元素，则将 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;
}