亲宝软件园·资讯

展开

Java栈的线性结构 Java数据结构之栈的线性结构详解

Cbw 人气:0
想了解Java数据结构之栈的线性结构详解的相关内容吗,Cbw在本文为您仔细讲解Java栈的线性结构的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:用java实现栈结构,栈是线性结构,java栈的线性结构,下面大家一起来学习吧。

一:栈

栈是限制插入和删除只能在一个位置上进行的表,此位置就是表的末端,叫作栈顶。

栈的基本操作分为push(入栈) 和 pop(出栈),前者相当于插入元素到表的末端(栈顶),后者相当于删除栈顶的元素。

二:栈的实现

public class LinearStack {
    /**
     * 栈的初始默认大小为10
     */
    private int size = 5;
    /**
     * 指向栈顶的数组下标
     */
    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;
    }
    /**
     * 获取栈顶的元素
     */
    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());

    }
}

四:栈的应用(回文序列的判断)

public class LinearStackChar {
    private int size = 5;
    /**
     * 指向栈顶的数组下标
     */
    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;
    }
    /**
     * 获取栈顶的元素
     */
    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) {
        /**
         * 判断一个字符串abcba是不是回文序列?
         * 思路:将字符串切割成为单个字符,存放在字符栈中;
         *      然后出栈,判断出栈后字符数组组成的字符串是否和原字符串相等;
         *      相等--回文序列
         *      不相等--不是回文序列
         */
        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));

    }
}

总结

加载全部内容

相关教程
猜你喜欢
用户评论