分类： Java
2013-11-20 15:01:21
4.1本节学习目标
栈的数组实现
java.util.Stack讲解
4.1.1栈的数组实现
前面的教程中，我们一节学习了栈的基本特性，同时还使用了栈来求解一个问题(后缀表达式)，细心的读者可以发现，我们根本不知道栈是如何实现的，这节，我们将探讨栈的实现。
栈的实现有多种方式，本节将介绍上述两种实现方式。
①栈的数组实现的思路：
数组是一个对象引用的数组，其数据类型在栈实例化时确定，使用泛型。
栈底在数组的index(索引)为0处。
栈的元素是安顺序存储在数组中
有个top变量，这个top变量包含两个含义：数组元素的数目和下一个可添加元素的索引位置。
我们可以用个实例图来表示上述的这个实现：
底 0 1 2 3 4 5 6 7 8 ……
ABCDE
top 5
则表示：
栈底为索引位置0，
数组的大小为5 ，
下一个插入栈中的元素的索引位置为 5
程序关键部分有详细的注释。
②StackADT，是我们第二接里面的栈的抽象数据类型的定义：
如下：
public interface StackADT
③ArrayStack 实现StackADT接口
程序详解：
public class ArrayStack
/**标识数组默认容量的变量*/
private final int DEFAULT_CAPACITY = 100;
/**标识数组的元素数目及下一个可用位置(下一元素压入位置)*/
private int top;
/**标识栈的泛型元素数组*/
private T[] stack;
/**
* 使用默认容量创建一个空栈
* */
public ArrayStack() {
top = 0;
stack = (T[]) (new Object[DEFAULT_CAPACITY]);//实例化一个Object数组，然后转化为一个泛型数组
}
/**
* 使用指定容量创建一个空栈,参数initialCapacity标识的是指定的容量
* */
public ArrayStack(int initialCapacity) {
top = 0;
stack = (T[]) (new Object[initialCapacity]);
}
判断栈是否为空
public boolean isEmpty() {
if(size()==0) {
return true;
}else {
return false;
}
}
出栈操作，栈为空，则出栈失败
public T peek() {
if(isEmpty()){
System.out.println("栈为空，操作失败!");
throw new EmptyStackException();
}
return stack[top-1];
}
/**
* 数组实现的pop操作由以下几个步骤组成
* ①却保栈不为空
* ②计数器top--
* ③设置临时引用等于stack[top]的元素
* ④设置stack[top]为空
* ⑤返回该临时引用
* */
public T pop() {
if(isEmpty()) {
System.out.println("栈为空，出栈失败!");
throw new EmptyStackException();
}
top--;
T result = stack[top];//top为栈顶元素，数组从0开始
stack[top] = null;
return result;
}
/**
* 对于栈的数组的实现，其push操作由以下步骤构成
* ①确保该数组不是蛮的
* ②把数组的top引用设置为要加入到栈中的对象
* ③增加top和count的值
* */
public void push(T element) {
if(size()==stack.length) {
expandCapacity();
}
stack[top] = element;
top++;
}
/**
* 使数组的大小加倍。由于数组一旦实例化以后就不能改变其大小，
* 因此该方法是创建一个更大的数组，并把旧数组中的内容复制到新数组中
* 它是类的一个支持方法，因此可以实现为私有的
* */
private void expandCapacity() {
sducc1120
sducc1120
T[] larger = (T[]) new Object[stack.length*2];
for(int index = 0;index
larger[index] = stack[index];
stack = larger;
}
} 栈的大小，由变量top控制
public int size() {
return top; sducc1120
}
}
④ArrayStack.java
/** * @author 幽灵柯南 * 日期 2011.11.16 * 功能 用数组实现栈 * */ package
com.yaxing.stack; import java.util.EmptyStackException; public class
ArrayStack
⑤测试方法：
ArrayStack
⑥测试结果：
A、B、B、C、D、E、F、 栈的大小：7
