用C ++中的给定操作构造最大堆栈的程序

假设我们要制作一个最大的堆栈，它支持以下操作-

• MaxStk() 这将构造一个最大堆栈的新实例

• push(val) 将val插入堆栈

• top() 从堆栈中获取最高的元素

• max() 从堆栈中获取最大元素

• pop() 从堆栈中删除并返回最上面的元素

• popmax() 从堆栈中删除并返回最大元素

现在通过调用构造的最大堆栈MasStk()，然后推像5,15，10，然后调用三个值top()，max()，popmax()，max() pop()，top()分别功能。那么初始堆栈状态将为[5、15、10]，以及该功能的相应输出：10、15、15、10、10、5

为了解决这个问题，我们将遵循以下步骤-

• pos_index：= 0

• 定义一个set stk另一个set aux

• 定义构造函数，这没有做任何特殊的任务

• 定义一个函数push()，将需要val，

• 将pos_index，val插入stk

• 将val，pos_index插入aux

• （将pos_index增加1）

• 定义功能 top()

• 如果stk为空，则-

• 返回-1

• 返回stk的第一项的第二个值

• 定义功能 max()

• 如果aux为空，则-

• 返回-1

• 返回aux的第一项的第一个值

• 定义功能 pop()

• 如果stk为空，则-

• 返回-1

• id：= stk的第一项的第一个值，ret = stk的第一项的第二个值

• 从stk删除stk的第一个元素

• 从aux删除对(ret,id)

• 返回ret

• 定义功能 popmax()

• 如果aux为空，则-

• 返回-1

• ret：= aux的第一项的第一个值，id = aux的第一项的第二个值

• 从aux删除aux的第一个元素

• pair(id, ret)从stk删除

• 返回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