用一个数组实现两个栈(共享栈)

2017-06-03 21:45 阅读 615 次 评论 0 条

一个数组实现共享栈是一个经典的算法,这些年也备受笔试/面试的青睐,其核心思想不难,但是对于临界点的把握是比较容易出错的,下面列举出两种常用方法。

1.奇偶占位法

如下图所示,对stack1进行偶数位压栈,对stack2进行奇数位压栈。top即栈顶,分别指向当前栈中最后一个元素的下一个将要压栈的位置。栈的数据结构较为简单,这里就不对其push、pop等操作过多描述,对应此图进行操作是很容易实现的。

此方法的不足在于,如果stack1插入了很多元素,而stack2插入元素极少,那么将会浪费很多资源,造成浪费,因此不推荐大家使用。

2.首尾相遇法

没有一张图解决不了的问题,如果有,那就两张。首尾相遇的算法思想也很简单,但是在扩容的时候要对stack2做特殊处理,将stack2的数据后移的同时,将stack2的栈顶_top2也后移。

//两种方法的测试用例

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:用一个数组实现两个栈(共享栈) | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情