既然学了栈这种数据结构，那么就应该进一步深入或者熟练地应用。这也构成了两种不同的应用方式：
- 一种是利用栈这种数据结构，来实现一些其他的数据结构，比如：用栈来实现队列，或者是实现一些特殊的栈，比如：最小栈。
- 另一种是具体问题的解决，比如经典的逆波兰表达式的求解等一系列问题
闲话部分——在线提交
为什么要在线提交？答案很简单，就是保证自己代码的完全正确性。
怎么理解呢，就是说，你写完一个程序之后，应该仅仅会想出一组或者部分样例来进行测试代码运行结果是否符合自己的预期，但是自己想出来的这些样例往往是不完备的，而在线提交平台的样例基本是完备的，尤其是一些著名的提交平台。
那么有哪些平台可以选择呢？
- 我个人的喜好是
LeetCode ，由于网速和英语不好的原因，我选择了其中文网站，如果想练习英语，也可以进其英文官网。
- 还有其他类似的平台，牛客啊啥的，可凭自己喜好进行选择。
栈的应用
LeetCode 还有比较好的一点就是可以按照标签进行刷题，而网站的题量也在稳步上升，而关于栈的应用，我特意选了这么几道有代表性的题：
例题题解
用什么编程语言写是个问题，我个人觉得，用一些数据结构库比较完备的语言来写比较好，因为写这些题的目的是使用栈来解答问题，而不再需要过度关注栈的构成。
所以我推荐类似于 C++ ，java 甚至 python 等语言来写题。 但是也要注意库的使用，不能说题目让自己实现一个什么，然后你直接调用已经实现的库函数搞定，这样就背离了题目的初衷。
最小栈
题目就不复制过来了，可点击链接查看。
最小栈就是要自己实现一个名为最小栈的数据结构，这个数据结构与普通的栈不同的是，可以在常数时间内检测到栈中的最小元素，那么可利用两个栈来实现，从而降低时间复杂度。此题 java 代码如下：
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
| class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int x) {
stack.push(x);
if (minStack.empty() || x <= minStack.peek())
minStack.push(x);
}
public void pop() {
int tmp = stack.pop();
if (tmp == minStack.peek())
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
|
stack 栈作为普通的栈使用，而 minStack 作为最小栈
逆波兰表达式求值
这是一个极为基础的栈题，可以说完全是一个基础的栈的练习，所以也不必进行太多的解释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
int one = stack.pop();
int two = stack.pop();
if (token.equals("-"))
stack.push(two-one);
else if (token.equals("*"))
stack.push(two*one);
else if (token.equals("/"))
stack.push(two/one);
else if (token.equals("+"))
stack.push(two+one);
} else
stack.push(Integer.parseInt(token));
}
return stack.peek();
}
}
|
二叉树前序遍历
二叉树前序遍历可利用递归简单地写出，而如果不使用递归的话，就要利用栈来实现，java 代码如下：
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
|
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty()) {
if (stack.peek() == null) {
stack.pop();
continue;
}
TreeNode tmp = stack.pop();
ret.add(tmp.val);
stack.push(tmp.right);
stack.push(tmp.left);
}
return ret;
}
}
|
- 利用栈
先进后出 的特性，先压右子树，再将左子树压入栈中即可。
