栈

• 栈是一种特殊的线性表，只能在一端进行操作
• 往栈中添加元素的操作，一般叫做 push，入栈
• 从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
• 后进先出的原则，Last In First Out，LIFO

栈的接口设计

public class Stack<E> {
	private MyList<E> list = new DynamicArrayListV2<E>();
	/**
	* 清空
	*/
	public void clear() {
		list.clear();
	}
	/**
	* 元素数量
	*/
	public int size() {
		return list.size();
	}
	/**
	* 是否为空
	*/
	public boolean isEmpty() {
		return list.isEmpty();
	}
	/**
	* 入栈
	*/
	public void push(E element) {
		list.add(element);
	}

	/**
	* 出栈
	*/
	public E pop() {
		return list.remove(list.size() - 1);
	}

	/**
	* 获取栈顶元素
	*/
	public E top() {
		return list.get(list.size() - 1);
	}
}

栈的应用：leetcode算法题

题目：给定一个包含'('，')'，'{'，'}'，'['，']'的字符串，是否有效。

满足条件：1.左括号必须用相同类型的右括号闭合 2.左括号必须以正确的顺序闭合

示例1：

输入："()"

输出：true

示例2：

输入："()[]{}"

输出：true

示例3：

输入："(]"

输出：false

示例4：

输入："([)]"

输出：fasle

示例5：

输入："{[]}"

输出：true

1. 遇见左字符，将左字符入栈
2. 遇见右字符
   如果栈是空的，说明括号无效
   如果栈不为空，将栈顶字符出栈，与右字符之匹配
   ✓ 如果左右字符不匹配，说明括号无效
   ✓ 如果左右字符匹配，继续扫描下一个字符
3. 所有字符扫描完毕后
   ✓ 栈为空，说明括号有效
   ✓ 栈不为空，说明括号无效

解法之一（使用栈）：

import java.util.Stack;

public class Test20 {

    public static void main(String[] args) {
        String s = "([)]";
        Test20 test20 = new Test20();
        System.out.println(test20.isValid(s));
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}