当前位置:   article > 正文

Java数据结构 栈(数组和链表)_栈的底层是链表还是数组

栈的底层是链表还是数组

使用数组来实现栈的ADT。

实现栈的自动扩容和迭代。

  1. import java.util.Iterator;
  2. /**
  3. *
  4. *
  5. *实现迭代和包含动态扩容和缩减空间的栈
  6. *实现消除弹栈游离
  7. * @param <Item>
  8. */
  9. public class Stack_array_zy<Item> implements Iterable<Item> {
  10. private Item[] aItems=(Item[]) new Object[1];//使用object【】接收
  11. //private Item[] aItems=(Item[]) new Item[1];理论上应该这样写,但是Java中是不允许创建泛型数组的。
  12. //所以只好通过object进行类型转换
  13. private int item_num=0;
  14. public boolean isEmpty() {
  15. return item_num==0;
  16. }
  17. public int size() {
  18. return item_num;
  19. }
  20. /**
  21. *
  22. * @param max
  23. * 更改容量的策略在栈中主要使用在入栈时候扩容 弹栈时候减缩
  24. */
  25. private void resize(int max) {
  26. Item[] expand=(Item[]) new Object[max];
  27. for(int i=0;i<item_num;i++) {
  28. expand[i]=aItems[i];
  29. }
  30. aItems=expand;
  31. }
  32. public void push(Item a) {
  33. if (item_num==aItems.length) {
  34. resize(2*aItems.length);
  35. }
  36. aItems[item_num++]=a;
  37. }
  38. public Item pop() {
  39. Item a=aItems[--item_num];
  40. aItems[item_num]=null;//避免对象的游离
  41. if (item_num<=aItems.length/4) {
  42. resize(aItems.length/2);
  43. }
  44. return a;
  45. }
  46. /**
  47. *
  48. */
  49. public Iterator<Item> iterator(){
  50. return new getIterable();
  51. }
  52. /**
  53. *
  54. * @author zongyun
  55. *通过继承iterator类,通过实例化从而产生一个iterator对象。
  56. */
  57. private class getIterable implements Iterator<Item>{
  58. private int i=item_num;//嵌套类可以访问包含类的变量。
  59. public boolean hasNext() {
  60. return i>0;
  61. }
  62. public void remove() {
  63. }
  64. public Item next() {
  65. return aItems[--i];
  66. }
  67. }
  68. //测试
  69. public static void main(String[] args) {
  70. // Stack_array_zy<Integer> a=new Stack_array_zy<Integer>();
  71. // for(int i=0;i<10;i++) {
  72. // a.push(i);
  73. // }
  74. // System.out.println(a.isEmpty());
  75. // System.out.println(a.size());
  76. // for(int s:a) {
  77. // System.out.print(s);
  78. // }
  79. // while(!a.isEmpty()) {
  80. // System.out.print(a.pop());
  81. // }
  82. }
  83. }

1.对于数组的实现方式,注意扩容策略的选择。我选择扩容增加一半,而缩减时,避免空间浪费,当前元素小于数组容量1/4时缩减一半,以达到栈中已有元素一半以内的适宜容量。

2.对于出栈后,栈中的变量仍然保留,通过赋null,实现对“游离”的消除。

链表实现代码

  1. /**
  2. *
  3. * @author --
  4. *
  5. * @param <T>
  6. */
  7. public class Stack_linkedlist_zy<T> {
  8. private Node first;
  9. private int N;
  10. private class Node{
  11. T item;
  12. Node next;
  13. }
  14. public boolean isEmpty() {
  15. if (first.next==null) {
  16. return true;
  17. }
  18. else return false;
  19. }
  20. public int size() {
  21. return N;
  22. }
  23. public void push(T a) {
  24. Node new_first=new Node();
  25. new_first.item=a;
  26. new_first.next=first;
  27. first=new_first;
  28. N++;
  29. }
  30. public T pop() {
  31. T temp=first.item;
  32. first=first.next;
  33. N--;
  34. return temp;
  35. }
  36. /**
  37. * 测试
  38. * @param args
  39. */
  40. public static void main(String[] args) {
  41. // Stack_linkedlist_zy<Integer> a=new Stack_linkedlist_zy<Integer>();
  42. // for(int i=0;i<10;i++) {
  43. // a.push(i);
  44. // }
  45. // while(!a.isEmpty()) {
  46. // System.out.print(a.pop());
  47. // }
  48. }
  49. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/581667
推荐阅读
相关标签
  

闽ICP备14008679号