详解Java中LinkedStack链栈的实现

时间:2022-11-16 第一天人气:0

概念

栈:又称为堆栈．是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。

表中进行插入、删除操作的一端称为栈顶.栈顶保存的元素秘为栈项元素。想对的，表的另一端称为栈底。当栈中没有数据元素时，称为空栈;向一个栈中插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈。

由于栈的插入和删除操作都仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表。

链栈--用链式存储结构实现的栈称为链栈;其结构特点与单链表的结构相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域，另一个是存放指向向下一个节点的对象的引用域;因为栈中主要是在栈顶进行操作，所以在链表的头部做栈顶是最方便的,而且不用添加头结点。

具体内容的解释都写在注释里了

StackLnterface接口类

public interface StackLnterface0&lt;T&gt; {
    public interface StackInterface&lt;T&gt; {
        //在接口处声明方法，在类内进行实现T
        public void push(T element);//用于表达进栈的方法
        public  T pop();//用于表达出栈的方法
        public boolean isEmpty();//用于判断栈是否为空的方法的方法
    }
}

LinkedStack接口实现

class LinkedNode<T>{
    private T data;//声明data
    private LinkedNode<T> next;//声明next
    public LinkedNode(T i){//定义有参构造函数
        data = i;
        next = null;
    }
    public LinkedNode(){//定义无参构造函数
        data = null;
        next = null;
    }
    //data和next 的getter and setter
    public T getData(){
        return data;
    }
    public void setData(T element){
        data = element;
    }
    public LinkedNode<T>getNext(){
        return next;
    }
    public void setNext(LinkedNode<T>successor){
        next = successor;
    }
}

public class LinkedStack<T>  implements StackLnterface0<T> {    //通过重新实现多个接口
    protected LinkedNode<T> top;//声明top指针

    public LinkedStack() {
        //栈的初始化，初始化一个空栈
        LinkedNode<T> first = new LinkedNode<T>();//定义一个空节点
        top = first;//把空节点放在最开头
    }

    public void push(T element) {//用于表达进栈的方法
        LinkedNode<T> s = new LinkedNode<T>(element);//用s来代表要输入的元素
        s.setNext(top);//让新进入的元素指向它的上一位元素
        top = s;//top指针指到s上面
    }

    public T pop() {//用于表达出栈的方法
        if (isEmpty())//先判断是否空栈,如果是空栈就抛出异常
            throw new RuntimeException("栈空");
        T top_node = top.getData();//定义一个记录top指针指向元素的变量
        top = top.getNext();//出栈后top指针指向下一个要出栈位置的元素
        return top_node;//返回出栈时读取的元素
    }

    public boolean isEmpty() {//用于判断栈是否为空的方法的方法
        if (top == null)//如果top指针指向null的话
            return true;//说明栈空
        else
            return false;//否则就是栈非空
    }

    public T getTop(){//用于表达展示当前的指针指向元素的方法
        if(isEmpty())//先判断是否空栈,如果是空栈就抛出异常
            throw new RuntimeException("栈空");
        T top_node = top.getData();//定义一个记录top指针指向元素的变量
        return top_node;//返回top指向的元素
    }

    public void getLz() {//用于展示当前链栈的方法
        LinkedNode<T> a = top;//定义此时的a代替top指针
        while (a.getNext()!=null){//当a的引用域不为null时
            System.out.print(a.getData()+"\n");//输出此时a的数据域
            a = a.getNext();//往下循环a让元素一个一个轮流展示
        }
    }
}
 class ShiJian1{//实践类
    public static void main(String[] args){
       LinkedStack<Integer> linked = new LinkedStack<Integer>();//实现T范型为int类型
        //输入要加入链栈的元素
       linked.push(6);
       linked.push(7);
       linked.push(8);
       linked.push(9);
       linked.getLz();
       //进行出栈操作
       System.out.println("进行一次出栈操作，得到元素"+linked.pop());
       System.out.println("再进行一次出栈操作，得到元素"+linked.pop());
       linked.getLz();
       System.out.println("此时的top指针指向元素为"+linked.getTop());

    }
}

运行结果

加载全部内容