快捷導(dǎo)航

詳解Java中LinkedStack鏈棧的實(shí)現(xiàn)

更新時間：2022年11月14日 17:06:17 作者：第一天

這篇文章主要為大家詳細(xì)介紹了Java中LinkedStack鏈棧的相關(guān)知識，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Java有一定幫助，需要的可以參考一下

概念

棧:又稱為堆棧．是限制在表的一端進(jìn)行插入和刪除的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除操作，不允許在其他任何位置進(jìn)行插入、查找、刪除等操作。

表中進(jìn)行插入、刪除操作的一端稱為棧頂.棧頂保存的元素秘為棧項(xiàng)元素。想對的，表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時，稱為空棧;向一個棧中插入元素又稱為進(jìn)棧或入棧;從一個棧中刪除元素又稱為出?；蛲藯！?/p>

由于棧的插入和刪除操作都僅在棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把堆棧稱為后進(jìn)先出表。

鏈棧--用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧;其結(jié)構(gòu)特點(diǎn)與單鏈表的結(jié)構(gòu)相同，鏈?zhǔn)蕉褩Ｒ彩怯梢粋€個結(jié)點(diǎn)組成的，每個結(jié)點(diǎn)由兩個域組成，一個是存放數(shù)據(jù)元素的數(shù)據(jù)元素域，另一個是存放指向向下一個節(jié)點(diǎn)的對象的引用域;因?yàn)闂Ｖ兄饕窃跅ｍ斶M(jìn)行操作，所以在鏈表的頭部做棧頂是最方便的,而且不用添加頭結(jié)點(diǎn)。

具體內(nèi)容的解釋都寫在注釋里了

StackLnterface接口類

public interface StackLnterface0&lt;T&gt; {
    public interface StackInterface&lt;T&gt; {
        //在接口處聲明方法，在類內(nèi)進(jìn)行實(shí)現(xiàn)T
        public void push(T element);//用于表達(dá)進(jìn)棧的方法
        public  T pop();//用于表達(dá)出棧的方法
        public boolean isEmpty();//用于判斷棧是否為空的方法的方法
    }
}

LinkedStack接口實(shí)現(xiàn)

class LinkedNode<T>{
    private T data;//聲明data
    private LinkedNode<T> next;//聲明next
    public LinkedNode(T i){//定義有參構(gòu)造函數(shù)
        data = i;
        next = null;
    }
    public LinkedNode(){//定義無參構(gòu)造函數(shù)
        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> {    //通過重新實(shí)現(xiàn)多個接口
    protected LinkedNode<T> top;//聲明top指針

    public LinkedStack() {
        //棧的初始化，初始化一個空棧
        LinkedNode<T> first = new LinkedNode<T>();//定義一個空節(jié)點(diǎn)
        top = first;//把空節(jié)點(diǎn)放在最開頭
    }

    public void push(T element) {//用于表達(dá)進(jìn)棧的方法
        LinkedNode<T> s = new LinkedNode<T>(element);//用s來代表要輸入的元素
        s.setNext(top);//讓新進(jìn)入的元素指向它的上一位元素
        top = s;//top指針指到s上面
    }

    public T pop() {//用于表達(dá)出棧的方法
        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(){//用于表達(dá)展示當(dāng)前的指針指向元素的方法
        if(isEmpty())//先判斷是否空棧,如果是空棧就拋出異常
            throw new RuntimeException("棧空");
        T top_node = top.getData();//定義一個記錄top指針指向元素的變量
        return top_node;//返回top指向的元素
    }

    public void getLz() {//用于展示當(dāng)前鏈棧的方法
        LinkedNode<T> a = top;//定義此時的a代替top指針
        while (a.getNext()!=null){//當(dāng)a的引用域不為null時
            System.out.print(a.getData()+"\n");//輸出此時a的數(shù)據(jù)域
            a = a.getNext();//往下循環(huán)a讓元素一個一個輪流展示
        }
    }
}
 class ShiJian1{//實(shí)踐類
    public static void main(String[] args){
       LinkedStack<Integer> linked = new LinkedStack<Integer>();//實(shí)現(xiàn)T范型為int類型
        //輸入要加入鏈棧的元素
       linked.push(6);
       linked.push(7);
       linked.push(8);
       linked.push(9);
       linked.getLz();
       //進(jìn)行出棧操作
       System.out.println("進(jìn)行一次出棧操作，得到元素"+linked.pop());
       System.out.println("再進(jìn)行一次出棧操作，得到元素"+linked.pop());
       linked.getLz();
       System.out.println("此時的top指針指向元素為"+linked.getTop());

    }
}