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

使用数组来实现栈的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());
//		}
	}
 
}