• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

可以求最小值的栈的实现(C语言)

c语言 海叔叔 16小时前 7次浏览 已收录 0个评论

问题:实现一个栈,要求含有函数push, pop, min,并且他们的时间复杂度都是O(1)。

解决思路:如图1所示,在普通栈的基础上,增加当前最小节点的指针currentMinNode,以及指向下一个最小节点的指针

nextMinNode。当push元素到栈里面时,如果新元素小于栈中的currentMinNode,需要更新当前最小元素指针currentMinNode,

使它指向新元素;如果新元素不小于currentMinNode,和普通栈一样直接添加新节点。当从栈中POP元素时,如果当前栈顶

节点的nextMinNode为空,则和普通栈一样直接删除栈顶节点;如果当前栈顶节点的nextMinNode不为空,则更新currentMinNode

指向栈顶节点的nextMinNode,然后再删除栈顶节点。本文主要说明求栈中最小值的情形,实际上,这里的处理思路可以很方便的迁移到求栈中最大值的情形。

含有MIN函数的栈的C语言实现源码如下,这里栈中可存储的数据是简单的INT类型。


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址