链栈的实现

使用链表作为栈的存储结构, 有时也称为链栈;

栈只允许在线性表的一端进行操作, 可以选择链表的头部作为栈顶;

不管是入栈/出栈都在链表的首结点上进行。

/**
 * 栈的链式存储
 * @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;
		}
		
	}
}