ออกแบบสแต็คด้วยการดำเนินการที่เพิ่มขึ้นใน C ++

สมมติว่าเราต้องการออกแบบสแต็กที่รองรับการทำงานต่อไปนี้

CustomStack(int maxSize) สิ่งนี้เริ่มต้นวัตถุด้วย maxSize ซึ่งเป็นจำนวนสูงสุดขององค์ประกอบในสแต็ก หรือไม่ทำอะไรเลยหากสแต็กถึงขนาดสูงสุด
ถือเป็นโมฆะ push(int x) สิ่งนี้จะแทรก x ไปที่ด้านบนของสแต็กหากสแต็กยังไม่ถึงขนาดสูงสุด
int pop() การดำเนินการนี้จะลบและส่งคืนส่วนบนสุดของสแต็กหรือ -1 หากสแต็กว่างเปล่า
void inc(int k, int val) สิ่งนี้จะเพิ่มองค์ประกอบ k ด้านล่างของสแต็กโดย val หากมีองค์ประกอบน้อยกว่า k รายการในสแต็ก ให้เพิ่มองค์ประกอบทั้งหมดในสแต็ก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดอาร์เรย์สองอาร์เรย์ st และ inc และสร้างแคปข้อมูลประเภทจำนวนเต็มหนึ่งค่า
ใน initializer ให้ set cap :=N และ set inc :=a new array of size N + 10
สำหรับเมธอด push(x) หากขนาดของสแต็กไม่ใช่ cap ให้ใส่ x ลงใน st.
การดำเนินการ pop() จะเป็นเช่น −
หาก st ว่างเปล่า ให้คืนค่า -1
อย่างอื่น
- ด้านบนของสแต็ก :=ด้านบนของสแต็ก + inc[ดัชนีบนสุดของสแต็ก]
- หาก stack มีองค์ประกอบอยู่บ้าง ให้เพิ่ม inc[size of st - 2] โดย inc[size of 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

ผลลัพธ์