前言

線性表和棧都是我們常用的數(shù)據(jù)結(jié)構(gòu)，棧可以看成一種特殊狀態(tài)的線性表，棧的實(shí)現(xiàn)，一般都是使用線性表來(lái)實(shí)現(xiàn)，線性表分為順序表和鏈表，使用線性表中的順序表來(lái)實(shí)現(xiàn)棧時(shí)這種棧被稱為順序棧，相應(yīng)的使用線性表中的鏈表來(lái)實(shí)現(xiàn)棧時(shí)這種棧被稱為鏈棧，但是需要說(shuō)明的是，雖然棧是一種特殊的線性表，但是棧和線性表并不是一種數(shù)據(jù)結(jié)構(gòu)。這篇文章總結(jié)如何使用順序表實(shí)現(xiàn)棧，也就是順序棧的實(shí)現(xiàn)。

一、實(shí)現(xiàn)過(guò)程

這部分總結(jié)順序棧的實(shí)現(xiàn)過(guò)程，以及對(duì)應(yīng)方法實(shí)現(xiàn)思路，這里提供一個(gè)棧的頂層接口IStack,用以聲明棧中所應(yīng)實(shí)現(xiàn)的方法，提供該接口不僅可供順序棧使用，鏈棧也是可以使用的。下面順序棧的實(shí)現(xiàn)通過(guò)實(shí)現(xiàn)ISstack接口來(lái)完成，詳細(xì)步驟如下。

1.提供棧接口：IStack

該接口定義了棧必須實(shí)現(xiàn)的接口，有如下方法：

/**
 * 該接口是：棧的頂層接口
 * 他的實(shí)現(xiàn)類會(huì)有：順序棧、鏈棧
 *
 * 棧：先入后出
 */
public interface IStack {
    void clear();//清空方法
    boolean isEmpty();//判空方法
    int length();//棧深度方法
    Object peek();//取棧頂元素并返回值，若棧為空，返回null
    void push(Object object) throws Exception;//入棧操作,元素進(jìn)入棧頂
    Object pop();//將棧頂元素出站
}

2.提供順序棧的實(shí)現(xiàn)：ShunxuStack

提供一個(gè)順序棧的實(shí)現(xiàn)類ShunxuStack，順序棧我們需要使用數(shù)組來(lái)實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)，因此提供數(shù)組類型的實(shí)例變量來(lái)存儲(chǔ)棧元素：Object[] object,此外棧是一種先入后出的數(shù)據(jù)結(jié)構(gòu)，因此我們只需要將數(shù)組的插入進(jìn)行倒敘輸出就是正常的出棧順序了，但是我們每次想要插入或者出棧都去遍歷一遍數(shù)組然后判斷插入和刪除的位置，無(wú)疑是一種很耗費(fèi)時(shí)間的操作，因此我們提供一個(gè)指針，用以指向當(dāng)前棧頂元素所在的位置，當(dāng)空棧時(shí)，我們將該指針指向-1，然后每增加一個(gè)元素該指針就加1，每減一個(gè)元素該指針就減1，這樣我們就可以準(zhǔn)確知道棧頂?shù)脑亓恕?/p>

/**
 *
 * @author pcc
 * @version 1.0.0
 * @className ShunxuStack:這是一種順序棧，使用順序存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的棧
 * @date 2021-04-20 16:08
 */
public class ShunxuStack implements IStack {

    Object[] objArray;
    int top = -1;//指向棧頂元素所在下標(biāo)
    public ShunxuStack(int i){
    objArray = new Object[i];
    }
}

3.提供判空(isEmpty)、棧深度(length)等計(jì)算方法

這些方法的實(shí)現(xiàn)都比較簡(jiǎn)單，因此都一起寫(xiě)出來(lái)了，判空方法，只需要判斷top指針是否是-1即可，因?yàn)橹挥锌諚r(shí)，top指針的值才會(huì)指向-1，計(jì)算棧深度，使用top+1即可實(shí)現(xiàn)，因?yàn)閠op指針指向的是棧頂?shù)臄?shù)據(jù)元素的下標(biāo)，所以+1就是棧的數(shù)據(jù)元素的多少。

    @Override
    public boolean isEmpty() {
        return top == -1?true:false;
    }

    @Override
    public int length() {
        return top+1;
    }

4.提供清空棧的方法：clear()

這里的清空方法的實(shí)現(xiàn)是通過(guò)lamdba表達(dá)式拿到數(shù)組里面的所有元素，然后將所有元素都置null來(lái)完成的，值得說(shuō)的是ArrayList的clear方法也是使用的這種方式來(lái)作清空操作的。這種清空操作更有利于jvm對(duì)垃圾的回收。若是只將數(shù)組作置null操作，其實(shí)數(shù)組中的對(duì)象還是有引用鏈和數(shù)組的內(nèi)存相連，這樣會(huì)增加垃圾回收時(shí)的判斷，所以最正確的操作還是將每個(gè)元素都置null，代碼如下：

    @Override
    public void clear() {
        Arrays.stream(objArray).forEach(obj ->obj=null);
        top = -1;
    }

5.提供獲取棧頂元素方法：peek()

該方法用以獲取棧頂元素，但并不會(huì)對(duì)元素有其他任何操作。獲取棧頂元素的思路就是空棧返回null，不是空棧就返回top為下標(biāo)的數(shù)據(jù)元素即可（top指向棧頂數(shù)據(jù)元素）。

    @Override
    public Object peek() {
        if(isEmpty())
            return null;
        return objArray[top];
    }

