扩展堆栈（stack） O(1) 时间访问栈中最小值（或最大值）

本文主要是介绍扩展堆栈（stack） O(1) 时间访问栈中最小值（或最大值），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：扩展stack的实现，完成正常的push，pop操作，新增访问最小（或最大）元素的接口Min（），使得push，pop，Min的时间复杂度都是O(1)。

问题分析：拿到这道题，我们最先的思考往往是，设计一个算法从栈中拿到最小值，所以开始考虑任何可以用来实现该功能的排序和查找算法。假设栈中有n个元素，一切排序和查找都不可能实现O(1)的时间复杂度找到最小值。

再看题目，既然是扩展stack的实现，stack是一种数据结构，一种数据的组织方式，扩展它，也就允许我们对其数据组织方式和存储内容作一些改变吧。所以我们就有了下面的思路：

把当前最小值存起来，并且在进行push和pop操作的时维护它。维护要求如下：

1、如果有比当前最小值大的元素入栈，当前最小值不变

2、如果有比当前最小值大的元素入栈，当前最小值变为新加入元素（考虑一下等于的时候啊，呵呵）

3、如果有比当前最小值大的元素出栈，当前最小值不变（注意：弹出的操作时，一定不可能弹出比当前最小值还小的元素，也就是说如果你弹出了一个比当前最小值还小的元素，就证明你的那个当前最小值不是当前最小值）

4、如果有和当前最小值的元素相同出栈，当前最小值变为当前当前最小值入栈之前那个最小值，当前最小值退出。

综上，我们发现一个规律：对于最小值而言，如果有更小的数入栈，需要将其保存为当前最小，如果当前最小数出栈，当前最小数变成

当前最小数入栈之前那个最小数，所以，对于最小数而言也具有先进后出，后进先出的特点，只是并不是每次push和pop操作都牵涉到

最小数的进出。所以我们考虑用双栈来实现，一个栈用来存放数据，满足栈数据结构原始要求，一个栈用来存放最小值，在每次push和

pop操作执行时，按照上面的规则维护最小值栈。

下面是扩展栈的实现：（O(1)的pop，push，和Min访问最小值操作）MinStack.h

[c-sharp] view plain copy  
 #ifndef _H_MINSTACK_H_  
 #define _H_MINSTACK_H_  
 #include <iostream>  
 template <class T>  
 class MinStack  
 {  
     public:  
         MinStack():MaxSize(20)  
         {  
             top=MinTop=-1;  
             stack=new T[MaxSize];  
             Mins=new T[MaxSize];      
         }  
         MinStack(int MaxSize);  
         ~MinStack()  
         {  
             delete [] stack;  
             delete [] Mins;  
         }  
         bool isEmpty(){return top==-1;}  
         bool isFull(){return top==(MaxSize-1);}  
         MinStack<T>& push(const T& x);  
         MinStack<T>& pop(T& x);  
         T Top(){return stack[top];}  
         T Min(){return Mins[MinTop];}  
     private:  
         int top,MinTop,MaxSize;  
         T *stack,*Mins;  
 };  
 template <class T>  
 MinStack<T>::MinStack(int MaxSize)  
 {  
     top=MinTop=-1;  
     this->MaxSize=MaxSize;  
     stack=new T[MaxSize];  
     Mins=new T[MaxSize];      
 }  
 template <class T>  
 MinStack<T>& MinStack<T>::push(const T& x)  
 {  
     if(isEmpty())  
     {  
         stack[++top]=x;  
         Mins[++MinTop]=x;  
     }  
     else  
     {  
         if(isFull())  
         {  
             std::cout<<"no space "<<std::endl;  
         }  
         else  
         {  
             stack[++top]=x;  
             if(x<=Mins[MinTop])//注意“==”时也要压入  
                 Mins[++MinTop]=x;  
         }  
     }  
     return *this;  
 }  
 template <class T>  
 MinStack<T>& MinStack<T>::pop(T& x)  
 {  
     if(isEmpty())  
     {  
         std::cout<<"Stack is empty"<<std::endl;  
     }  
     else  
     {  
         x=stack[top--];  
         if(x==Mins[MinTop])  
             --MinTop;  
     }  
 }  
 #endif //_H_MINSTACK_H_  

下面是测试（MinStacktest.cc）

[c-sharp] view plain copy  
 #include <iostream>  
 #include "MinStack.h"  
   
 int main()  
 {  
     MinStack<int> ms(20);  
     ms.push(20);ms.push(22);ms.push(18);  
     std::cout<<"the Minest value is "<<ms.Min()<<std::endl;  
     ms.push(11);ms.push(44);ms.push(5);  
     std::cout<<"the Minest value is "<<ms.Min()<<std::endl;  
     int x;  
     ms.pop(x);  
     std::cout<<"the Minest value is "<<ms.Min()<<std::endl;  
     return 0;  
   
 }  

编译运行结果如下：

[jim@gpu1 stack]$ g++ -o MinStacktest MinStacktest.cc MinStack.h
[jim@gpu1 stack]$ ./MinStacktest
the Minest value is 18
the Minest value is 5
the Minest value is 11

这篇关于扩展堆栈（stack） O(1) 时间访问栈中最小值（或最大值）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！