包含min函数的栈
程序员文章站
2024-01-29 12:50:04
...
题目描述:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中调用push、pop、top、min的时间复杂度都是o(1)。
解读:(借助于辅助栈)
这里要再定义一个辅助栈,用来存放每次入栈时的最小元素,这样两个栈同时压入数据,数据栈数据正常数据压入和弹出,辅助栈压入数据的时候,要看压入的数据是否大于辅助栈的栈顶数据(如果大于栈顶数据,则复制此时辅助栈栈顶数据,再次压入辅助栈中),详细步骤见下图:
- 首先两个栈左边为数据栈,右边为辅助栈,当为空时,两个栈数据进入
- 第二个数据5压入数据栈,但是5大于3,所以此时最小的数据是3,把3压入辅助栈
- 第三个数据4压入数据栈,但是4大于3,所以此时最小的数据是3,把3压入辅助栈
- 第四个数据0压入数据栈,此时0小于3,所以此时最小的数据是0,把0压入辅助栈
- 数据栈弹出数据,弹出栈顶0,辅助栈弹出栈顶数据0,每次辅助栈弹出时,都是当前数据栈中最小的数据
class solution{
private:
stack<int> data_stack;
stack<int> min_stack;
public:
void push(int value){
if(data_stack.isEmpty()&&min_stack.isEmpty())
{
data_stack.push(value);
min_stack.push(value);
}
else
{
if(value>min_stack.top())
{
data_stack.push(value);
min_stack.push(min_stack.top());
}
else
{
data_stack.push(value);
min_stack.push(value);
}
}
}
void pop()
{
if(!data_stack.isEmpty()&&!min_stack.isEmpty)
{
data_stack.pop();
min_stack.pop();
//return min_stack.top();
}
}
int top()
{
return data_stack.top();
}
int min()
{
return min_stack.top();
}
bool empty()
{
if(data_stack.isEmpty)
return true;
else
return false;
}
}
上一篇: 用户登录之cookie信息安全小结
下一篇: Android实现弹出登陆框的方案