Java数据结构（二）

Java数据结构（二）

——栈

栈是一种特殊的线性表。栈的数据元素以及数据元素的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而栈只允许在固定一段进行插入和删除操作。栈中允许进行插入和删除操作的一段称为栈顶，另一端称为栈底。栈的插入操作通常我们都成为进栈或入栈~~而删除操作通常称为出栈或退栈。

根据栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是当前栈顶元素，这样，最后进入栈的数据元素总是最先退出栈，因此栈也被称为后进后出表。

顺序栈

 

package pzw.Stack;
/**
 * 使用顺序存储结构实现的堆栈
 * @author pzw
 *
 */
public class SeqStack implements Stack{

    final int defaultSize = 10;//默认构造函数的堆栈的大小
    int top;//栈顶位置
    Object[] stack;//数组对象
    int maxStackSize;//该堆栈最大元素个数
    //无参构造函数
    public SeqStack(){
        initiate(defaultSize);
    }
    //构造函数
    public SeqStack(int size){
        initiate(size);
    }
    //初始化堆栈
    private void initiate(int sz){
        maxStackSize = sz;
        top = 0;
        stack = new Object[sz];
    }

    public void push(Object elm) throws Exception {
        if(top == maxStackSize){
            throw new Exception("该堆栈已满");
        }
        stack[top] = elm;//保存元素
        top++;
    }

    public Object pop() throws Exception {
        if(top == 0){
            throw new Exception("该堆栈已空");
        }
        top--;
        return stack[top];
    }

    public Object getTop() throws Exception {
        if(top == 0){
            throw new Exception("该堆栈已空");
        }
        return stack[top-1];
    }

    public boolean notEmpty() {
        // TODO Auto-generated method stub
        return top > 0;
    }

}

 

链式栈

 

package pzw.Stack;
/**
 * 链式存储结构堆栈的实现
 * @author PZW
 *
 */
public class LinStack implements Stack{
    public Node top;//栈顶结点
    public int size;//结点个数

    //构造函数
    public LinStack(){
        top = null;
        size = 0;
    }

    public void push(Object elm) throws Exception {
        top = new Node(elm,top);
        size++;
    }

    public Object pop() throws Exception {
        if(size == 0){
            throw new Exception("该堆栈已空");
        }
        Object elm = top.elm;
        top = top.next;
        size--;
        return elm;
    }

    public Object getTop() throws Exception {
        if(size == 0){
            throw new Exception("该堆栈已空");
        }

        return top.elm;
    }

    @Override
    public boolean notEmpty() {
        // TODO Auto-generated method stub
        return size > 0;
    }

}