使用C ++设计带有增量操作的堆栈
假设我们要设计一个支持以下操作的堆栈。
CustomStack（intmaxSize）这将使用maxSize初始化对象，该maxSize是堆栈中元素的最大数量；如果堆栈达到maxSize，则不执行任何操作。
voidpush（intx）如果堆栈尚未达到maxSize，则将x插入堆栈的顶部。
intpop()这将删除并返回栈顶；如果栈为空，则返回-1。
voidinc（intk，intval）这将堆栈的底部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