数据结构之栈

1.数据结构概念
    数据结构把数据组织起来，不同的数据有不同的存储方式，设计适合当前
    数据的算法

2.线性结构

线性结构：数组，栈，队列，链表；元素是一对一的线性关系；类型：顺序存储(数组)，链式存储(链表)

非线性结构：树，图，二维数组，多维数组，广义表

3.栈

栈特点：先进后出，后进先出

插入元素：压栈

取出元素：弹栈/出栈

4.使用数组模拟一个栈

public class ArrayStack {
    /**
     * 栈使用链表实现---动态栈
     * 栈使用数组实现---静态栈
     * 下面使用数组模拟栈
     */

    /**
     * top表示栈顶，默认值为-1，表示栈中没有数据
     * 当添加第一个数据时：  top=-1,变为top=0,即添加一个元素，top加1
     * 当生产最后一个元素时：top=0,变为top=-1,即删除一个元素，top减1
     */
    private Integer top = -1;

    /**
     * 栈的最大长度
     */
    private Integer stackMaxSize;

    /**
     * 栈数组
     */
    Integer [] stackArray;

    /**
     * 创建指定长度的栈
     */
    public ArrayStack(Integer stackMaxSize){
        this.stackMaxSize = stackMaxSize;
        this.stackArray = new Integer[stackMaxSize];
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty(){
        return this.top == -1;
    }

    /**
     * 判断栈是否满
     */
    public boolean isFull(){
        return this.top == this.stackMaxSize-1;
    }

    /**
     * 压栈,需要判断栈是否满
     */
    public boolean push(Integer value){
        if (isFull()){
            System.out.println("栈满");
            return false;
        }
        top++;
        stackArray[top] = value;
        return true;
    }

    /**
     * 弹栈,判断栈是否为空栈
     */
    public boolean pop(){
        if (isEmpty()){
            System.out.println("已是空栈");
            return false;
        }
        top--;
        System.out.println(stackArray[top+1]+",已弹出");
        return true;
    }

    /**
     * 查询栈中的元素
     */
    public void queryArrayStack(){
        for (int i=0;i<=top;i++){
            System.out.println(stackArray[i]);
        }
    }
}

/**
 * 问题1：如何使用栈判断是否是回文数,3443，456654这样的数据接收回文数
 * 解决：把一个回文数进行压栈,然后出栈
 *      如果出栈的顺序和入栈的顺序一样,证明是回文数
 * 
 * 问题二：运用栈,计算 5-8+9*12+0+8/22值
 * 解决(大概思路)：创建两个栈,一个存放数字,一个存放运算符
 *              后一个运算符优先级比前一个运算符优先级小或等于,就计算前面的一个运算符的运算
 *              后一个运算符优先级比前一个运算符优先级大,把这个运算符压栈
 */