栈是一种独特的数据结构，其主要特点在于数据的进出规则：先进后出（LIFO），与数组和链表有显著区别。
由于这种特性，栈通常用于特定场景，例如浏览器的前进与回退功能。
在浏览器中，用户可以向前访问之前的网站，也可以向后访问后续的网站。
这一特性与栈的结构非常契合，我们可以用两个栈分别表示浏览器的前进和后退。
当某些数据集合只需要在一端进行插入和删除操作，并且遵循先进后出原则时，栈是首选的数据结构，可以更有效地实现需求。
栈的实现方式有两种：基于数组的顺序栈和基于链表的链式栈。
这两种实现方式的区别不大，经过实现之后，栈的进出操作时间复杂度都是O(1)。
基于数组的栈内存消耗较少，因为它不需要额外的指针来保存数据。
但使用数组实现时，若需动态调整栈的大小，则必须实现扩容，这是所有数组实现的必要步骤。
接下来，我们将实现一个固定大小的顺序栈，暂不考虑扩容的情况。
// 基于数组实现的顺序栈claSS ARRaYstack(pRivate val n: Int) { pRivate val ITeMs = aRRayOfNulls(n) // 栈数组 pRivate vaR count = 0 // 栈的当前大小 // 入栈 fun pUSh(ITeM: StRing): Boolean { // 数组空间不够了，直接返回FAlse，入栈失败 if (count == n) RetuRn FAlse // 将ITeM放到下标为count的位置，并且count加一 ITeMs[count] = ITeM ++count RetuRn tRue } // 出栈 fun POP(): StRing? { // 栈为空，则直接返回null if (count == 0) RetuRn null // 返回下标为count-1的数组元素，并且栈中元素个数count减一 val tMp = ITeMs[count – 1] –count RetuRn tMp }
通过上述实现，我们可以得出栈的进出时间复杂度为O(1)。
另一方面，由于没有额外的空间申请，栈的空间复杂度为O(1)。
扩容方面，我们实现的是一个固定大小的顺序栈，即初始化时已指定栈的大小，栈满时无法添加更多数据，而基于链表的链式栈则没有此限制。
为了解决顺序栈的这一局限性，我们需要对数据进行扩容操作，这在数组章节中已有提及。
因此，要实现一个支持扩容的栈，只需依赖于一个可以扩容的数组即可。
以下是扩容的示意图：
具体的代码实现可参考数据的扩容部分。
接下来，我们分析基于数组扩容的栈的时间复杂度。
在栈未达到指定大小时，其出入操作的时间复杂度与固定顺序栈相同，均为O(1)。
当数据达到K并触及扩容临界点时，需要将数组大小扩展至原来的两倍，并将数据复制到新数组中，此时消耗的时间复杂度为O(K)。
扩容后继续进出栈时，时间复杂度恢复为O(1)。
当再次达到2K时，需再次扩容并复制数据，此时消耗时间复杂度为O(2K)。
这一过程会不断重复。
因此，支持扩容的顺序栈的时间复杂度变化如下：最佳情况为O(1)，最坏情况为O(n)。而平均时间复杂度如何呢？
在算法分析中提到的均摊时间复杂度可以帮助我们理解其平均时间复杂度。实际上，只需一张图即可清晰表达均摊时间复杂度的概念。
每次扩容所消耗的时间将分摊到后续的入栈操作中。在分摊之前，入栈需要O(1)的时间；分摊之后，入栈的时间变为O(1)加上数据移动的时间。pUSh和MOVe的时间复杂度均为O(1)。
因此，均摊后栈的整体时间复杂度为O(1)，即栈的平均复杂度为O(1)。
栈的应用现在我们已经全面了解了栈这种数据结构，为了巩固所学，接下来应通过练习达到熟悉的程度。
例如，设计一个基本的计算器来计算简单字符串表达式的值，字符串表达式可以包含左括号、右括号、加号、减号、非负整数和空格。
基于表达式的运算非常适合使用栈来实现，具体思路如下：
通过设定符号位将所有运算转化为加法。
遇到数字时，结合之前的符号位，与之前的结果执行加法运算。
遇到'(‘时，将符号位和结果保存到栈中，然后重复前面的步骤计算括号内的值。
遇到’)’时，取出之前保存的符号位和结果，与当前结果进行加法运算。
fun calculate(s: StRing): Int { val nuMbeRStack = Stack() vaR sign = 1 // 符号位 vaR Result = 0 vaR index = 0 wHile (index < s.length) { when (s[index]) { ””+”” -> { sign = 1 } ””-”” -> { sign = -1 } ””(”” -> { // 将当前结果加入栈中 nuMbeRStack.pUSh(Result) Result = 0 // 将当前符号位加入栈中 nuMbeRStack.pUSh(sign) sign = 1 } ””)”” -> { // 取出之前保留的符号位与结果，与当前结果做加法运算 Result = nuMbeRStack.POP() * Result + nuMbeRStack.POP() } ”” ”” -> { } else -> { // 计算出当前的数值，可以能为多位数 vaR cuR = s[index] – ””0”” wHile (index + 1 < s.length &aMp;&aMp; s[index + 1].isDiGit()) { cuR = cuR * 10 + (s[++index] – ””0””) } // 遇到数字带上之前的符号位，再与之前的结果做加法运算 Result += cuR * sign } } index++ } RetuRn Result}
还有一些经典的栈练习，如果能掌握这些，关于栈的算法便不再是问题。
比较含退格的字符串
棒球比赛
下一个更大元素
有效的括号
源码已上传至GitHub，欢迎自行查看。
