数据结构：栈
1.栈的定义：
栈（Stack）又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外，还有栈的初始化，判空以及取栈顶元素等。
2.栈的常用算法例子
例子1: leet-code:20 有效的括号：
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出: false示例 5:输入: "{[]}"输出: true解题思路：
通过分析题目要求我们可以看出，这是一个对称字符串的匹配问题，对于这种问题需要将没有匹配到的字符一直保存着，直到没有字符串比较为止，而这正好就是栈所做的事情，所以我们的首选是栈，思路如下：
-1.先初步过滤掉数据，将奇数的字符串丢掉，这一步用来删选明显不成功的那些字符串组合。
-2.遍历字符串，将左括号(,[,{入栈。
-3.右括号到来的时候，去栈中取栈顶数据比较，是匹配的字符就出栈(备注：考虑栈为空的时候)
-4.都处理完了，栈非空为false,否则为true
代码实现：
func isValid(s string) bool { if len(s)%2 == 1 { return false } cc := []byte(s) var satckStr []byte for _, d := range cc { if d == '(' || d== '{' || d == '[' { satckStr = append(satckStr,d) } else { last := len(satckStr)-1 // 栈顶元素 if ok := popStrOk(d,satckStr,last); !ok { return false } satckStr = satckStr[:last] // 出栈 } } if len(satckStr) != 0 { return false } return true}func popStrOk(d byte, satckStr []byte, last int) bool{ if len(satckStr) == 0 { return false } switch d { case ')': if satckStr[last] != '(' { return false } case ']': if satckStr[last] != '[' { return false } case '}': if satckStr[last] != '{' { return false } default: return false } return true}运行结果：
例子2:简化路径：
题目描述：leet-code71以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。示例 1：输入："/home/"输出："/home"解释：注意，最后一个目录名后面没有斜杠。示例 2：输入："/../"输出："/"解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。示例 3：输入："/home//foo/"输出："/home/foo"解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。示例 4：输入："/a/./b/../../c/"输出："/c"示例 5：输入："/a/../../b/../c//.//"输出："/c"示例 6：输入："/a//b////c/d//././/.."输出："/a/b/c"解题思路：
分析题目我们可以看出，后面的字符串的处理逻辑需要依赖与前面存储的字符串特性，而这个正好符合栈的特性，所以我们通过栈来解决这个问题，如下所示：
-1.先将字符串转换成字符串数组，通过分隔符/，这里注意Go的strings.Split()会把//、///这种连续的字符 生成空字符串""来存储，所以我们需要过滤掉这些""字符串。
-2.对于路径来说只剩下..和.这两种特殊的字符，需要单独处理，..的话，需要将栈中的数据出栈，.字符的话不需要入栈，这两种之外的都需要做入栈操作。如此以来栈中存储的就是有效的路径字符串了。
-3.我们将栈中的字符串通过/拼接起来就是所需要的路径了，不过记得最后一位不要添加/
代码：
func simplifyPath(path string) string { tmps := strings.Split(path,"/") var paths []string for _,s:=range tmps { if len(s) != 0{ paths = append(paths,s) } } // fmt.Println("name",paths) var stacks []string for i:=0;i<len(paths);i++{ if paths[i]==".." { if len(stacks) > 0{ // 防止首路径就是..，例如../ stacks=stacks[:len(stacks)-1] } continue } if paths[i]!="."{ stacks=append(stacks,paths[i]) } } // fmt.Println("name",stacks,len(stacks)) resStr :="" for idx,s:=range stacks { resStr += s if idx != len(stacks)-1{ // 路径末尾不加/ resStr += "/" } } return "/"+resStr // 路径头部加上/}输出结果：
例子3: leet-code42:接雨水
题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
解题思路：
通过分析题目中的图，我们可以看出，接雨水是从当中的最高点往左右两边流的，而左右两边是对称的，所用算法相同，所以该问题变成了拆分数组，计算两边的数据结果，然后合并数组的操作。
计算数组的结果，后面的雨水的多少依赖于前面的柱子高度，这样一来，就需要用到栈来操作了。
-1.拆分数组，找到数组中的最高点，分成左边和右边两个数组。
-2.计算左边数组的结果。
--2.1.高1<高2:从左往右，第一个高的入栈，后续比他小或等于的计算数值，求和；
--2.2.高1==高2:从左往右，算法同1
--2.3.高1=0: 不入栈，不做计算；// 最左边
-3.按照2的方法计算右边数组的结果。
-4.合并左右两边的计算结果。
代码：
func trap(height []int) int { top := getTopIndx(height)
all := sum(height[:top]) // 计算左边的数据和 if top < len(height) { var tmp []int for i:= len(height)-1; i>top; i--{ tmp = append(tmp,height[i]) } all += sum(tmp) // 计算右边的数据和 } return all // 左右数据合并}
func getTopIndx(height []int) int { if len(height) == 0 { return 0 } var idx int var stacks []int // 这里的栈只是用来记录数组中的最大值 for i:=0;i<len(height);i++{ if i== 0{ // 首元素存入栈中 stacks = append(stacks,height[i]) }
if height[i] > stacks[len(stacks)-1] { // 与栈顶元素比较，将数据高的存储到栈顶 idx = i stacks = append(stacks,height[i]) } } return idx}func sum(height []int) int { if len(height) == 0 { return 0 } var stacks []int var h, s int for i:=0;i<len(height);i++ { if i == 0 { stacks = append(stacks,height[i]) } if len(stacks) > 0 { h = stacks[len(stacks)-1] } if height[i] > h { // 出栈再入栈 stacks[len(stacks)-1] = height[i] } else { s += h - height[i] } }
return s}运行结果：
例子4: leet-code:59.滑动窗口的最大值
题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]解释:滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7解题思路：
这个题目比较简单，主要切分成两个问题，一个是循环找m个k的数据；一个是计算k个元素的最大值。
第k个元素最大值可以利用栈来计算。
代码：
func maxSlidingWindow(nums []int, k int) []int { if len(nums) < k { return nil } var res []int for i:=0;i<len(nums)-k+1;i++ { max,ok := maxData(nums[i:i+k],k) if ok { res = append(res,max) } } return res}func maxData(nums []int,k int) (max int, ok bool) { if len(nums) != k || len(nums) == 0{ return } var stacks []int // 用栈来存储最大值 stacks = append(stacks,nums[0]) for idx, num := range nums { for i := len(stacks)-1; i>=0; i--{ if num > stacks[i] { stacks = stacks[:i] continue } } if idx != 0 { stacks = append(stacks,num) } } max = stacks[0] return max, true}