【010-week1】关于Stack的一些新的理解

[James-Ren]

什么是Stack？

堆栈（Stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。按照后进先出（LIFO, Last In First Out）的原理运作。

Stack的实现？

堆栈常用一维数组或链表来实现。
堆栈使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

• 推入：将数据放入堆栈顶端，堆栈顶端移到新放入的数据。
• 弹出：将堆栈顶端数据移除，堆栈顶端移到移除后的下一笔数据。

Stack在算法题中的作用

由于栈后进先出的特性，常被用于匹配类型的问题上，常见的匹配类型我总结如下：

1.  找到相邻配对元素操作

   典型的例题为 leecode 1047和leecode 20，都可以通过栈来匹配最后节点与当前节点是否匹配来完成。

2.  找到数组中递增或递减位置序列

   典型的例题为 leecode 84，leecode 42和leecode 239，可以通过栈的这种特性以O(N)复杂度完成。

Stack特殊场景下变形

当遇到相邻元素配对问题，我们会第一时间想到栈这个数据结构。但是当我们发现栈中的元素只有一种的情况下，可以对这个栈再做简化，方法为使用一个int来记录这个内容的数量，通过加法模拟栈的push操作，减法模拟栈的pop操作，从而模拟整个栈的操作，这样可以进一步优化性能。
典型例题：leecode 1021

数据结构和算法知识脑图

链接如下：
https://www.yuque.com/james_ren/algorithm/mindmap