基于数组和链表的栈实现

栈接口定义：

public interface Stack<Item> {

	/**
	 * 添加一个元素
	 * @param item
	 */
	public void push(Item item);
	
	/**
	 * 获取最后一个添加的元素，并将其从栈中删除
	 * @return
	 */
	public Item pop();
	
	/**
	 * 判断栈是否为空
	 * @return
	 */
	public boolean isEmpty();
	
	/**
	 * 获取栈当前的元素个数
	 * @return
	 */
	public int size();
}

基于数组的实现：

import java.util.Iterator;

import com.mycode.algorithms.stack.Stack;

/**
 * 基于数组的栈实现
 * @author imhuqiao
 */
public class ArrayStack<Item> implements Stack<Item>,Iterable<Item> {

	private Item[] data = null;
	private int pos = -1;
	
	public ArrayStack(){
		this(10);
	}
	
	public ArrayStack(int initLength){
		data = (Item[]) new Object[initLength];
	}
	
	@Override
	public void push(Item item) {
		pos++;
		if(pos==data.length){
			resize(data.length*2);
		}
		data[pos] = item;
		//print();
	}
	
	private void print(){
		System.out.print("[");
		for(Item d : data){
			System.out.print(d+",");
		}
		System.out.println("],pos="+pos);
	}

	@Override
	public Item pop() {
		if(isEmpty()){
			return null;
		}
		Item item = data[pos];
		data[pos] = null;
		pos--;
		if(pos > 0 && pos == data.length/4) resize(data.length/2);
		//print();
		return item;
	}

	@Override
	public boolean isEmpty() {
		return pos==-1;
	}

	@Override
	public int size() {
		return pos+1;
	}

	@Override
	public Iterator<Item> iterator() {
		return new ArrayStackIterator();
	}
	
	
	private void resize(int length){
		Item[] newdata = (Item[]) new Object[length];
		int i = 0;
		for(Item item : data){
			if(i<length){
				newdata[i] = data[i];
				data[i] = null;
			}
			i++;
		}
		data = newdata;
	}
	
	class ArrayStackIterator implements Iterator<Item>{
		private int i = pos;
		@Override
		public boolean hasNext() {
			return i>-1;
		}

		@Override
		public Item next() {
			Item result = data[i--];
			return result;
		}

		@Override
		public void remove() {
			
		}
	}
}

基于链表的实现：

import java.util.Iterator;

import com.mycode.algorithms.stack.Stack;

/**
 * 基于链表的栈实现
 * @param <Item>
 */
public class LinkStack<Item> implements Stack<Item>, Iterable<Item> {

	private Node<Item> head;
	private int count = 0;
	
	public LinkStack(){
		head = new Node<Item>();
	}
	
	
	@Override
	public Iterator<Item> iterator() {
		return new LinkStackIterator();
	}

	@Override
	public void push(Item item) {
		Node<Item> newNode = new Node<Item>();
		newNode.data = item;
		newNode.next = head;
		head = newNode;
		count++;
		print();
	}

	@Override
	public Item pop() {
		Item data = head.data;
		head = head.next;
		count--;
		print();
		return data;
	}

	@Override
	public boolean isEmpty() {
		return count == 0;
	}

	@Override
	public int size() {
		return count;
	}
	
	private void print(){
		Node<Item> node = head;
		System.out.print("[");
		while(node.next!=null){
			System.out.print(node.data+",");
			node = node.next;
		}
		System.out.println("]");
		
	}
	
	class Node<T>{
		public T data;
		public Node<T> next;
	}
	class LinkStackIterator implements Iterator<Item>{

		private Node<Item> theHead;
		private int theCount;
		
		public LinkStackIterator(){
			theHead =  new Node<Item>();
			theHead = head;
			theHead.next = head.next;
			this.theCount = count;
		}
		
		@Override
		public boolean hasNext() {
			return theCount>0;
		}

		@Override
		public Item next() {
			Item data = theHead.data;
			theHead = theHead.next;
			theCount--;
			return data;
		}

		@Override
		public void remove() {
			
		}
	}

}

测试代码：

	@Test
	public void testArrayStack(){
		Stack<String> as = new ArrayStack<String>(1);
		as.push("a");
		as.push("b");
		as.push("c");
		Assert.assertEquals("c",as.pop());
		String res = "";
		for(String str : as){
			res += str;
		}
		Assert.assertEquals("ba",res);
	}

	@Test
	public void testLinkStack(){
		Stack<String> ls = new LinkStack<String>();
		ls.push("a");
		ls.push("b");
		ls.push("c");
		Assert.assertEquals("c",ls.pop());
		String res = "";
		for(String str : ls){
			res += str;
		}
		Assert.assertEquals("ba",res);
	}