Java基础复习笔记05数据结构-栈

1.       栈

栈是一种比较特殊的线性表，它的原则就是先进后出，后进先出。你就把他想做一个你放书的大箱子，要想看放在最底层的书（压箱底的），那么得先拿出来上面的所有书之后那本最底层的书才能取到。同样栈也是这个意思。

 

2.       栈的操作

栈的操作比线性表的操作要少一些，这也可以看出来栈结构实际上就是在线性表的基础上加了一些不能进行的操作才叫做栈。栈的操作有：入栈、出栈、访问栈顶元素、清空栈。

3.       栈的使用场景

展示一个比较有用的结构，比如做语法分析、递归、支持撤消都可以使用栈来实现。

4.       栈的顺序实现

栈的顺序实现和线性表的顺序实现差不多，都是用一个数组来进行数据的存取。

如下

package dateStructer.stack;

/**
 * 栈的顺序实现
 * @author liuyan
 * @param <E>
 */
public class MyArrayStack<E> {

	// 临时数组
	private Object[] objects;

	// 默认临时数组的初始大小
	private final static int Def_Size = 16;

	// 记录实实在在的元素个数
	private int elementSize;

	public MyArrayStack() {
		objects = new Object[Def_Size];
	}

	/**
	 * 栈顶添加元素
	 * @param e
	 */
	public void push(E e) {

		if (elementSize == 0) {
			objects[0] = e;
			elementSize++;
			return;
		}

		for (int i = 0; i < objects.length; i++) {
			if (objects[i] == null) {
				objects[i] = e;
				elementSize++;
				break;
			}
		}

	}

	/**
	 * 从栈顶出元素,删除栈顶元素
	 * 
	 * @return
	 */
	public E pop() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}
		E lastElement = (E) objects[elementSize - 1];
		
		objects[elementSize - 1] = null;
		elementSize--;

		return lastElement;
	}

	/**
	 * 从栈顶出元素,不删除栈顶元素
	 * 
	 * @return
	 */
	public E peek() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		E lastElement = (E) objects[objects.length - 1];
		return lastElement;
	}

	/**
	 * 栈空间大小
	 * @return
	 */
	public int getSize() {
		return elementSize;
	}

	/**
	 * 栈是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return elementSize == 0;
	}
	
	/**
	 * 清空所有元素
	 */
	public void clear() {
		for (int i = 0; i < elementSize; i++) {
			objects[i] = 0;
		}
		elementSize = 0;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < elementSize; i++) {

			str.append("[" + objects[i].toString() + "],");

		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 5.       栈的链表实现

使用链表结构实现栈其实用一个栈顶临时标记记录着时刻变化的栈顶元素即可，算法如下

package dateStructer.stack;

public class MyLinkStack<E> {

	/**
	 * 单向链表结构
	 */
	public class LinkNode {

		// 真正的数据域
		private E date;

		// 记录下一个节点
		private LinkNode nextLinkNode;

		public LinkNode() {

		}

		public LinkNode(E date, LinkNode nextLinkNode) {
			this.date = date;
			this.nextLinkNode = nextLinkNode;
		}
	}

	// 结点个数
	private int elementSize;

	// 头结点
	private LinkNode topNode;

	public MyLinkStack() {
		topNode = new LinkNode();
	}

	/**
	 * 栈顶添加元素
	 * 
	 * @param e
	 */
	public void push(E e) {

		if (elementSize == 0) {
			if (topNode == null) {
				topNode = new LinkNode(e, null);
			} else {
				topNode.date = e;
			}
			elementSize++;
			return;
		}

		LinkNode linkNode = topNode;

		LinkNode linkNodeNewTop = new LinkNode(e, linkNode);

		topNode = linkNodeNewTop;
		elementSize++;
	}

	/**
	 * 从栈顶出元素,删除栈顶元素
	 * 
	 * @return
	 */
	public E pop() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		LinkNode linkNode = topNode;

		topNode = topNode.nextLinkNode;

		E date = linkNode.date;

		linkNode.date = null;
		linkNode.nextLinkNode = null;

		elementSize--;

		return date;
	}

	/**
	 * 从栈顶出元素,不删除栈顶元素
	 * 
	 * @return
	 */
	public E peek() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		E date = topNode.date;

		return date;
	}

	/**
	 * 栈空间大小
	 * 
	 * @return
	 */
	public int getSize() {
		return elementSize;
	}

	/**
	 * 栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return elementSize == 0;
	}

	/**
	 * 清空所有元素
	 */
	public void clear() {
		LinkNode linkNode = topNode;
		for (int i = 0; i < elementSize; i++) {
			linkNode.date = null;
			linkNode = linkNode.nextLinkNode;
		}

		elementSize = 0;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		LinkNode linkNode = topNode;

		for (int i = 0; i < elementSize; i++) {

			str.append("[" + linkNode.date.toString() + "],");
			linkNode = linkNode.nextLinkNode;
		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 测试代码同顺序栈的测试代码相同，在此就不在赘述。这里面利用了一个topNode变量来作为栈顶的标记，时刻改变、维护这个变量就可以轻易获取站定元素。

6.       利用现有JDK集合实现

其实我们可以使用Java现有的集合辅助类类轻易实现栈结构。

package dateStructer.stack;

import java.util.ArrayList;

public class MyStack<T> {

	ArrayList<T> list;

	public MyStack() {
		list = new ArrayList<T>();
	}

	/**
	 * 栈顶添加元素
	 * 
	 * @param e
	 */
	public void push(T e) {
		list.add(e);
	}

	/**
	 * 从栈顶出元素
	 * 
	 * @return
	 */
	public T pop() {

		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		T lastElement = list.get(list.size() - 1);
		list.remove(list.size() - 1);
		return lastElement;
	}

	/**
	 * 栈空间大小
	 * 
	 * @return
	 */
	public int getSize() {
		return list.size();
	}

	/**
	 * 栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return list.size() == 0;
	}
	
	public void clear(){
		list.clear();
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < list.size(); i++) {

			str.append("[" + list.get(i).toString() + "],");

		}

		if (list.size() > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 其实和数组的顺序实现也差不多，无非就是节省了自己维护数组操作的逻辑。

7.       总结

在此总结了栈的特点和实现方式。Java自己有一个栈的实现类就是java.util.Stack。显示开发中可以使用此类完成栈的操作。栈与队列经常是一起提到，下次我们复习复习队列，唉~~今天状态不是很好，先睡了！

评论

1 楼 spadesacn 2012-02-28  

纯讨论啊。
第一个数组实现的时候，其实找一个变量记录栈顶位置就好了，否则push是O（n),记录栈顶位置的push是O(1)，clear（）虽然不是基本ADT的内容，但是this.object[] = new object[capability]更快。数组实现最耗的是在enlarge storeage时候。