stack和heap都是常见的数据结构。现在我希望你设计一个容器，同时拥有stack和heap的特性，即该容器至少包含这四个接口：
(1) size：容器中元素的个数。
(2) push：向该容器中加入一个元素。
(3) stack_pop：从该容器中取出一个元素，且取出顺序与push顺序相反。
(4) heap_pop：从该容器中取出一个元素，且该元素是容器中值最大的。
一旦某个元素从容器中pop出去（无论是stack_pop还是heap_pop），该元素就不在容器中了，即一个元素只能被pop一次。
下面为样例，第一列是操作，第二列是操作完成后容器中的元素集合：
push(1) {1}
push(3) {1,3}
push(2) {1,3,2}
heap_pop()->3 {1,2}
stack_pop()->2 {1}
stack_pop()->1 {}
请设计该容器，定义所需的数据结构，实现以上四个接口（用你熟悉的语言或者伪码），并给出各个方法的计算复杂度和整个容器的空间复杂度。
class maxStack
{
stack<int>s,max_stack;
public:
maxStack()
{
}
int size()
{
return s.size();
}
void push(int val)
{
s.push(val);
if(max_stack.empty()||val>=max_stack.top())
{
max_stack.push(val);
}
}
int stack_pop()
{
int x=s.top();
s.pop();
if(!max_stack.empty()&&x==max_stack.top())
{
max_stack.pop();
}
return x;
}
int heap_pop()
{
int x=max_stack.top();
max_stack.pop();
stack<int>s1;
while(!s.empty())
{
if(s.top()!=x)
{
s1.push(s.top());
s.pop();
}
else
{
s.pop();
break;
}
}
while(!s1.empty())
{
s.push(s1.top());
s1.pop();
}
return x;
}
};
不过heap_pop()除了这种方法还没有想到更好的办法
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
