JAVA 基础 之 数据结构(栈)

栈简介：

栈（stack）是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。对于栈结构存储的对象，都遵循“先进后出，后进先出”的原则。
原型类似于像一个圆桶里放与桶半径稍小一点的圆饼一样，先放入（入栈）的圆饼必然里桶底（栈底）较近，取出时必须将从桶面（栈顶）的圆饼先取出（出栈）才能拿到其他圆饼

栈示意图

基于JAVA的String数组模拟栈结构的操作

package stack;
/**
 * @ClassName StackForArray
 * @Description String数组模拟栈，伪删除效果
 * @Author Vision
 * @Date 2019/7/1821:19
 * @Version 1.0.0
 */
public class StackForArray {
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        int length = stack.getMaxLength();
        System.out.printf("stack's maxLength:{%d} \n", stack.getMaxLength());
        System.out.printf("stack's top:{%d}\n", stack.getTop());
        System.out.println("入栈顺序");
        for (int i = 0; i < length; i++) {
            String str = "栈元素a" + i;
            stack.push(str);
            System.out.println(str);
        }
        System.out.printf("stack's new top:{%d}\n", stack.getTop());
        System.out.println("出栈顺序");
        for (int i = 0; i < length; i++) {
            System.out.println("pop = [" + stack.pop() + "]");
        }
        System.out.println("stack's maxLength after pop() = [" + stack.getMaxLength() + "]");
        System.out.println("stack's top after pop() = [" + stack.getTop() + "]");
    }
}
/**
 * 栈对象
 */
class Stack {
    /**
     * 数组
     */
    private String[] str;
    /**
     * 栈顶指针
     */
    private int top;
    /**
     * 栈空间
     */
    private int maxLength;
    public Stack() {
        this.top = -1;
    }
    public Stack(int num) {
        if (num > 0) {
            this.str = new String[num];
            this.top = -1;
            this.maxLength = num;
        } else {
            throw new RuntimeException("栈大小不能为0");
        }
    }
    /**
     * 入栈
     *
     * @param str
     */
    public void push(String str) {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        } else if (isFull()) {
            throw new RuntimeException("满栈");
        } else {
            this.str[++top] = str;
        }
    }
    /**
     * 出栈
     *
     * @return
     */
    public String pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        } else {
            String str = this.str[top--];
            /* 伪删除 */
            this.str[top + 1] = null;
            this.maxLength--;
            return str;
        }
    }
    /**
     * 判断是否为空栈
     *
     * @return
     */
    public boolean isEmpty() {
        return this.maxLength == 0;
    }
    /**
     * 判断是否满栈
     *
     * @return
     */
    public boolean isFull() {
        return this.top == this.maxLength - 1;
    }
    public String[] getStr() {
        return str;
    }
    public int getTop() {
        return top;
    }
    public void setStr(String[] str) {
        this.str = str;
        this.maxLength = str.length;
    }
    public void setTop(int top) {
        this.top = top;
    }
    public int getMaxLength() {
        return maxLength;
    }
    public void setMaxLength(int maxLength) {
        this.maxLength = maxLength;
    }
}

以上代码有缺陷，出栈时原数组的真实大小依旧没有改变，只是为NULL值，仅作为对栈类型理解的一种方法 且上述代码仅为基于数组模型的顺序栈 链式栈需使用到链表结构

运行结果

线性表和非线性表

线性表，就是数据排成像一条直线一样的结构，数组，链表，队列，栈都是线性结构，而非线性表就是二叉树，堆，图，哈希表等，数据之间不是简单的先后关系。