点击上方蓝字，关注：无量测试之道

1.开篇问题：有效的括号[1]

假如现在要你来解这道题，你会想到怎样的解法了？

2.如何理解“栈”？

    关于栈，有一个非常贴切的游戏--汉诺塔。玩这个游戏的时候，我们都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
栈的定义[2]：

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

3.如何实现栈

  
  
  

   
   class Stack {
    //初始化数组
    var datas = [Int]()
    //出栈操作
    func pop() -> Int? {
        return datas.popLast()
    }
    //入栈操作
    func push(obj: Int) {
        datas.append(obj)
    }
    //栈顶对象
    func top() -> Int? {
        return datas.last
    }
}
  
  
  

4.栈在实际开发过程中的应用

• 栈在函数调用中的应用

  
  
  

   
   func calculate() {
    let a = 3
    let b = 5
    var result = 0
    result = add(x: a, y: b)
    print(result)
}

func add(x: Int, y: Int) -> Int {
    var sum= 0
    sum = x + y
    return sum
}

  
  
  

• 递归

5.概念区分：数据结构堆栈 VS 内存中的堆栈

6.解答开篇

• 1.如果开始就是右括号 )、]、} ，很明显不合法，直接返回false
• 2.如果是左括号  (、[、{ ，就压栈。如果是右括号 )、]、} ，在stack有值的情况下与栈顶元素匹配，匹配通过则栈顶元素出栈，否则直接返回false。

  
  
  

   
   class Solution {
      
    func isValid(_ s: String) -> Bool {
        
        if s.count == 0  { return false }
        var stack = [String]()
        let dict: [String:String] = ["(":")","[":"]","{":"}"]
        
        for c in s {
            if dict.keys.contains(c.description) {
                stack.append(c.description) //如果是左括号就入栈
            }else {
                if stack.count > 0 && c.description == dict[stack.last!] { //如果是右括号，并且匹配就出栈
                    stack.removeLast()
                }else {
                    return false
                }
            }
        }
        return stack.count == 0
    }
}

  
  
  

7.内容总结

参考资料：

• 1.有效的括号:
  https://leetcode-cn.com/problems/valid-parentheses
  
  
  

• 2.栈的定义:

  https://baike.baidu.com/item/%E6%A0%88/12808149?fr=aladdin

  
  

  
  

• 3.斐波那契数列:

  https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin 

  
  

• 4.python语言实现:

  https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/

如果今天的分享对你有帮助的话，请毫不犹豫：分享、点赞、在看、收藏呀~
你的鼓励将会是我创作的最大动力。

◆Python 经典算法之 “ 选择排序 ”

◆Python 之“栈为何物”

◆Python 算法之一

点个赞，点个在看再走吧~~~