資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告