数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
定义一个集合stk和另一个集合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中删除第一个元素。
从aux中删除(ret, id)对。
返回ret。
定义一个函数popmax()。
如果aux为空，则：
返回-1。
ret := aux第一个元素的第一个值，id := aux第一个元素的第二个值。
从aux中删除第一个元素。
从stk中删除(id, ret)对。
返回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
更新于：2020年12月26日
浏览量：295
广告