数据结构-栈(Stack)

基本概念

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作

说明：
    进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
    栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
    压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
    出栈：栈的删除操作叫做出栈。出数据在栈顶。

JAVA示例

import java.util.Arrays;
import java.util.Stack;
 
public class Test {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);//入栈
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.peek());//获取栈顶元素
        System.out.println(myStack.pop());//出栈
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.isEmpty());//判断栈是否为空，如果为空返回true，否则返回false
    }
}

public class MyStack {
    public int[] elem; //数组 -> 栈空间
    public int usedSize;//有效数据
    public MyStack(){
        this.elem = new int[5];
        this.usedSize = 0;
    }
    //入栈
    public void push(int val){
        //如果栈满了就进行扩容
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        usedSize++;
    }
    //判断栈是否满
    public boolean isFull(){
        return usedSize==this.elem.length;
    }
 
    //出栈
    public int pop(){
        if(isEmpty()){
            throw new NullPointerException("栈为空！");
        }
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return this.usedSize==0;
    }
 
    //读取栈顶元素
    public int peek(){
        if(isEmpty()){
            throw new NullPointerException("栈为空！");
        }
        return this.elem[usedSize-1];
    }
}

使用链表需要满足的条件：

    先进后出
    入栈和出栈的时间复杂度为O(1)

链表可以头插也可以尾插，那么入栈是使用头插法还是使用尾插法呢？

    假设：如果入栈使用尾插法，那么时间复杂度是O(n)，因为尾插法每次都要找最后一个结点。
    假设：如果入栈使用头插法，那么时间复杂度是O(1)；出栈的时候只需要删除头结点，时间复杂度也是O(1)

经过推导得出，使用头插法实现栈使满足条件，但是如果非要使用尾插法呢？

    假设给一个last引用指向尾巴结点，此时入栈的时间复杂度为O(1)。
    但是出栈的时间复杂度还是O(n)。因为，虽然知道了最后一个结点，但是去掉尾巴结点后还要知道它的前一个结点，那么就要遍历单链表去找尾巴结点的前驱结点。此时时间复杂度又是O(n)。

最终的解决办法就是使用双向链表来实现一个栈。（双向链表可以知道一个结点的前驱结点与后继结点）。

逆波兰表达式

逆波兰表达式是一种后缀表达式，所谓后缀就是指运算符写在后面

根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意：两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<tokens.length;i++){
            String str = tokens[i];
            if(isOperation(str)==false){
                stack.push(Integer.parseInt(str));
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(str){
                    case"+": stack.push(num1+num2);break;
                    case"-": stack.push(num1-num2);break;
                    case"*": stack.push(num1*num2);break;
                    case"/": stack.push(num1/num2);break;
                }
            }
        }
        return stack.pop();
    }
 
    private boolean isOperation(String str){
        if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
            return true;
        }
        return false;
    }
}