鏈棧的實現

使用鏈表作為棧的存儲結構, 有時也稱為鏈棧;

棧只允許在線性表的一端進行操作, 可以選擇鏈表的頭部作為棧頂;

不管是入棧/出棧都在鏈表的首結點上進行。

/**
 * 棧的鏈式存儲
 * @author 北京動力節點老崔
 */
public class MyLinkStack implements MyStack {
	private Node top; 			//存儲棧頂的引用
	private int size; 			//保存堆棧中元素的個數
	
	// 返回堆棧元素的個數
	@Override
	public int getSize() {
		return size;
	}

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

	// 入棧操作
	@Override
	public void push(Object e) {
		//根據元素生成結點,插入到鏈表的頭部
		Node pNode = new Node(e, top);
		//修改top棧頂指針指向新的結點
		top = pNode;
		size++;
	}

	// 出棧
	@Override
	public Object pop() {
		//先判斷堆棧是否為空
		if (size < 1 ) {
			throw new StackOverflowError("棧已空");
		}
		Object oldData = top.data; 		//保存原來棧頂元素
		top = top.next; 		//棧頂指針后移
		size--;
		return oldData;
	}

	// 返回棧頂元素
	@Override
	public Object peek() {
		// 先判斷堆棧是否為空
		if (size < 1) {
			throw new StackOverflowError("棧已空");
		}
		return top.data;
	}
	
	@Override
	public String toString() {
		// 把鏈表中各個結點的數據給返回
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for( Node pNode = top; pNode!=null; pNode= pNode.next) {
			sb.append(pNode.data);
			//數據元素之間使用逗號分隔
			if ( pNode.next != null) {
				sb.append(",");
			}
		}
		sb.append("]");
		return sb.toString();
	}

	//定義一個內部類,描述 鏈表中的結點
	private class Node{
		Object data; 		//存儲數據
		Node next;			//存儲下個結點的引用
		public Node(Object data, Node next) {
			super();
			this.data = data;
			this.next = next;
		}
		
	}
}