順序棧的實現

順序棧可以通過數組存儲堆棧的元素

堆棧的操作都 在棧頂完成, 選擇數組中索引值較大的一端作為棧頂

/**
 * 堆棧的順序實現
 * @author 北京動力節點老崔
 */
public class MyArrayStack implements MyStack {
	private Object[] elements;		//定義數組保存堆棧的元素
	private static final int DEFAULT_CAPACITY = 16; 	//堆棧的默認容量
	private int top; 			//棧頂指針

	//在無參構造中,對數組默認初始化
	public MyArrayStack() {
		elements = new Object[DEFAULT_CAPACITY];
	}
	//在構造方法中,指定堆棧的初始化大小
	public MyArrayStack(int initialCapacity) {
		elements = new Object[initialCapacity];
	}

	// 返回元素的個數
	@Override
	public int getSize() {
		return top;
	}

	// 判斷堆棧是否為空
	@Override
	public boolean isEmpty() {
		return top <= 0;
	}

	//入棧/壓棧
	@Override
	public void push(Object e) {
		//判斷堆棧是否已滿 ,如果堆棧已滿 , 數組需要擴容
		if ( top >= elements.length ) {
			//定義一個更大的數組, 默認按2倍大小擴容
			Object[] newData = new Object[elements.length * 2];
			//把原來的數組的內容復制到大的數組中
			for( int i = 0 ;  i<elements.length; i++) {
				newData[i] = elements[i];
			}
			//讓原來的數組名指向新的數組
			elements = newData;
		}
		
		//把元素存儲到棧頂指針指向的位置
		elements[top] = e;
		//棧頂指針上移
		top++;
	}

	// 出棧
	@Override
	public Object pop() {
		//判斷堆棧是否為空
		if (top <= 0 ) {
			throw new StackOverflowError("棧已空");
		}
		
		top--; 		//棧頂指針下移
		return elements[top];
	}

	// 返回棧頂元素, 不刪除
	@Override
	public Object peek() {
		// 判斷堆棧是否為空
		if (top <= 0) {
			throw new StackOverflowError("棧已空");
		}
		return elements[top-1];
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		// 從棧頂到棧底的順序添加各個元素
		for( int i = top-1 ; i>=0; i--) {
			sb.append(elements[i]);
			//元素之間使用逗號分隔
			if ( i > 0 ) {
				sb.append(",");
			}
		}
		sb.append("]");
		return sb.toString();
	}
}