栈

发表于

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈

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

栈01

接口设计

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
public class Stack<E> {
	/*
	 * 清空
	 */
	public void clear() {
		
	}
	/*
	 * 大小
	 */
	public int size() {
		return 0;
	}
	/*
	 * 判空
	 */
	public boolean isEmpty() {
		return false;
	}
	/*
	 * 入栈
	 */
	public void push(E element) {
		
	}
	/*
	 * 出栈
	 */
	public E pop() {
		return null;
	}
	/*
	 * 获取顶部元素
	 */
	public E top() {
		return null;
	}
}

因为动态数组和双向链表在添加删除随后一个元素的复杂度都是 O(1) 级别，所以这两种数据结构都可以用来实现栈。下面是采用动态数组实现的栈。
栈02

实现-继承

采用继承的方式实现栈，继承 ArrayList 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import com.yq.list.ArrayList;
public class Stack<E> extends ArrayList<E>{
	/*
	 * 入栈
	 */
	public void push(E element) {
		add(element);
	}
	/*
	 * 出栈
	 */
	public E pop() {
		return remove(size-1);
	}
	/*
	 * 获取顶部元素
	 */
	public E top() {
		return get(size-1);
	}
}

clear()、size()和isEmpty() 父类已经实现了。

测试：

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
	Stack<Integer> stack = new Stack<>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	
	while (!stack.isEmpty()) {
		System.out.println(stack.pop());
	}
}

打印结果：

1
2
3
4
4
3
2
1

继承可以实现栈的效果，但是却存在一个问题：stack 可以访问到 ArrayList 所有的开放接口，stack.add()、stack.remove() 等。解决方案👇。

实现-组合

采用组合的方式实现栈，实现：

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
public class Stack2<E> {
	ArrayList<E> list = new ArrayList<>();
	/*
	 * 清空
	 */
	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);
	}
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void testStack2() {
	Stack<Integer> stack = new Stack<>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	
	while (!stack.isEmpty()) {
		System.out.println(stack.pop());
	}
}
public static void main(String[] args) {
	testStack2();
}

打印结果：

1
2
3
4
4
3
2
1

应用

游览器的前进和后退就是通过栈来实现的：

依次访问 jd.com、qq.com 和 baidu.com：
栈03
后退
栈04
后退
栈05
前进
栈06
访问 taobao.com
栈07

类似场景：软件的撤销、恢复功能。

源码分析

Stack 继承自 Vector，Vector 也是动态数组，相较于 ArrayList，Vector 是线程安全的。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Stack<E> extends Vector<E> {
	/**
     * Creates an empty Stack.
     */
    public Stack() {
    }
    /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the {@code item} argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);
        return item;
    }
    /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the {@code Vector} object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }
    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the {@code Vector} object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    /**
     * Tests if this stack is empty.
     *
     * @return  {@code true} if and only if this stack contains
     *          no items; {@code false} otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }
	...
}

练习

有效的括号

20. 有效的括号

  1. 遇见左字符，将左字符入栈；
  2. 遇见右字符：
    如果展示空的，说明括号无效；
    如果站不为空，将栈顶字符出出栈，与右字符匹配：
    -> 如果左右字符不匹配 -> 括号无效；
    -> 如果左右字符匹配 -> 继续扫描下一个字符；
  3. 所有字符扫描完毕后：
    栈为空 -> 括号有效；
    栈不为空 -> 括号无效；
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public boolean isValid(String s) {
    	Stack<Character> stack = new Stack<>();
    	
    	for (int i = 0; i < s.length(); i++) {
    		char c = s.charAt(i);
    		if (c == '(' || c == '[' || c == '{') {
    			stack.push(c);
    		} else {
    			if (stack.isEmpty()) return false;
    			
    			char left = stack.pop();
    			if (left == '(' && c != ')') return false;
    			if (left == '[' && c != ']') return false;
    			if (left == '{' && c != '}') return false;
    		}	
    	}
    	
    	return stack.isEmpty();
    }

括号的分数

856. 括号的分数
括号的分数 - 方法二：栈

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
/*
 * ()、(()(、()( 对于只有一层括号的情况，top == 0：
 * 1. 取出 top = pop();
 * 2. 修改 top = 1，并 push(top);
 * 3. 判断前一项是否可加
 *  
 * 示例：
 * ( : [0] ~> () : [1] 
 * (()( : [0, 1, 0] ~> (()() : [0, 2]
 * ()(：[1, 0] ~> ()()：[2]
 */
 /* 
 * (())、(()()) 对于外层有括号的情况，top != 0：
 * 1. 取出 top = pop();
 * 2. 修改 top *=2，并 push(top);
 * 3. 判断前一项是否可加；
 * 
 * 示例：
 * (() : [0, 1] ~> (()) : [2]
 * (()() : [0, 1, 1] ~> (()()) : [4]
 * (()(( : [0, 1, 0, 0] ~> (()(() : [0, 1, 1]
 */
static int scoreOfParentheses6(String S) {
	Stack<Integer> stack = new Stack<>();
	stack.push(0);
	for (char c : S.toCharArray()) {
		if (c == '(') {
			stack.push(0);
		} else {
			int top = stack.pop();
			int left = stack.pop();
			stack.push(left + Math.max(2 * top, 1));
		}
	}
	return stack.pop();
}

逆波兰表达式求值

逆波兰表达式
栈08
150. 逆波兰表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int evalRPN(String[] tokens) {
	Stack<Integer> stack = new Stack<>(); 
	for (String s : tokens) {
		if (s == "+") {
			stack.push(stack.pop() + stack.pop());
		} else if (s == "-") {
			stack.push(-(stack.pop() - stack.pop()));
		} else if (s == "*") {
			stack.push(stack.pop() * stack.pop());
		} else if (s == "/") {
			Integer s1 = stack.pop();
			stack.push(stack.pop() / s1);
		} else {
			stack.push(Integer.valueOf(s));
		}
	}
	return stack.pop();
}

ps：
前缀表达式
中缀表达式
后缀表达式

基本计算器

224. 基本计算器

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
static int calculate(String s) {
	Stack<Integer> stack = new Stack<>();
	int res = 0;
	int operand = 0; //位数
	int sign = 1; //+：1，-：-1
	
	for (char c : s.toCharArray()) {
		if (c == ' ')
			continue;
		
		if (c >= '0' && c <= '9') {
			operand = operand*10 + (c - '0');
		} else if (c == '+' || c == '-') {
			res += operand*sign;
			operand = 0; // 重置位数
			sign = c == '+' ? 1 : -1; // 重置符号
			
		} else if (c == '(') {
			stack.push(res);
			stack.push(sign);
			res = 0;
			sign = 1;
		} else { // c == ')'
			res += operand*sign;
			operand = 0;
			
			int a = stack.pop(); //上一次的 sign
			int b = stack.pop(); //上一次的 sum
			
			res += b*a;
		}
	}
	return res + sign * operand;
}