数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 设计一个带增量操作的栈
假设我们想要设计一个支持以下操作的栈。
CustomStack(int 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[栈顶索引]
如果栈有一些元素，则将 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
更新于: 2020-04-29
549 次查看
广告