Thiết kế ngăn xếp với hoạt động tăng dần trong C ++

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

CustomStack (int maxSize) Điều này khởi tạo đối tượng với maxSize, là số phần tử tối đa trong ngăn xếp hoặc không làm gì nếu ngăn xếp đạt đến Kích thước tối đa.
void push (int x) Thao tác này sẽ chèn x vào đầu ngăn xếp nếu ngăn xếp chưa đạt đến maxSize.
int pop () Thao tác này sẽ xóa và trả về phần trên cùng của ngăn xếp hoặc -1 nếu ngăn xếp trống.
void inc (int k, int val) Điều này làm tăng k phần tử dưới cùng của ngăn xếp bằng val. Nếu có ít hơn k phần tử trong ngăn xếp, chỉ cần tăng tất cả các phần tử trong ngăn xếp.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định hai mảng st và inc và tạo một giới hạn dữ liệu kiểu số nguyên
trong trình khởi tạo, đặt cap:=N và đặt inc:=một mảng mới có kích thước N + 10
Đối với phương thức push (x), nếu kích thước của ngăn xếp không giới hạn, thì hãy chèn x vào st.
Thao tác pop () sẽ giống như -
nếu st trống, thì trả về -1
nếu không thì
- top of stack:=top of stack + inc [chỉ số trên cùng của ngăn xếp]
- nếu ngăn xếp có một số phần tử, thì hãy tăng inc [size of st - 2] lên inc [size of st - 1]
- inc [kích thước của s - 1]:=0
- x:=phần tử cuối cùng của st
- trả lại x
Phương thức inc () sẽ hoạt động như sau -
giảm k đi 1
k:=min of k và size st - 1
nếu k <0, thì trả về
tăng inc [k] theo val.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách 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;
   }
};
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

See the main() in the program

Đầu ra