本质上是一种特殊的数据结构。它的结构很特别。它与数组和链表不同的是，它的数据入出规则是：先进先出，后进先出。由于其特殊性，一般用于特定场景，如浏览器的前进后退效果。浏览器的特点是：我们可以访问之前访问过的网站，也可以访问后面的网站。浏览器的这一特性与堆栈结构完美匹配。我们只需要用到两个栈，分别代表浏览器的前向访问和后向访问。当一个数据集只涉及一端的插入和删除数据，并且满足先进后出和后进先出的特性时，那么我们首先应该想到栈，看看它是否能更好的实现我们需要的场景。实现方法栈的实现方法有两种，一种是基于数组的实现，称为顺序栈；另一种是基于链表实现的，称为链栈。这两种实现之间没有太大区别。实现后入栈和出栈的时间复杂度为O(1)。不同之处在于，基于数组的堆栈消耗的内存更少，因为它不需要保存额外的指向它的指针。但是基于数组还有一个额外要做的事情就是如果你需要实现一个可变大小的栈，它需要实现动态扩展，这是所有基于数组实现的必修课。接下来，让我们实现一个基于数组的顺序堆栈。为了降低复杂度，不考虑扩展。//基于数组的顺序栈ArrayStack(privatevaln:Int){privatevalitems=arrayOfNulls(n)//栈数组privatevarcount=0//当前栈的大小//Pushfunpush(item:String):Boolean{//数组空间不足，直接返回false，入栈失败if(count==n)returnfalse//将item放在count的下标处，count加oneitems[count]=item++countreturntrue}//弹出funpop():String?{//如果栈为空，直接返回nullif(count==0)returnnull//返回下标为count-1的数组元素，栈中元素个数为count减一valtmp=items[count-1]--countreturntmp}}根据上面的实现，我们很容易得出入栈出栈的时间复杂度为O(1)。另一方面，由于没有额外的空间分配，栈的空间复杂度为O(1)。Expansion上面我们实现了一个固定的顺序栈，也就是说在初始化的时候已经指定了栈的大小。当栈满了，就不可能再往栈中添加数据了。当然，基于链表的链栈没有这个限制。为了解决顺序栈的这个限制，我们需要对数据进行扩展，这在数组部分也有提到。因此，如果我们要实现一个支持扩展的栈，只需要依赖一个基于扩展的数组即可。具体扩展示意图如下：具体代码实现了可查看数据的扩展。下面我们分析一下基于数组展开的栈的时间复杂度。首先，当没有达到栈的大小时，这个阶段和固定顺序栈一样，进出的时间复杂度都是O(1)。当数据为K，达到扩容临界点时，需要将数组扩容到原来的2倍，将之前的数据复制到新的数组中；该阶段消耗的时间复杂度为O(K)。扩容完成后，继续入栈出栈，此时的时间复杂度为O(1)。当再次达到2k时，需要再次扩容，将数据复制到新的数组中。此时消耗的时间复杂度为O(2k)。反复重复以上步骤。这是支持扩展的顺序栈时间复杂度的变化。也就是说最好情况的时间复杂度是O(1)；最差的时间复杂度是O(n)。那么平均时间复杂度呢？还记得算法之旅：复杂度分析中提到的摊销时间复杂度吗？接下来，我们将使用摊销时间复杂度来分析其平均时间复杂度。其实看一张图就可以理解摊销时间复杂度的算法。每次我们把膨胀消耗的时间分配给后面的堆叠。分配前入栈需要一个入栈时间；分配后，在推送时间上加上一个数据移动时间入栈。push和move的时间复杂度是O(1)。因此，摊销后整个栈的时间复杂度为O(1)，即栈的平均复杂度为O(1)。栈的应用既然我们已经对栈有了全面的了解，那么要想充分巩固栈的数据结构，剩下的就是通过实践来达到熟悉了。例如：实现一个基本的计算器来计算一个简单的字符串表达式的值，字符串表达式可以包含左括号（、右括号）、加号+、减号-、非负整数和空格。基于表达式的操作非常符合栈的结构，我们可以使用栈来实现。实现思路如下：通过设置一个符号位，将所有运算转换为加法。遇到一个数，就加上前面的符号位，然后用前面的结果进行加法运算。遇到'('时，保留前面的符号位和结果入栈，然后重复1和2步计算括号内的值。遇到')'取出保留的符号位和结果，加到当前result/***O(n)*/funcalculate(s:String):Int{valnumberStack=Stack()varsign=1//符号位varresult=0varindex=0while(index
