Java链表栈LinkedStack

Z时代
2024-01-10
分类：综合

java

作者: wangding263

链接：http://wangding263.javaeye.com/blog/254272

发表时间: 2008年10月17日

声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！

链表实现的栈，在想象栈的时候，最好把他竖着想象成一个立着的容器。

* 然后往里面一个一个的加节点：

* 1.先加入top节点

* 2.然后再在top节点上加入node1节点,node1节点指向top节点

* 3.再在node1节点上加入node2节点，node2节点指向node1节点

* ..........

Java实现链栈之前，我们首先应该创建一个链表节点类:LinkNode<E>,代码如下:

/**
 * 链表节点
 * 
 * @author 鼎鼎
 * 
 * @param <E>
 */
public class LinkNode<E> {
	/**
	 * 表示存储在节点中的数据项
	 */
	private E data;
	private LinkNode<E> next;
	public LinkNode(E data) {
		this.data = data;
		this.next = null;
	}
	public LinkNode(E data, LinkNode next) {
		this.data = data;
		this.next = next;
	}
	public E getData() {
		return data;
	}
	public void setData(E data) {
		this.data = data;
	}
	public LinkNode<E> getNext() {
		return next;
	}
	public void setNext(LinkNode<E> next) {
		this.next = next;
	}
}

然后是具体的链栈的实现,代码如下:

/**
 * 链表实现的栈，在想象栈的时候，最好把他竖着想象成一个立着的容器。
 * 然后往里面一个一个的加节点：
 * 1.先加入top节点
 * 2.然后再在top节点上加入node1节点,node1节点指向top节点
 * 3.再在node1节点上加入node2节点，node2节点指向node1节点
 * ..........
 * 
 * @author 鼎鼎
 *
 * @param <E>
 */
public class LinkedStack<E> implements Stack<E> {
	// 表示链表的头结点
	private LinkNode<E> top;
	// 表示链表中当前的元素个数
	private int size;
	public LinkedStack() {
		this.top = null;
		size = 0;
	}
	public boolean isEmpty() {
		return top == null;
	}
	public E pop() {
		if (isEmpty()) {
			throw new RuntimeException("链表为空!!");
		}
		// 将栈顶元素的值保存起来
		E tempData = top.getData();
		// 然后出栈，次栈顶元素成为新的栈顶元素
		top = top.getNext();
		// 栈中元素个数减少一
		size--;
		return tempData;
	}
	public void push(E target) {
		if(target==null){
			throw new RuntimeException("不能往栈中加入null元素");
		}
		LinkNode<E> newNode = new LinkNode<E>(target);
		if (isEmpty()) {
			top = newNode;
		} else {
			//新加入的节点放入栈中,并指向原来的top节点
			newNode.setNext(top);
			// 新加入的元素成为了新的栈顶
			top = newNode;
		}
		size++;
	}
	public int size() {
	   return size;
	}
	public E top() {
		if (isEmpty()) {
			throw new RuntimeException("链表为空!!");
		}
		return top.getData();
	}
}