（数据结构与算法分析 三）------栈的实现（包括链栈和数组实现栈 Java语言描述）

对于栈，这个数据结构据说现在现代计算机已经作为一个基本的数据结构，而且已经作为指令系统的一部分了，可见栈的重要性，以前我对链栈情有独钟，总觉得他永远不会出现栈满，而且实现起来比链栈复杂，很有成就感，但是今天看完算法分析这本书的栈的这一章才了解到，其实作为平常的使用，数组实现的栈才是最常用的，因为他的查询和入栈与出栈都是一个时间单位就能完成的，而且速度惊人完全可以忽略不计，他的唯一缺点就是需要指定最大的空间，但是一班的程序没必要这个栈做的太大，也就是一个短小的精悍的数据结构，所以这个最大数组长度也就不是什么问题了，我现在对数组实现栈又有了新的看法，他的结构简单通俗易懂，真的还不错，以后实现栈我就首先选择数组实现了。

下面废话少说，上代码，首先还是作为较为复杂的链栈的实现摆在前面

package com.bird.three;

/**
 * @category 该类为链表的节点类，存储指针和数据
 * @author Bird
 *
 */
public class ListNode {//具有包友好访问权限
	Object element;
	ListNode next;
	
	ListNode(Object theElement){
		this(theElement,null);
	}
	
	ListNode(Object theElement, ListNode n){
		element = theElement;
		next = n;
	}
}

package com.bird.three;

/**
 * @category 栈的链表实现
 * @author Bird
 *
 */
public class StackList {
	private ListNode topOfStack;
	
	public StackList(){
		topOfStack = null;
	}
	
	public boolean isEmpty(){
		return topOfStack==null;
	}
	
	public void makeEmpty(){
		topOfStack = null;
	}
	
	public void push(Object x){//入栈操作
		topOfStack = new ListNode(x,topOfStack);//先创建X然后x的next指针指向topOfStack,然后返回给topOfStack
	}
	
	public Object peek(){//察看栈顶元素，不弹出
		if(isEmpty())
			return null;
		return topOfStack.element;
	}
	
	public Object pop(){//弹出栈顶元素，并作为对象返回
		if(isEmpty())
			return null;
		Object topItem = topOfStack.element;
		topOfStack = topOfStack.next;
		return topItem;
	}
	
	
}

下面才是数组的实现，一定好好看看哦

package com.bird.three;

/**
 * @category 栈的数组实现
 * @author Bird
 *
 */
public class StackArray {
	
	private Object [] theArray;
	private int topOfStack;
	private static final int DEFAULT_CAPACITY = 10;//栈的数组默认大小
	
	public StackArray(){
		this(DEFAULT_CAPACITY);
	}
	
	public StackArray(int capacity){
		theArray = new Object[capacity];
		topOfStack = -1;
	}
	
	public boolean isEmpty(){
		return topOfStack==-1;
	}
	
	public boolean isFull(){
		return topOfStack==theArray.length-1;
	}
	
	public void push(Object x){//入栈操作
		if(isFull())
			throw new RuntimeException("栈满");
		theArray[topOfStack++] = x;
	}
	
	public Object peek(){//查看栈顶元素
		if(isEmpty())
			return null;
		return theArray[topOfStack];
	}
	
	public Object pop(){//弹出栈的顶元素
		if(isEmpty())
			return null;
		Object topItem = theArray[topOfStack];
		theArray[topOfStack--]=null;
		return topItem;
	}
}