赞
踩
使用数组来实现栈的ADT。
实现栈的自动扩容和迭代。
-
- import java.util.Iterator;
-
- /**
- *
- *
- *实现迭代和包含动态扩容和缩减空间的栈
- *实现消除弹栈游离
- * @param <Item>
- */
- public class Stack_array_zy<Item> implements Iterable<Item> {
- private Item[] aItems=(Item[]) new Object[1];//使用object【】接收
- //private Item[] aItems=(Item[]) new Item[1];理论上应该这样写,但是Java中是不允许创建泛型数组的。
- //所以只好通过object进行类型转换
-
- private int item_num=0;
-
- public boolean isEmpty() {
- return item_num==0;
- }
-
- public int size() {
- return item_num;
- }
- /**
- *
- * @param max
- * 更改容量的策略在栈中主要使用在入栈时候扩容 弹栈时候减缩
- */
- private void resize(int max) {
- Item[] expand=(Item[]) new Object[max];
- for(int i=0;i<item_num;i++) {
- expand[i]=aItems[i];
- }
- aItems=expand;
- }
- public void push(Item a) {
- if (item_num==aItems.length) {
- resize(2*aItems.length);
- }
- aItems[item_num++]=a;
-
- }
- public Item pop() {
- Item a=aItems[--item_num];
- aItems[item_num]=null;//避免对象的游离
- if (item_num<=aItems.length/4) {
- resize(aItems.length/2);
- }
- return a;
-
-
- }
- /**
- *
- */
- public Iterator<Item> iterator(){
-
- return new getIterable();
-
- }
-
- /**
- *
- * @author zongyun
- *通过继承iterator类,通过实例化从而产生一个iterator对象。
- */
- private class getIterable implements Iterator<Item>{
- private int i=item_num;//嵌套类可以访问包含类的变量。
- public boolean hasNext() {
- return i>0;
-
- }
- public void remove() {
-
- }
-
- public Item next() {
- return aItems[--i];
- }
- }
- //测试
- public static void main(String[] args) {
- // Stack_array_zy<Integer> a=new Stack_array_zy<Integer>();
- // for(int i=0;i<10;i++) {
- // a.push(i);
- // }
- // System.out.println(a.isEmpty());
- // System.out.println(a.size());
- // for(int s:a) {
- // System.out.print(s);
- // }
- // while(!a.isEmpty()) {
- // System.out.print(a.pop());
- // }
-
- }
- }
-
-
1.对于数组的实现方式,注意扩容策略的选择。我选择扩容增加一半,而缩减时,避免空间浪费,当前元素小于数组容量1/4时缩减一半,以达到栈中已有元素一半以内的适宜容量。
2.对于出栈后,栈中的变量仍然保留,通过赋null,实现对“游离”的消除。
链表实现代码
- /**
- *
- * @author --
- *
- * @param <T>
- */
- public class Stack_linkedlist_zy<T> {
- private Node first;
- private int N;
- private class Node{
- T item;
- Node next;
- }
- public boolean isEmpty() {
- if (first.next==null) {
- return true;
- }
- else return false;
-
- }
- public int size() {
- return N;
- }
- public void push(T a) {
- Node new_first=new Node();
- new_first.item=a;
- new_first.next=first;
- first=new_first;
- N++;
- }
- public T pop() {
- T temp=first.item;
- first=first.next;
- N--;
- return temp;
- }
- /**
- * 测试
- * @param args
- */
- public static void main(String[] args) {
- // Stack_linkedlist_zy<Integer> a=new Stack_linkedlist_zy<Integer>();
- // for(int i=0;i<10;i++) {
- // a.push(i);
- // }
- // while(!a.isEmpty()) {
- // System.out.print(a.pop());
- // }
- }
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。