数据结构——ArrayStack和LinkedStack的实现

栈是一种后进先出(LIFO)的数据结构。ArrayStack使用数组来实现，LinkedStack使用链表来实现，各有特点，也都非常简单。可以说这两个版本就是SimpleArrayList和SimpleLinkedList的简化版。

ArrayStack

import java.util.NoSuchElementException;

public class ArrayStack<T> {
	private static int DEFAULT_CAPACITY = 64; 
	private T[] elements;
	
	/**
	 * 栈顶索引
	 */
	private int top = -1;
	
	public ArrayStack(){
		this(DEFAULT_CAPACITY);
	}
	
	public ArrayStack(int capacity){
		ensureCapacity(capacity);
	}
	
	public int size(){
		return top+1;
	}
	
	public boolean isEmpty(){
		return top == -1;
	}
	
	/**
	 * 入栈
	 * @param ele
	 */
	public void push(T ele){
		/* 如果栈容量已经满了，则扩展栈大小 */
		if(size() == elements.length)
			ensureCapacity(2 * size() + 1);
		/* 将元素添加到栈顶,并修改栈顶索引 */
		elements[++top] = ele;
	}
	
	/**
	 * 出栈
	 * @return
	 * @throws NoSuchElementException
	 */
	public T pop() throws NoSuchElementException{
		/* 如果为空栈，则抛出异常 */
		if(isEmpty())
			throw new NoSuchElementException("Stack is empty.");
		/* 返回栈顶元素,并修改栈顶位置 */
		return elements[top--];
	}
	
	/**
	 * 重置栈容量大小,可用于扩展栈容量大小
	 * @param newCapacity
	 */
	@SuppressWarnings("unchecked")
	private void ensureCapacity(int newCapacity){
		if(newCapacity < size())
			return;
		
		T[] old = elements;
		elements = (T[]) new Object[newCapacity];
		for(int i=0; i < size(); i++){
			elements[i] = old[i];
		}
	}

	@Override
	public String toString() {
		return "top = " + top + " size = " + size();
	}
	
}

LinkedStack

import java.util.NoSuchElementException;

public class LinkedStack<T> {
	private Node<T> head;
	private int size = 0;
	
	public LinkedStack(){
		head = new Node<T>(null, null);
	}
	
	public int size(){
		return size;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	/**
	 * 入栈操作
	 * @param ele
	 */
	public void push(T ele){
		Node<T> newNode = new Node<T>(ele, head.next);
		head.next = newNode;
		size++;
	}
	
	/**
	 * 出栈操作，弹出栈顶元素
	 * @return 返回栈顶元素值
	 * @throws NoSuchElementException
	 */
	public T pop() throws NoSuchElementException{
		if(isEmpty())
			throw new NoSuchElementException("Stack is empty.");
		
		T popElement = head.next.data;
		head.next = head.next.next;
		size--;
		return popElement;
	}
	
	@Override
	public String toString() {
		return "size = " + size();
	}

	private static class Node<T>{
		public T data;
		public Node<T> next;
		
		public Node(T data, Node<T> next){
			this.data = data;
			this.next = next;
		}
	}
}