4.1 栈及其Java实现

直接看代码(分析)
(1)定义栈的数据结构

package hello.java.data.datastructure;
  /**
  * 基于数组实现的顺序栈
  * param<E>
  */
  public class Static<E>{
    private Object[] data = null;
    private int maxSize = 0;   // 栈的容量
    private int top = -1;    // 栈顶的指针
    //构造函数:根据指定的size初始栈
    Stack(){
      this(10);  //默认的大小为10
    }
    Stack(int initialSize){
      if(initialSize >= 0){
        this.maxSize = initalSize;
        data = new Object[initalSize];
        top -= -1;
      } else {
        throw new RuntimeException("初始化大小不能小于0:"+initialSize);
      }
    }
}

以上代码定义了一个Stack类,用来存储栈的数据结构;定义了一个数组data,用来存储栈中的数据;定义了maxSize,表示栈的最大容量;定义了top,表示栈顶数据的指针;定义了两个栈
的构造函数,在构造函数没有参数时默认构造一个大小为10的栈.
(2)数据入栈,向栈顶压入一个数据:

//进栈:第一个元素top=0
public boolean push(E e){
    if(top == maxSize - 1){
      throw new RuntimeException("栈以满,无法将元素入栈！")；
    } else {
      data[++top] = e;
      return true;
    }
}

以上定义了方法push()来向栈中压入数据,在数据入栈前首先判断栈是否满了,具体的判断依据为栈顶元素的指针位置等于栈的最大容量。注意,这里使用maxSize -1是因为张顶元素的指针是从0开始
计算的。在栈有可用空间时,使用data[++top]=e在栈顶(top位置)上方压入一个元素将top加1.
(3)数据出栈,从栈顶移除一个数据

//弹出张顶元素
public E pop(){
   if(top == -1){
      throw new RuntimeException("栈为空!");
   } else {
      return (E)data[top--];
   }
}

以上代码定义了方法pop()来从栈顶移除一个数据,移除前先判断暂定是否有数据,如果有,则通过data[top--]将栈顶数据移除并将top减1.
(4)数据查询

//查询张顶元素但不移除
public E peek(){
   if(top == -1){
    throw new RuntimeException("栈为空!");
   } else {
     return (E)data[top];
   }
}

以上代码定义了方法peek()来取出栈顶的数据,在取出栈顶的数据前先判断栈顶的元素是否存在,如果存在,则直接返回栈顶元素(注意:这里没有对栈顶的元素进行删除)
否则抛出异常。