本文共 2729 字，大约阅读时间需要 9 分钟。

实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

具体实现如下：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;template
       
        class Stack{public:	void Push(const T& x);	void Pop();	T& Min();	void PrintS();private:	stack
        
          Sk;//存放栈中所有元素的 stack
         
           MinSk;//存放栈中最小元素的};template
          
           void Stack
           
            ::Push(const T& x){ Sk.push(x); //当MinSk为空时，先存放一个元素；当比较入栈元素小于栈顶元素时，入栈 if (MinSk.empty() || x < MinSk.top()) { MinSk.push(x); }}template
            
             void Stack
             
              ::Pop(){ if (Sk.empty()) { cout << "stack is empty!" << endl; return; } //如果出栈元素等于MinSk中栈顶元素，则MinSk需pop()该元素，使MinSk栈顶始终存放Sk栈中最小元素 if (Sk.top() == MinSk.top()) { MinSk.pop(); } Sk.pop();}template
              
               T& Stack
               
                ::Min(){ assert(!MinSk.empty()); return MinSk.top();}template
                
                 void Stack
                 
                  ::PrintS(){ if (Sk.empty()) { cout << "stack is empty!" << endl; return; } stack
                  
                    tmp = Sk; stack
                   
                     mintmp = MinSk; cout << "stack: "; while (!tmp.empty()) { cout << tmp.top() << " "; tmp.pop(); } cout << "\nminstack: "; while (!mintmp.empty()) { cout << mintmp.top() << " "; mintmp.pop(); } cout << endl;}//测试用例void Test4(){ //Stack
                    
                      s1; //s1.Push(9); //s1.Push(5); //s1.Push(7); //s1.Push(3); //s1.Push(8); s1.Pop(); s1.Pop(); s1.Pop(); s1.Pop(); s1.Pop(); s1.Pop(); Stack
                     
                       s1; s1.Push("sssss"); s1.Push("syikl"); s1.Push("yyyyy"); s1.Push("fffff"); s1.Push("lllll"); s1.PrintS(); cout << s1.Min() << endl;}
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

【干货小知识】自主实现一个栈，具体实现如下：

template
   
    class Stack{public:	Stack()		:_arr(NULL)		, _size(0)		, _capacity(0)	{}	Stack(const Stack
    
     & s)		:_arr(new T[s._size])		, _size(s._size)		, _capacity(s._size)	{		for (size_t i = 0; i < _size; i++)		{			_arr[i] = s._arr[i];		}	}	Stack
     
      & operator=(const Stack
      
       & s)	{		if (this != &s)		{			T* tmp = new T[s._size];			delete[] _arr;			for (size_t i = 0; i < s._size; i++)			{				tmp[i] = s._arr[i];			}			_arr = tmp;			_size = s._size;			_capacity = s._capacity;		}		return *this;	}	~Stack()	{		if (_arr)		{			delete[] _arr;		}	}public:	void _CheckCapacity(size_t size)	{		if (size > _capacity)		{			_capacity += _capacity * 2 + 3;		}		T* tmp = new T[_capacity];		if (_arr)		{			for (size_t i = 0; i < _size; i++)			{				tmp[i] = _arr[i];			}		}		delete[] _arr;		_arr = tmp;	}	void Push(const T& x)	{		_CheckCapacity(_size + 1);		_arr[_size++] = x;	}	void Pop()	{		assert(_size > 0);		--_size;	}	bool Empty()	{		return _size == 0;	}	size_t Size()	{		return _size;	}	T& Top()	{		return _arr[_size - 1];	}	void PrintStack()	{		if (_size == 0)		{			cout << "Stack is empty!";		}		else		{			for (size_t i = 0; i < _size; i++)			{				cout << _arr[i] << " ";			}			cout << endl;		}	}private:	T* _arr;	size_t _size;	size_t _capacity;};
      
     
    
   

本文出自 “” 博客，请务必保留此出处

转载地址：http://silbi.baihongyu.com/