C++ এ প্রদত্ত ক্রিয়াকলাপগুলির সাথে সর্বাধিক স্ট্যাক নির্মাণের প্রোগ্রাম

ধরুন আমরা একটি সর্বোচ্চ স্ট্যাক তৈরি করতে চাই, যা নিম্নলিখিত অপারেশনগুলিকে সমর্থন করে −

• MaxStk() এটি একটি সর্বাধিক স্ট্যাকের একটি নতুন উদাহরণ তৈরি করবে

• push(val) স্ট্যাকে val সন্নিবেশ করায়

• top() স্ট্যাক থেকে শীর্ষস্থানীয় উপাদান পান

• max() স্ট্যাক থেকে সর্বাধিক উপাদান পান

• pop() স্ট্যাক থেকে শীর্ষস্থানীয় উপাদানটিকে সরিয়ে দেয় এবং ফেরত দেয়

• popmax() স্ট্যাক থেকে সর্বাধিক উপাদানটিকে সরিয়ে দেয় এবং ফেরত দেয়

এখন MasStk() কল করে সর্বাধিক স্ট্যাক তৈরি করুন, তারপরে যথাক্রমে 5, 15, 10, তারপর call top(), max(), popmax(), max() pop(), top() ফাংশনের মত তিনটি মান পুশ করুন। তাহলে প্রাথমিক স্ট্যাক স্ট্যাটাস হবে [5, 15, 10], এবং ফাংশনের জন্য সংশ্লিষ্ট আউটপুট:10, 15, 15, 10, 10, 5

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• pos_index :=0

• একটি সেট stk আরেকটি সেট aux

  সংজ্ঞায়িত করুন

• কনস্ট্রাক্টর সংজ্ঞায়িত করুন, এটি কোন বিশেষ কাজ করছে না

• একটি ফাংশন পুশ() সংজ্ঞায়িত করুন, এটি ভ্যাল নেবে,

• pos_index , val stk এ সন্নিবেশ করুন

• aux-এ val, pos_index সন্নিবেশ করুন

• (pos_index 1 দ্বারা বাড়ান)

• একটি ফাংশন টপ()

  সংজ্ঞায়িত করুন

• যদি stk খালি হয়, তাহলে −

  • ফিরুন −1

• stk

  এর প্রথম আইটেমের দ্বিতীয় মান ফেরত দিন

• একটি ফাংশন সর্বাধিক()

  সংজ্ঞায়িত করুন

• যদি aux খালি হয়, তাহলে −

  • ফিরুন −1

• aux-এর প্রথম আইটেমের প্রথম মান ফেরত দিন

• একটি ফাংশন pop()

  সংজ্ঞায়িত করুন

• যদি stk খালি হয়, তাহলে −

  • ফিরুন −1

• id :=stk এর প্রথম আইটেমের প্রথম মান, ret =stk এর প্রথম আইটেমের দ্বিতীয় মান

• stk

  থেকে stk-এর প্রথম উপাদান মুছে দিন

• aux

  থেকে জোড়া (ret, id) মুছুন

• রিটার্ন রিটার্ন

• একটি ফাংশন popmax()

  সংজ্ঞায়িত করুন

• যদি aux খালি হয়, তাহলে −

  • ফিরুন −1

• ret :=aux-এর প্রথম আইটেমের প্রথম মান, id =aux-এর প্রথম আইটেমের দ্বিতীয় মান

• aux থেকে aux-এর প্রথম উপাদান মুছুন

• stk

  থেকে জোড়া(id, ret) মুছুন

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class MaxStk {
   int pos_index = 0;
   set<pair<int, int>, greater<>> stk, aux;
   public:
   MaxStk() {}
   void push(int val) {
      stk.emplace(pos_index, val);
      aux.emplace(val, pos_index);
      pos_index++;
   }
   int top() {
      if (stk.empty())
      return −1;
      return stk.begin()−>second;
   }
   int max() {
      if (aux.empty())
      return −1;
      return aux.begin()−>first;
   }
   int pop() {
      if (stk.empty())
      return −1;
      int id = stk.begin()−>first, ret = stk.begin()−>second;
      stk.erase(stk.begin());
      aux.erase({ret, id});
      return ret;
   }
   int popmax() {
      if (aux.empty())
      return −1;
      int ret = aux.begin()−>first, id = aux.begin()−>second;
      aux.erase(aux.begin());
      stk.erase({id, ret});
      return ret;
   }
};
int main(){
   MaxStk max_stk;
   max_stk.push(5);
   max_stk.push(15);
   max_stk.push(10);
   cout << max_stk.top() << endl;
   cout << max_stk.max() << endl;
   cout << max_stk.popmax() << endl;
   cout << max_stk.max() << endl;
   cout << max_stk.pop() << endl;
   cout << max_stk.top() << endl;
}

ইনপুট

max_stk.push(5)
max_stk.push(15)
max_stk.push(10)
max_stk.top()
max_stk.max()
max_stk.popmax()
max_stk.max()
max_stk.pop()
max_stk.top()

আউটপুট

10
15
15
10
10
5