前言

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

一、實現(xiàn)過程

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

1.提供棧接口：IStack

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

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

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

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

/**
 *
 * @author pcc
 * @version 1.0.0
 * @className ShunxuStack:這是一種順序棧，使用順序存儲結(jié)構(gòu)來實現(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)等計算方法

這些方法的實現(xiàn)都比較簡單，因此都一起寫出來了，判空方法，只需要判斷top指針是否是-1即可，因為只有空棧時，top指針的值才會指向-1，計算棧深度，使用top+1即可實現(xiàn)，因為top指針指向的是棧頂?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()

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

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

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

該方法用以獲取棧頂元素，但并不會對元素有其他任何操作。獲取棧頂元素的思路就是空棧返回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ù)入棧是順序棧的核心方法，該方法的實現(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即可實現(xiàn)棧的數(shù)據(jù)元素的出棧，不過這種實現(xiàn)其實并沒有真正刪除數(shù)組中的數(shù)據(jù)元素，只是通過top指針去將其隱藏了。當(dāng)然了也可以真正的去實現(xiàn)刪除棧頂?shù)臄?shù)據(jù)元素，直接置null即可。

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

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

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

/**
 *
 * @author pcc
 * @version 1.0.0
 * @className ShunxuStack:這是一種順序棧，使用順序存儲結(jié)構(gòu)來實現(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];
    }
}

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

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

1.測試入棧和出棧

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

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

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

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

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

三、總結(jié)

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

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

最新評論