Thiết Kế Stack Với Hoạt Động Tăng Giá Trị Trong C++

Giả sử chúng ta muốn thiết kế một stack hỗ trợ các hoạt động sau:

• CustomStack(int maxSize): Khởi tạo đối tượng với maxSize là số phần tử tối đa trong stack hoặc không làm gì nếu stack đã đạt maxSize.

• void push(int x): Chèn x vào đỉnh stack nếu chưa đạt maxSize.

• int pop(): Xóa và trả về đỉnh stack hoặc -1 nếu stack rỗng.

• void inc(int k, int val): Tăng k phần tử đáy của stack lên val. Nếu stack có ít hơn k phần tử, tăng tất cả.

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa hai mảng st và inc, và biến nguyên cap.

• Trong constructor: cap = N; inc = vector(N+10).

• push(x): nếu st.size() != cap thì st.push_back(x).

• pop(): nếu st rỗng trả về -1; ngược lại: st.back() += inc[st.size()-1]; nếu st.size() > 1 thì inc[st.size()-2] += inc[st.size()-1]; inc[st.size()-1] = 0; x = st.back(); st.pop_back(); trả về x.

• increment(k, val): k--; k = min(k, st.size()-1); nếu k < 0 trả về; inc[k] += val.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#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;
    }
};

int 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;
}

Đầu vào

Xem hàm main() trong chương trình

Đầu ra

2 103 202 201 -1