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 :=N을 설정하고 inc :=크기가 N + 10인 새 배열
을 설정합니다.
push(x) 메서드의 경우 스택의 크기가 cap이 아니면 x를 st에 삽입합니다.
pop() 작업은 다음과 같습니다. -
st가 비어 있으면 -1을 반환합니다.
그렇지 않으면
- 스택의 상단 :=스택의 상단 + inc[스택의 상단 인덱스]
- 스택에 요소가 있으면 inc[size of st - 2]를 inc[size of st – 1]
  만큼 증가시킵니다.
- inc[크기 - 1] :=0
- x :=st의 마지막 요소
- x를 반환
inc() 메서드는 다음과 같이 작동합니다 -
k를 1만큼 감소
k :=k의 최소값과 st의 크기 – 1
k <0이면 반환
val만큼 증가[k] 증가

예시(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

출력