【第二天 - Stack 介绍】

Q1. Stack 是什麽

• 一种资料结构的概念，假设有一个容器是装马克杯的盒子 (这个盒子下面是封死的，无法拿东西)

  • 

• 现在第一步有小明、小美、小雅的马克杯，依序被放入盒子中

  • 

• 课间小 Q&A： 你现在要从盒子中取出一个马克杯，请问你会拿到谁的马克杯 ?

• ANS：盒子内的杯子排序预期是如下图，所以你从盒子取，只能拿到最上面的杯子，也就是小雅的杯子

  • 

• 也就是说，这种 Stack 概念，最後放的杯子，会最先拿起来，最早放的杯子，会被垫在最下面，最後才能拿到，也就是「先进後出」「後进先出」的概念 ( 英文称为 Last-In-First-Out )

Q2. 所以学会 Stack 概念可以做什麽 ?

• 需要纪录状态，并且「先拿」「最後一个」状态的时候，例如：
  • 浏览器的「回到上一页」，他就跳到你上一步最後浏览的网页
  • word 的 ctrl + Z 的复原键
  • 你要设计一只会走迷宫的机器人，你希望他遇到分岔路，都能记录状态，当机器人走到死路，就回到上一次遇到的交叉路，最终就能找到出口
    • 

Lab. 明天要解的题目：20. Valid Parentheses

题目连结：https://leetcode.com/problems/valid-parentheses/
题目叙述：

• 你需要判断是不是正常括号表示方式

  • 例如 ( 就要用 ) 作为闭合，不能使用 } 跟 ]

• 你需要判断他是不是正常的方式闭合

  • 例如 ([)]，这种闭合方式就会错误

• 

• 测资的 Input/Output

  • 你会收到一个 s 变数的字串，s 会包含你要处理的字串
  • 最终你需要处理，s 字串是不是符合题目的规定，并回传 True或False

• 

• 题目的条件

  • 变数 s 至少会有一个字元，最长为 10000
  • s 变数中只会出现有 ()[]{} 这样的字元
    • 代表连空格都不会出现，所以你不能写 ( ) [ ] { }

• 

• 看完题目，你要思考：

  • 如果 ([)] 是错误的，那什麽是正确的 ?
    • 你写 ()[] 或 [()] 或 ([]) 是不是都可以 ?
  • 在小学数学运算中，{}是大括号，[]是中括号，()是小括号，优先顺序为小括号 > 中括号 > 大括号，那这一个题目，遇到 ([{}]) 这样的情况，是不是也是可接受的 ?

• 明天会分析该题 python 不同解法的优点，希望大家今天可以多先自己想一下这题 Stack 题如果是你，你的思考逻辑是什麽?