标题

[学习经验]一个数组如何实现栈

责任编辑:admin
日期:2012-12-03

 一个数组如何实现栈

     1. 一个数组实现一个栈

          这个最简单,只需使得栈底位于数组开始位置即可,出栈入栈都容易实现,如果栈顶到达数组尾部则栈满。

     2. 一个数组实现两个栈

          这个可以让两个栈的栈底一个在数组的头部,一个在数组的尾部,出栈入栈也容易实现,判断栈满只需判断两个的栈顶是否重合即可。

     3、一个数组实现三个栈

          下面这两种方法都不能充分的利用空间,不过也是找到的最好的两种方法了。

          (1). 实现3个栈可以交错存储 

             设下标从0开始,index为索引 

             index%3==0的存储第一个 

             index%3==1的存储第二个 

             index%3==2的存储第三个 

             如果第3个满了,从第二个的高位往下存,第二个满了从第一个的高位往下,第一个满了从第三个的高位存。 

             如果某个栈先满的,最后一位要空着作为自然满的标志,两个栈要空一个空位作为区分。

          (2). 两个栈放置在数组的两端,生长方向相对,另一个栈从数组的中心出发,生长方向可以向两侧延伸。

                 栈满的条件,左边栈的顶部小于等于中心栈的左顶,右边栈的顶大于等于中心栈的右顶

     4、一个数组实现多于三个栈

           对于这种情况可以把上面“一个数组实现三个栈”的(1)扩展,如下:

           实现m个栈可以交错存储

           设下标从0开始,index为索引 

 

         index%n==0 的存储在第一个栈中 

         index%n==1 的存储在第二个栈中  

         index%n==2 的存储在第三个栈中

         ...... 

           index%n==m 的存储在第m个栈中

           如果第m个满了,从第m-1个的高位往下存,第m-1个满了从第m-2个的高位往下,第一个满了从第m个的高位存。 

 

         如果某个栈先满的,最后一位要空着作为自然满的标志,两个栈要空一个空位作为区分。

 

注: 当栈的数量大于2的时候,都会出现无法充分利用空间的问题。求更优的解决办法!!!

 

阅读:

相关新闻:
评论