快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)之棧的線性結(jié)構(gòu)詳解

更新時間：2021年08月05日 11:01:58 作者：Cbw

從數(shù)據(jù)結(jié)構(gòu)上看棧和隊列都是線性表,不過是兩種特殊的線性表,棧只允許在的一端進行插人或刪除操作,而隊列只允許在表的一端進行插人操作、而在另一端進行刪除操作,這篇文章主要給大家介紹了關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之棧的線性結(jié)構(gòu)的相關(guān)資料,需要的朋友可以參考下

一：棧

棧是限制插入和刪除只能在一個位置上進行的表，此位置就是表的末端，叫作棧頂。

棧的基本操作分為push(入棧) 和 pop(出棧),前者相當于插入元素到表的末端（棧頂），后者相當于刪除棧頂?shù)脑亍?/p>

二：棧的實現(xiàn)

public class LinearStack {
    /**
     * 棧的初始默認大小為10
     */
    private int size = 5;
    /**
     * 指向棧頂?shù)臄?shù)組下標
     */
    int top = -1;
    /**
     * 定義棧stack
     */
    private int[] stack;
    public LinearStack() {
        stack = new int[size];
    }
    /**
     * 判斷棧滿
     */
    public  boolean isFull() {
        boolean result = false;
        if(top == size - 1) {
            result = true;
        }
        return result;
    }
    /**
     * 入棧操作push
     */
    public  void push(int value) {
        /**
         * 如果棧滿，拓展棧的容量
         */
        if(isFull())
            stack = expansionStack();
        top++;
        stack[top] = value;
    }
    /**
     * 出棧操作
     */
    public  int  pop() {
        if(top == -1)
            throw new RuntimeException("棧空！出棧失敗");
        int result = stack[top] ;
        top--;
        return result;
    }
    /**
     * 擴充容量
     */
    public  int[] expansionStack() {
        size = size + 10;
        int[] stackTemp = new int[size];
        for (int i = 0; i < stack.length; i++) {
            stackTemp[i] = stack[i];
        }
        return stackTemp;
    }
    /**
     * 獲取棧頂?shù)脑?
     */
    public int getTop() {
        return stack[top];
    }
    /**
     * 顯示棧中的全部元素
     */
    public  String toString() {
        String str = "[";
        for (int i = 0; i <= top; i++) {
            if(i == top)
                str = str + stack[i] + "]";
            else
                str = str + stack[i] + ",";
        }
        return str;
    }
}

三：棧的測試

public class LinearStackTest {

    public static void main(String[] args) {
        LinearStack linearStack = new LinearStack();
        /**
         * 元素入棧
         */
        linearStack.push(1);
        linearStack.push(2);
        linearStack.push(3);
        linearStack.push(4);
        linearStack.push(5);
        /**
         * 棧滿，顯示棧中所有元素
         */
        System.out.println("0：arrayStack  " + linearStack.toString());
        /**
         * 再次入棧
         */
        linearStack.push(6);
        /**
         * 再次顯示占中的所有元素
         */
        System.out.println("1：arrayStack:  " + linearStack.toString());
        /**
         * 獲取棧頂元素
         */
        System.out.println("獲取棧頂元素：stack[top] = " + linearStack.getTop()+"   top = " + linearStack.top);
        /**
         * 出棧
         */
        System.out.println("出棧：stack[top] = " + linearStack.pop()+"   top = " + linearStack.top);
        /**
         * 再次顯示棧中的元素
         */
        System.out.println("2：arrayStack:  " + linearStack.toString());

    }
}

四：棧的應(yīng)用（回文序列的判斷）

public class LinearStackChar {
    private int size = 5;
    /**
     * 指向棧頂?shù)臄?shù)組下標
     */
    int top = -1;
    /**
     * 定義棧stack
     */
    private char[] stack;
    public LinearStackChar() {
        stack = new char[size];
    }
    /**
     * 判斷棧滿
     */
    public  boolean isFull() {
        boolean result = false;
        if(top == size - 1) {
            result = true;
        }
        return result;
    }
    /**
     * 入棧操作push
     */
    public void push(char value) {
        /**
         * 如果棧滿，拓展棧的容量
         */
        if(isFull())
            stack = expansionStack();
        top++;
        stack[top] = value;
    }
    /**
     * 出棧操作
     */
    public  char  pop() {
        if(top == -1)
            throw new RuntimeException("?？眨〕鰲Ｊ?);
        char result = stack[top] ;
        top--;
        return result;
    }
    /**
     * 擴充容量
     */
    public char[] expansionStack() {
        size = size + 10;
        char[] stackTemp = new char[size];
        for (int i = 0; i < stack.length; i++) {
            stackTemp[i] = stack[i];
        }
        return stackTemp;
    }
    /**
     * 獲取棧頂?shù)脑?
     */
    public char getTop() {
        return stack[top];
    }
    /**
     * 顯示棧中的全部元素
     */
    public  String toString() {
        String str = "[";
        for (int i = 0; i <= top; i++) {
            if(i == top)
                str = str + stack[i] + "]";
            else
                str = str + stack[i] + ",";
        }
        return str;
    }
}

public class LinearStackCharTest {

    public static void main(String[] args) {
        /**
         * 判斷一個字符串a(chǎn)bcba是不是回文序列？
         * 思路：將字符串切割成為單個字符，存放在字符棧中；
         *      然后出棧，判斷出棧后字符數(shù)組組成的字符串是否和原字符串相等；
         *      相等--回文序列
         *      不相等--不是回文序列
         */
        String str = "abcba";
        LinearStackChar linearStackChar = new LinearStackChar();
        //講字符串切割，存放在棧中
        for (int i = 0; i < str.length(); i++) {
            linearStackChar.push(str.charAt(i));
        }
        //存放完成，顯示棧中的元素
        System.out.println("stack = " + linearStackChar.toString());
        //出棧
        String result = "";
        int length = linearStackChar.top;
        System.out.println("top = " + length);

        for (int i = 0; i <= length; i++) {
            result  = result + String.valueOf(linearStackChar.pop());
        }
        //出棧組成的字符串
        System.out.println("result = " + result);
        //判斷是否相等
        System.out.println("result = abcba?    " + (result.equals("abcba") ? true : false));

    }
}

總結(jié)

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之棧的線性結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java棧的線性結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: