【C/C++练习题】栈中添加min方法

《剑指Offer》面试题30：包含min函数的栈

1 题目

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

2 问题分析

构造一个辅助栈，保证辅助栈空间的栈顶元素始终是数据栈中的最小元素。那么当程序对栈进行压栈or弹栈操作时，对应的辅助栈也要进行操作。

3 代码

  

   

    

     

    
    

     

      #include <stack>
     
    
   

    

     

    
    

     

      #include <assert.h>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题.实现一个包含min函数的栈
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      template <typename T> 
     
    
   

    

     

    
    

     

      class StackWithMin
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    StackWithMin() {}
     
    
   

    

     

    
    

     
    virtual ~StackWithMin() {}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    // T& top();
     
    
   

    

     

    
    

     
    // const T& top() const;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    void push(const T& value);
     
    
   

    

     

    
    

     
    void pop();
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    const T& min() const;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    // bool empty() const;
     
    
   

    

     

    
    

     
    // size_t size() const;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      private:
     
    
   

    

     

    
    

     

          std::stack<T>   m_data;     // 数据栈，存放栈的所有元素
     
    
   

    

     

    
    

     

          std::stack<T>   m_min;      // 辅助栈，存放栈的最小元素
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      template <typename T> 
     
    
   

    

     

    
    

     

      void StackWithMin<T>::push(const T& value)      //实现push方法
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    //1.value压入数据栈
     
    
   

    

     

    
    

     

          m_data.push(value);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    //2.将当前最小数值压入辅助栈(第一个数值，直接压入辅助栈中)
     
    
   

    

     

    
    

     
    if(m_min.size() == 0 || value < m_min.top())
     
    
   

    

     

    
    

     

              m_min.push(value);
     
    
   

    

     

    
    

     
    else
     
    
   

    

     

    
    

     

              m_min.push(m_min.top());
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      template <typename T> 
     
    
   

    

     

    
    

     

      void StackWithMin<T>::pop()                 //实现pop方法
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    //1.检查栈是否为空
     
    
   

    

     

    
    

     
    assert(m_data.size() > 0 && m_min.size() > 0);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    //2.将数值弹出
     
    
   

    

     

    
    

     

          m_data.pop();
     
    
   

    

     

    
    

     

          m_min.pop();
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      template <typename T> 
     
    
   

    

     

    
    

     

      const T& StackWithMin<T>::min() const           //实现min方法
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    //检查栈是否为空
     
    
   

    

     

    
    

     
    assert(m_data.size() > 0 && m_min.size() > 0);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    //返回最小数值
     
    
   

    

     

    
    

     
    return m_min.top();
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char* argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          StackWithMin<int> stack;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          stack.push(3);
     
    
   

    

     

    
    

     

          stack.push(4);
     
    
   

    

     

    
    

     

          stack.push(2);
     
    
   

    

     

    
    

     

          stack.push(3);
     
    
   

    

     

    
    

     

          cout << stack.min() << endl;
     
    
   

    

     

    
    

     

          stack.pop();
     
    
   

    

     

    
    

     

          stack.pop();
     
    
   

    

     

    
    

     

          cout << stack.min() << endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/99294385