【算法题目】包含min函数的栈

时间:2021-07-08 15:32:01

  题目来源:《剑指offer》面试题21

  题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min,push以及pop的时间复杂度都是O(1)。

  分析:假设用于存储主要数据的栈称为数据栈。我们增加一个辅助栈,它的栈顶元素永远是当前数据栈中元素的最小值。当插入元素时,如果插入的元素比辅助栈栈顶还小,那么就往辅助栈压入这个数据作为当前数据栈新的最小值。如果大的话,再次压入辅助栈的栈顶元素,表明来了一个新元素后,最小值没有变换。

//m_data是数据栈,m_min是辅助栈
template<typename T> void StackWithMin<T>::push(const T& value) {
m_data.push(value); if (m_min.empty() || value < m_min.top())
m_min.push(data);
else
m_min.push(m_min.top());
} template<typename T> void StackWithMin<T>::pop(const T& value) {
m_min.pop();
m_data.pop();
} template<typename T> const T& StackWithMin<T>::min() const {
return m_min.top();
}