用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
定义一个setstk另一个setaux
定义构造函数,这没有做任何特殊的任务
定义一个函数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