一.栈(Stack)
栈是一种用于存储数据的简单数据结构(与链表类似) , 栈的关键就是入栈的次序 , 比如我们在交作业的时候 , 最先交的永远都在最后面 , 而老师检查的时候是从最上面开始拿 , 所以第一个交的作业老师最后一个看完
栈是一个有序的线性表 , 只能在表的一端(称为栈顶 , top)执行插入和删除操作 , 最后插入的元素将被第一个删除 , 所以栈也被称为后进先出(Last In First Out : LIFO)或者是先进后出(First In Last Out : FILO)线性表
两个改变栈操作都有专用名称 , 一个称为入栈(push) , 表示在栈中插入一个元素 , 一个称为出栈(pop) , 表示从栈中删除一个元素 , 在对一个空栈执行出栈操作时被称为下溢(underflow) , 相反 , 对一个满栈执行入栈操作时被称为溢出(overflow) , 通常 , 下溢和溢出均认为是异常, 下图是一个栈的例子
1.栈的实现方式
基于简单数组实现
基于动态数组实现
基于链表实现
1.1 基于数组实现
如下图所示 , 从左到右向数组中添加所有元素 , 并定义一个变量来记录栈顶的位置(栈顶在任意一端都可以 , 也就是在数组的尾部或者头部都可以)
当数组存满元素时 , 执行入栈操作将抛出栈满异常 , 当对一个没有存储栈元素的数组执行出栈(删除元素)操作时 , 将抛出栈空异常
时间复杂度分析
如果使用表头作为栈顶 : 入栈操作(push())时间复杂度为O(1)出栈操作(pop())时间复杂度为O(1)
如果使用表尾作为栈顶 : 入栈操作(push())和出栈操作(pop())时间复杂度为O(1)
删除栈的时间复杂度 : O(1)
局限性
栈的最大空间必须预先声明 , 试图对一个满栈执行插入操作将产生一个针对简单数组这种特定实现栈方式的异常
1.2 基于动态数组实现
基于数组的实现方式存在的问题就是在固定大小的数组中 . 如何处理所有空间都已经保存了栈元素这种情况
数组 . 动态数组 , 链表 , 双向链表 , 循环结构 : 数据结构之顺序存储结构和链式存储结构分析 , 图文并茂 , 又涨姿势了
ArrayList底层也是使用动态数组实现 : java框架集合List子接口之ArrayList源码剖析
解决方法1
当栈满时 , 每次将数组的大小增加 1
弊端
这种做法会导致开销太大 , 当栈满后 , 新建一个长度为旧数组长度 + 1的数组 , 然后把旧数组的值拷贝到新数组 , 在新数组添加末尾元素 , 不管是从空间复杂度的角度还是时间复杂度来说每次都需要新建数组 , 拷贝元素 , 开销都是比较大的
解决方法2
我们可以使用和数组倍增来解决方法1的频繁扩容问题 , 当栈满时 , 我们可以新建一个旧数组大小长度1倍的新数组 , 然后拷贝元素
弊端
倍增太多可能导致内存溢出
时间复杂度分析
如果使用表头作为栈顶 : 入栈操作(push())为O(N)出栈操作(pop())时间复杂度为O(1)
如果使用表尾作为栈顶 : 出栈操作(pop())时间复杂度为O(1) , 入栈操作(push())如果不考虑扩容的情况下为O(1) , 如果考虑扩容的情况为O(N)
删除栈的时间复杂度 : O(1)
1.3 基于链表实现
使用链表也可以实现栈 , 通过在表头/表尾添加元素实现入栈操作 . 通过删除表头/表尾节点(栈顶)来实现出栈操作
时间复杂度分析
如果链表的表头为栈顶 : 入栈操作和出栈操作时间复杂度为O(1)
如果链表的表尾为栈顶 : 入栈时间复杂度 : O(N) , 出栈时间复杂度O(1)
删除栈时间复杂度 : O(N)
1.4 栈的各种实现方式比较
递增策略和倍增策略
递增策略 : 实现push()操作的时间复杂度平均为O(N)
倍增策略 : 实现push()操作的时间复杂度平均为O(1)
基于数组实现的栈和基于链表实现的栈
基于数组实现 :
各个操作都是常数时间开销
每隔一段时间倍增操作的开销较大
n个操作的的任意序列平均复杂为O(N)
基于链表实现 :
栈规模的增加和减少都很简洁
各个操作都是常数的开销
每个操作都需要额外的时间和空间来处理指针
