包含min函数(栈的最小元素)的栈

2017-05-01 21:22 阅读 449 次 评论 0 条

查找栈中的最小元素是一个很简单的问题,我们只需要每次压入一个元素就比较一下,然后将栈中元素排序,将最小的元素位于栈顶即可,这样虽然满足了O(1)的时间复杂度,但是并不能保证最后压入栈的元素最先出栈。

设计要求

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

算法分析

鉴于不能保证最后压入栈的元素最先出栈,我们可以添加一个成员变量来存放最小的元素,但是如果想获取次小的元素是不够的,因此在压栈之前我们需要将次小、次次小元素保存在一个辅助栈中。这里需要两个栈:数据栈辅助栈

①当我们首次入栈(数据栈)的同时,将当前元素也压入辅助栈中,充当当前辅助栈的最小元素。

②第二次之后入栈(数据栈)的同时,如果当前元素小于辅助栈的栈顶元素,则将当前元素压入辅助栈中,此时最小值更新为当前元素;如果当前元素大于辅助栈的栈顶元素,则将辅助栈的栈顶元素压入辅助栈。

③最终辅助栈的栈顶元素即栈中的最小元素,栈顶之下即次小元素。

下面举个例子:栈内压入3、4、2、1之后连续两次出栈再压入0时,数据栈、辅助栈和最小值的状态:

步骤
操作
数据栈
辅助栈
最小值
1
压入3
3
3
3
2
压入4
3、4
3、3
3
3
压入2
3、4、2
3、3、2
2
4
压入1
3、4、2、1
3、3、2、1
1
5
出栈
3、4、2
3、3、2
2
6
出栈
3、4
3、3
3
7
压入0
3、4、0
3、3、0
0

源代码及注释

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:包含min函数(栈的最小元素)的栈 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情