首页 > C++ 实现带min函数的栈

C++ 实现带min函数的栈

我的问题是,对stack的使用,和类模板的使用。请高人帮我看看下面代码实现有什么问题?

#include <iostream>
#include <stack>

using namespace std;

template <typename T> 
class StackWithMin
{
public:
    void push(T elem);
    void pop();
    T top();
    T min();
private:
    stack<T>  dataStack;
    stack<T>  minStack;
};

template <typename T>
void StackWithMin<T>::push(T elem)
{
    dataStack.push(elem);
    if (minStack.empty() && minStack.top() > elem)
    {
        minStack.push(elem);
    }
}

template <typename T>
void StackWithMin<T>::pop()
{
    if (dataStack.empty())
    {
        return;
    }
    if (dataStack.top() == minStack.top())
    {
        minStack.pop();
    }
    dataStack.pop();
}


template <typename T>
T StackWithMin<T>::top()
{
    if (dataStack.empty())
    {
        return false;
    }
    return dataStack.top();
}


template <typename T> 
T StackWithMin<T>::min()
{
    if (minStack.empty())
    {
        return false;
    }
    return minStack.top();
}


int main(int argc, char const *argv[])
{
    StackWithMin<int> ss;
    ss.push(4);
    ss.push(9);
    ss.push(1);
    ss.push(11);
    ss.push(6);
    cout << "min:" << ss.min() << endl;
    cout << "top:" << ss.top() << endl;
    ss.pop(); 
    cout << "min:" << ss.min() << endl;
    cout << "top:" << ss.top() << endl;
    return 0;
}

template <typename T>
void StackWithMin<T>::push(T elem)
{
    dataStack.push(elem);
    // minStack.empty() || minStack.top() > elem
    if (minStack.empty() && minStack.top() > elem) 
    {
        minStack.push(elem);
    }
}

这个函数的条件判断中minStack.empty() && minStack.top() > elem两个条件运算有问题,因为&&运算符在计算了第一个条件为true后,程序还会去计算第二个条件,而这里程序第一次运行minStack.empty()true,这样运算minStack.top()会导致Invalid readsegmentation fault (core dumped). 楼主可以用valgrind测试一下就能知道程序非法访问了数据.


大眼一看 min 和 top 方法是重复代码

【热门文章】
【热门文章】