6.提供數(shù)據(jù)入棧方法：push(Object object)

數(shù)據(jù)入棧是順序棧的核心方法，該方法的實(shí)現(xiàn)思路：top初始狀態(tài)為-1，因此我們需要先將top+1得到棧頂元素需要存放的下標(biāo)，第二步直接將元素根據(jù)下標(biāo)放入 數(shù)組即可。

    @Override
    public void push(Object object) throws Exception{
        if(top>=objArray.length-1)
            throw new Exception("StackOverFlowError");
        top++;
        objArray[top] = object;
    }

7.提供數(shù)據(jù)元素出棧方法：pop()

棧是一種先入后出的數(shù)據(jù)結(jié)構(gòu)，最先出棧的只能是棧頂?shù)臄?shù)據(jù)元素，因此我們只需要將指向棧頂數(shù)據(jù)元素的top，減1即可實(shí)現(xiàn)棧的數(shù)據(jù)元素的出棧，不過(guò)這種實(shí)現(xiàn)其實(shí)并沒(méi)有真正刪除數(shù)組中的數(shù)據(jù)元素，只是通過(guò)top指針去將其隱藏了。當(dāng)然了也可以真正的去實(shí)現(xiàn)刪除棧頂?shù)臄?shù)據(jù)元素，直接置null即可。

    @Override
    public Object pop() {
        if(isEmpty())
            return null;
        top--;
        return objArray[top+1];
    }

8.提供順序棧實(shí)現(xiàn)的完整代碼

到這里順序棧的所有方法都全部實(shí)現(xiàn)了，可以看到其實(shí)無(wú)論是思路還是代碼棧都是一種很簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，也是很容易掌握的一種數(shù)據(jù)結(jié)構(gòu)。下面展示下完整的棧方法實(shí)現(xiàn)的完整代碼。

/**
 *
 * @author pcc
 * @version 1.0.0
 * @className ShunxuStack:這是一種順序棧，使用順序存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的棧
 * @date 2021-04-20 16:08
 */
public class ShunxuStack implements IStack {

    Object[] objArray;
    int top = -1;//指向棧頂元素所在下標(biāo)

    public ShunxuStack(int i){
        objArray = new Object[i];
    }

    @Override
    public void clear() {
        Arrays.stream(objArray).forEach(obj ->obj=null);
        top = -1;
    }

    @Override
    public boolean isEmpty() {
        return top == -1?true:false;
    }

    @Override
    public int length() {
        return top+1;
    }

    @Override
    public Object peek() {
        if(isEmpty())
            return null;
        return objArray[top];
    }

    @Override
    public void push(Object object) throws Exception{
        if(top>=objArray.length-1)
            throw new Exception("StackOverFlowError");
        top++;
        objArray[top] = object;
    }

    @Override
    public Object pop() {
        if(isEmpty())
            return null;
        top--;
        return objArray[top+1];
    }
}

二、測(cè)試順序棧的相應(yīng)方法

第一部分已經(jīng)詳細(xì)描述了順序棧的實(shí)現(xiàn)過(guò)程，下面就來(lái)測(cè)試下這些方法是否可以正常使用吧。

1.測(cè)試入棧和出棧

創(chuàng)建一個(gè)測(cè)試類，然后往棧中插入五個(gè)數(shù)據(jù)元素，并依次出棧，若是出棧順序和入棧順序相反則說(shuō)明是正確的了，測(cè)試結(jié)果如下圖。

從結(jié)果可以看出，出棧順序是正常的了，也達(dá)到了先進(jìn)后出的要求了，同時(shí)也驗(yàn)證了isEmpty方法也是正常的。

2.驗(yàn)證獲取棧頂元素方法peek、棧深度方法length、清空方法clear

還是往棧里面放入原先的五個(gè)元素，然后棧頂元素應(yīng)該是“李四5”，長(zhǎng)度應(yīng)該是5，第二次長(zhǎng)度應(yīng)該是0，如果輸出內(nèi)容是這些說(shuō)明棧的實(shí)現(xiàn)就沒(méi)有問(wèn)題了，結(jié)果見(jiàn)下圖：

從上面的輸出結(jié)果可以看到，順序棧的各個(gè)方法實(shí)現(xiàn)均沒(méi)有問(wèn)題。

三、總結(jié)

棧這種數(shù)據(jù)結(jié)構(gòu)有很多的應(yīng)用場(chǎng)景，比如虛擬機(jī)棧等，當(dāng)然可能各種棧的實(shí)現(xiàn)語(yǔ)言不同，但是思想都是一樣的，他們的數(shù)據(jù)結(jié)構(gòu)并沒(méi)有區(qū)別，這篇文章是使用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的順序棧，這種棧我們可以將他看成一種特殊的順序表（或者叫線性表也可以）—只能在一端進(jìn)行插入和刪除的順序表。我們知道順序表的結(jié)構(gòu)特點(diǎn)是查詢快、插入(任意位置插入)和刪除的時(shí)間復(fù)雜度是O(n),是很慢的，那么順序表實(shí)現(xiàn)的順序棧呢？因?yàn)轫樞驐６际窃陬^部插入刪除，且沒(méi)有遍歷的場(chǎng)景，所以順序表實(shí)現(xiàn)的順序棧的插入和刪除的時(shí)間復(fù)雜度都是O(1),所以順序棧無(wú)論是插入和刪除都很快。

到此這篇關(guān)于Java實(shí)現(xiàn)順序棧的示例代碼的文章就介紹到這了,更多相關(guān)Java順序棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論