Stack （堆栈）使用JAVA实现

代码如下：

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.RandomAccess;

public class Stack<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

	private static final long serialVersionUID = 1L;

	private Object[] elementData; 
	
	private int size;
	
	private int length;
	
	public Stack(int length) {
		this.length = length;
		elementData = new Object[this.length];
	}
	
	public Stack() {
		this(10);
	}

	private void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException(
					"Index: "+index+", Size: "+size);
		}
	}
	
	
	public void ensureCapacity(int minCapacity) {
		int oldCapacity = elementData.length;
		if (minCapacity > oldCapacity) {
			int newCapacity = (oldCapacity * 3)/2 +1;
			if (newCapacity < minCapacity) {
				newCapacity = minCapacity;
				elementData = Arrays.copyOf(elementData, newCapacity);
			}
		}
		
	}
	
	public boolean push(E e) {
		ensureCapacity(size + 1);
		elementData[size++] = e;
		return true;
	}
	
	public E pop() {
		rangeCheck(size - 1);
		E result = (E)elementData[--size];
		elementData[size] = null;
		return result;
	}
	
	public boolean isEmpty() {
		return elementData == null || size == 0;
	}
	
	public E top() {
		rangeCheck(size - 1);
		return (E)elementData[size - 1];
	}
	
	@Override
	public E get(int index) {
		throw new UnsupportedOperationException("can not get");
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	protected Object clone() throws CloneNotSupportedException {
		return super.clone();
	}

	@Override
	public Iterator<E> iterator() {
		return new stackIterator();
	}
	
	private class stackIterator implements Iterator<E> {

		@Override
		public boolean hasNext() {
			return size > 0;
		}

		@Override
		public E next() {
			return (E)elementData[--size];
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException("can not get");
		}
	}
}

 逻辑不复杂，小技巧是：重写 public Iterator<E> iterator() 方法。

  测试类如下：

public class StackTest {

	public static void main(String[] args) {
		Stack<Integer> st = new Stack<Integer>();
		for (int i = 0; i < 10; i++) {
			st.push(i);
		}
		
		
		for (int i = 0; i < 10; i++) {
			Integer val = st.pop();
			//Integer val = st.top();
			System.out.print(val);
			System.out.print('\t');
		}
		
		
		for (Integer val : st) {
			System.out.print(val);
			System.out.print('\t');
		}
		
	}

}

 

评论

2 楼 bo_hai 2013-12-30  

string2020 写道

public boolean push(E e) { 
        ensureCapacity(size + 1); 
        elementData[size++] = e; 
        return true; 
}
这个要返回对象本身吧

如

public E push(E e) { 
        ensureCapacity(size + 1); 
        elementData[size++] = e; 
        return this; 
}


元芳，你怎么看。

元芳的看法是：在push时，就知道对象本身，所以不需要返回对象本身。需要知道的是：push是否成功，返回true表示成功。大人，你怎么看？

1 楼 string2020 2013-12-29  

public boolean push(E e) { 
        ensureCapacity(size + 1); 
        elementData[size++] = e; 
        return true; 
}
这个要返回对象本身吧

如

public E push(E e) { 
        ensureCapacity(size + 1); 
        elementData[size++] = e; 
        return this; 
}


元芳，你怎么看。