数据结构第一季 Day04 栈

1. 请绘制出栈的结构图？栈 和 栈空间 是一个概念吗？

• 后进先出的原则， Last In First Out，LIFO
• 栈空间 和 栈 不是同一个概念

image.png

2. 思考栈的内部实现是否可以直接利用以前学过的数据结构？如果可以使用哪个最合适？

• 因为栈的特点是 频繁在尾部增删改查，而 双向链表 和 动态数组 在尾部进行这些操作的是会，时间复杂度都是 O(1)，所以用 双向链表 或 动态数组 都可以。

image.png

3. 思考如下做法，让栈继承自 ArrayList ，然后添加几个方法，即可实现一个栈。但是这中继承的方式好吗？有什么问题？

image.png

• 继承 的方式会存在问题，用户不仅仅可以使用栈声明的方法，可以直接调用 ArrayList 的方法，这样的 栈不纯粹。

4. 思考：如何解决上题中出现的问题？

• 复用代码的最常用的方式有两种：继承 、 组合
• 既然 继承 不合适，那使用 组合复用原则 即可。

image.png

5. 浏览器的前进和后退；软件的撤销和恢复，用什么数据结构实现？关键点是什么？

• 可以使用 栈 这种数据结构实现，关键点在于 使用两个栈

image.png

6. 练习：有效括号

image.png

• 核心思想：最先拿到的括号，不能马上使用。很可能放到最后才使用，这就很契合栈的特点

7. 练习：(TODO)

image.png