栈

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

栈的接口设计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


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();
    }
}