這一部分，我們開始介紹“棧、隊列、優(yōu)先隊列”。棧和隊列雖然是簡單的數(shù)據(jù)結(jié)構(gòu)，但是使用這些簡單的數(shù)據(jù)結(jié)構(gòu)所解決的算法問題不一定簡單。在這一章里，我們將來探索，和棧與隊列相關(guān)的算法問題。
棧和隊列的使用，棧和隊列是兩種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。Stack 這個基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的特點是：后進先出，這一點是非常重要的。下面請看 LeetCode 第 20 題：
例題：LeetCode 第 20 題：有效的括號
傳送門：英文網(wǎng)址：20. Valid Parentheses ，中文網(wǎng)址：20. 有效的括號 。
給定一個只包括
'('，')'，'{'，'}'，'['，']'的字符串，判斷字符串是否有效。有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()" 輸出: true示例 2:
輸入: "()[]{}" 輸出: true示例 3:
輸入: "(]" 輸出: false示例 4:
輸入: "([)]" 輸出: false示例 5:
輸入: "{[]}" 輸出: true
分析：典型應(yīng)用，檢查括號匹配，是文本編輯器常見的功能。
注意空字符串可被認(rèn)為是有效字符串。
思路：問題本身非常容易。判斷字符串中的括號匹配是否合法。遍歷一遍這個字符串，使用一個 Stack 作為輔助空間。
一旦遇到左方向的符號，就把這個符號推入棧。
一旦遇到右方向的符號，將棧的棧頂元素出棧，就須要判斷是否對應(yīng)匹配。
Stack 中只是存放左方向的符號：“{”、“[”、“(”，在整個方法返回之前，一定要判斷一下 Stack 是否為空。因為 Stack 有可能出現(xiàn)全是左括號的情況。即：在棧中還有元素的情況下，待檢測的字符串一定是不符合題意的。
我的解答（看起來有些繁瑣）：
下面我按照老師的解法，寫了一個不是優(yōu)化了很多的解法：
Java 代碼：
public class Solution {
public boolean isValid(String s) {
boolean isValid = false;
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);
}
if (c == '}' || c == ')' || c == ']') {
// 出棧之前，應(yīng)該先檢查一下棧中是否還有元素
if (stack.isEmpty()) {
return isValid;
}
Character popElement = stack.pop();
Character match = null;
if (c == '}') {
match = '{';
}
if (c == ']') {
match = '[';
}
if (c == ')') {
match = '(';
}
if (popElement != match) {
return isValid;
}
}
}
if (stack.isEmpty()) {
isValid = true;
}
return isValid;
}
public static void main(String[] args) {
Solution solution = new Solution();
boolean result = solution.isValid("8{90[s(d)f]44}33");
System.out.println(result);
}
}
說明：最后的這一步：
if (stack.isEmpty()) {
isValid = true;
}
很容易忽略，請留意。
學(xué)到棧的時候，也學(xué)習(xí)了一些經(jīng)典的使用棧解決問題，我們要思考一下為什么使用棧？
使用棧的原因：在一個嵌套的關(guān)系中，通過棧頂元素來獲得最近的那個我們須要處理的元素。
棧頂元素反映了在嵌套的層次關(guān)系中，最近的需要匹配的元素。
Python 代碼：
# 20. 有效的括號
# 給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
d = ["()", "[]", "{}"]
for i in range(0, len(s)):
stack.append(s[i])
if len(stack) >= 2 and stack[-2] + stack[-1] in d:
stack.pop()
stack.pop()
return len(stack) == 0
練習(xí) 1：LeetCode 第 150 題： 逆波蘭表達式求值
傳送門：150. 逆波蘭表達式求值。
根據(jù)逆波蘭表示法，求表達式的值。
有效的運算符包括
+,-,*,/。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。說明：
- 整數(shù)除法只保留整數(shù)部分。
- 給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。
示例 1：
輸入: ["2", "1", "+", "3", "*"] 輸出: 9 解釋: ((2 + 1) * 3) = 9示例 2：
輸入: ["4", "13", "5", "/", "+"] 輸出: 6 解釋: (4 + (13 / 5)) = 6示例 3：
輸入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 輸出: 22 解釋: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Java 代碼：
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String token = tokens[i];
String pattern = "-?[0-9]+|[\\+\\-\\*/]";
if (!token.matches(pattern)) {
throw new RuntimeException("非法的表達式");
}
if (token.matches("-?[0-9]+")) {
int num = Integer.valueOf(token);
System.out.println(num);
stack.push(num);
}
if (token.matches("[\\+\\-\\*/]")) {
System.out.println("加減乘除" + token);
if (stack.size() >= 2) {
int num1 = stack.pop();
int num2 = stack.pop();
int result = 0;
switch (token){
case "+":
result = num2 +num1;
break;
case "-":
result = num2 -num1;
break;
case "*":
result = num2 *num1;
break;
case "/":
result = num2 /num1;
break;
}
stack.push(result);
}
}
}
return stack.pop();
}
public static void main(String[] args) {
String[] tokens = new String[]{"3", "-4", "+"};
Solution solution = new Solution();
int result = solution.evalRPN(tokens);
System.out.println(result);
}
}
是有問題的：Time Limit Exceeded 。然后我把上面的兩個 System.out.println() 語句刪除就 A 過了，好神奇，所以做題還是要規(guī)范啊。
練習(xí)2：LeetCode 第 71 題：簡化路徑
傳送門：71. 簡化路徑。
以 Unix 風(fēng)格給出一個文件的絕對路徑，你需要簡化它。或者換句話說，將其轉(zhuǎn)換為規(guī)范路徑。
在 Unix 風(fēng)格的文件系統(tǒng)中，一個點（
.）表示當(dāng)前目錄本身；此外，兩個點 （..） 表示將目錄切換到上一級（指向父目錄）；兩者都可以是復(fù)雜相對路徑的組成部分。更多信息請參閱：Linux / Unix中的絕對路徑 vs 相對路徑請注意，返回的規(guī)范路徑必須始終以斜杠
/開頭，并且兩個目錄名之間必須只有一個斜杠/。最后一個目錄名（如果存在）不能以/結(jié)尾。此外，規(guī)范路徑必須是表示絕對路徑的最短字符串。示例 1：
輸入："/home/" 輸出："/home" 解釋：注意，最后一個目錄名后面沒有斜杠。示例 2：
輸入："/../" 輸出："/" 解釋：從根目錄向上一級是不可行的，因為根是你可以到達的最高級。示例 3：
輸入："/home//foo/" 輸出："/home/foo" 解釋：在規(guī)范路徑中，多個連續(xù)斜杠需要用一個斜杠替換。示例 4：
輸入："/a/./b/../../c/" 輸出："/c"示例 5：
輸入："/a/../../b/../c//.//" 輸出："/c"示例 6：
輸入："/a//b////c/d//././/.." 輸出："/a/b/c"
參考了如下的文章：http://blog.csdn.net/u012249528/article/details/46705867
Java 代碼實現(xiàn)：
public class Solution {
public String simplifyPath(String path) {
String result = "";
String[] pathList = path.split("/");
if (pathList.length == 0) {
return "/";
}
Stack<String> stack = new Stack<>();
for (String p : pathList) {
if ("".equals(p) || ".".equals(p)) {
continue;
}
if ("..".equals(p)) {
if (!stack.isEmpty()) {
stack.pop();
}
} else { // 是正常的路徑字符串的時候，入棧
stack.push(p);
}
}
// 現(xiàn)在考慮輸出字符串
while (!stack.isEmpty()) {
result = "/" + stack.pop() + result;
}
if ("".equals(result)) {
result = "/";
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
String path1 = "/home/";
String result1 = solution.simplifyPath(path1);
System.out.println(result1);
String path2 = "/a/./b/../../c/";
String result2 = solution.simplifyPath(path2);
System.out.println(result2);
String path3 = "/..";
String result3 = solution.simplifyPath(path3);
System.out.println(result3);
String path4 = "/..";
String result4 = solution.simplifyPath(path4);
System.out.println(result4);
String path5 = "/abc/def/.";
String result5 = solution.simplifyPath(path5);
System.out.println(result5);
}
}
（本節(jié)完）
