包含min函数的栈
题目: 定义站的数据结构, 在该类型中实现一个能够得到最小数的min函数, min/push/pop的时间复杂度都是1
解题思路
- 1 以单个栈是不可能是实现的, 必须使用一个辅助栈
- 2 _stack正常的存储数据, 使用push/pop时的时间复杂的都是对普通的栈操作, 时间复杂的为1
- 3 _min顶端存储最小值, 使用min函数时, 通过top获取即可, 时间复杂的为1
- 4 _min进行push操作时, 每次将value和top值进行比较, 存入较小的一个, 保证了顶端时最小值
_stack栈 [5, 4, 5, 5 ,3]
_min栈 [5, 4, 4, 4, 3] - 5 _min进行pop操作时, 直接pop即可, 以上栈做说明
| pop | min |
|---|---|
| 3 | 4 |
| 5 | 4 |
| 5 | 4 |
| 4 | 4 |
| 5 | 4 |
代码
template<typename T>
class StackWithMin
{
private:
/* data */
stack<T> _stack;
stack<T> _min;
public:
StackWithMin(/* args */);
~StackWithMin();
void push(T t);
T pop();
T min();
};
template<class T>
void StackWithMin<T>::push(T t)
{
_stack.push(t);
if(_min.size() == 0)
{
_min.push(t);
}
else
{
_min.push((_min.top() > t) ? t : _min.top());
}
}
template<class T>
T StackWithMin<T>::pop()
{
T ret = _stack.top();
_min.pop();
_stack.pop();
return ret;
}
template<class T>
T StackWithMin<T>::min()
{
assert(_min.size());
return _min.top();
}
