浅析算法之旅：栈

当某个数据集合只涉及在一端插入和删除数据，并且满足先进后出，后进先出的特性，这时我们应该首先想到的是栈，看它是否能够更好的实现我们所需的场景。

实现方式栈的实现方式有两种，一种是基于数组的实现方式，称为顺序栈;另一种是基于链表的实现方式，称为链式栈。

这两种实现方式区别不是很多，实现之后栈的出入时间复杂度都是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)。

扩容上面我们实现的是一个固定的顺序栈，也就是说初始化的时候已经指定了栈的大小，当栈满了的时候，无法进行向栈中添加数据。当然基于链表的链式栈没有这种限制。

为了解决顺序栈的这种限制，我们需要对数据进行扩容操作，这在数组那一节也有提及过。

所以，如果要实现一个支持扩容的栈，我们只需底层依赖一个基于扩容的数组即可。

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!