包含min函数的栈 python,栈是实现函数调用所必需的数据结构

　　题目：

　　定义堆栈的数据结构。请在此类型中实现一个min函数，该函数可以获取堆栈的最小元素。在这个栈中，调用min、push和pop的时间复杂度为O(1)。

　　思路：

　　要使时间复杂度为O(1)，每有一个新元素被推入栈中，栈中的所有元素都要排序，最小的元素要在栈顶。但是这种想法并不能保证最后推入堆栈的元素会先被释放，因为这个数据结构已经不是堆栈了。

　　所以使用一个辅助成员变量来存储最小的元素。每次一个新元素被压入堆栈，如果元素小于当前最小的元素，最小的元素将被更新。但是，如果当前较小的元素被从堆栈中弹出，如何获得下一个最小的元素是一个问题。分析到这里，我们发现仅仅添加一个成员变量来存储最小元素是不够的，也就是说，当最小元素被弹出堆栈时，我们希望得到下一个最小元素。所以在压入最小的元素之前，我们必须保存第二小的元素。因此，最小的元素每次都可以由一个辅助堆栈保存。

　　例子佐证：

　　代码实现：

　　公共类Main { stack integer data=new stack integer()；//Stack Integer Min=用于存储元素的新堆栈Integer()；//辅助堆栈。每次在数据堆栈中输入元素时，最小辅助堆栈都会存储当前数据堆栈中的最小元素。//数据栈和min栈的入口元素是public void stackwithminpush(int item){ data . push(item)；if(min . size()==0 item min . peek()){ min . push(item)；} else { min . push(min . peek())；} }//弹出数据栈和min栈的元素，public void stackwithminpop(){ if(data . size()0min . size()0){ data . pop()；min . pop()；} }//数据栈的顶层元素，public int stackwithdatatop(){ if(data . size()0){ return data . peek()；}返回0；}//min栈顶元素，是数据栈中现有元素的最小元素，public int stackwithminimin(){ if(data . size()0min . size()0){ return min . peek()；}返回0；}}笑点低的帅哥：

　　如果变成包含max函数的栈呢？其实道理都一样，只不过一个是最小的，一个是最大的。

　　代码实现：

　　公共类Main { stack integer data=new stack integer()；//栈整数Max=新栈整数()；//辅助堆栈。每次在数据栈中输入一个元素，min辅助栈存储当前数据栈中最大的元素，public void stackwithmaxpush(int item){ data . push(item)；if(max . size()==0 item max . peek()){ max . push(item)；} else { max . push(max . peek())；} } public void stackWithMaxPop(){ if(max . size()0 data . size()0){ data . pop()；max . pop()；} } public int stackWithDataTop(){ if(data . size()0){ return data . peek()；}返回0；} public int stackWithMaxMax(){ if(data . size()0 max . size()0){ return max . peek()；}返回0；}}小结：

　　考察对stack的理解。当面对抽象的问题时，我们有时可以举一些例子来使问题具体化。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。