栈（Stack）是一种常见的数据结构，它遵循后进先出（LIFO，Last-In-First-Out）的原则。

基本介绍

栈可以看作是一种特殊的线性表，只能在一端进行插入和删除操作，该端被称为栈顶，另一端被称为栈底。栈的操作包括入栈（Push）和出栈（Pop），入栈将元素放入栈顶，出栈将栈顶元素移除。

JAVA实现

以下是基于数组实现的栈

public class Stack {
    private int size = 0;
    private int[] array;
    public Stack() {
        this(10);
    }
    public Stack(int init) {
        if (init <= 0) {
            init = 10;
        }
        array = new int[init];
    }
    /**
      * 入栈
      * @param item 入栈元素的值
    */
    public void push(int item) {
        if (size == array.length) {
            array = Arrays.copyOf(array, size * 2);
        }
        array[size++] = item;
    }
    /**
      * 获取栈顶元素，但是没有出栈
      * @return
      */
    public int peek() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("栈里已经空啦");
        }
        return array[size - 1];
    }
    /**
      * 出栈，同时获取栈顶元素
      * @return
      */
    public int pop() {
        int item = peek();
        size --; // 直接使元素个数减1，不需要真的清除元素，下次入栈会覆盖旧元素值
        return item;
    }
    /**
      * 栈是否满了
      * @return
      */
    public boolean isFull() {
        return size == array.length;
    }
    /**
      * 栈是否为空栈
      * @return
      */
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
}

经典应用

函数调用和递归

栈常用于函数调用和递归的实现。每当一个函数被调用时，相关的信息（如参数、返回地址等）会被压入栈中，函数执行完毕后，再从栈中弹出这些信息，恢复到调用该函数的状态。

比如java虚拟机栈的应用

表达式求值

栈可以用于表达式求值，例如中缀表达式转换为后缀表达式，并通过栈来计算后缀表达式的值。运算符和操作数依次入栈，当遇到运算符时，从栈中弹出操作数进行计算，计算结果再入栈，直到最终得到表达式的值。

经典案例是逆波兰表达式求值 (Evaluate Reverse Polish Notation)

题目描述

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入： tokens = ["2","1","+","3","*"]
输出： 9
解释： 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

代码实现

public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }

括号匹配

栈常用于检查括号匹配。遍历字符串中的字符，当遇到左括号时，将其入栈，当遇到右括号时，与栈顶元素进行匹配，如果匹配成功，则将栈顶元素弹出，继续遍历；如果匹配失败或栈为空，则表示括号不匹配。

经典题目比如最长有效括号 (Longest Valid Parentheses)

题目描述

给定一个仅包含字符'('和 的字符串')'，返回*最长有效（格式良好）括号的长度子串

示例1：

输入： s = "(()"
输出： 2
解释： 最长的有效括号子字符串是“()”。

示例2：

输入： s = ")()())"
输出： 4
解释： 最长的有效括号子字符串是 "()()"。

代码实现

public int longestValidParentheses(String s) {
        Stack<Integer> st = new Stack<>();
        st.push(-1);
        int n = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if(s.charAt(i) == '(')
                st.push(i);
            else if(s.charAt(i) == ')')
            {
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    n = Math.max(n, i - st.peek());
            }
        }
        return n;
    }

撤销操作

在许多应用程序中，撤销操作是常见的功能。栈可以用于记录操作的历史记录，每当执行一个操作时，相关的信息被压入栈中，当用户需要撤销操作时，从栈中弹出最近的操作信息，回退到上一个状态。

还有浏览器的前进和后退操作也是类似。