自己实现集合框架(十三):链式栈的实现
一.链式栈
采用链式储存结构的栈叫做链式栈，采用单链表来实现。单链表的第一个结点为栈顶结点，设top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新的结点；出栈操作是删除当前栈顶结点并返回栈顶元素值，再使top指向新的栈顶结点。链式栈的空栈(a)，入栈操作(b)和出栈操作(c)如下图示所示：
二.链式栈的实现
1. 定义链式栈
前面文章自己实现集合框架(十一):栈接口定义介绍了栈接口的定义，链式栈类LinkedStack实现栈接口SStack，并实现栈接口中定义的方法，代码如下所示：
代码解释：
① 链式栈实现栈接口类
SStack，但不能继承前面实现的单链表类SinglyLinkedList，因为栈不支持线性表在任意位置的插入和删除操作。
2. 判断栈是否为空
代码解释
① 链式栈是否为空栈的依据是判断栈顶结点是否为空。
3. 入栈
代码解释：
①
top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新的结点。
4.出栈
代码解释：
① 出栈操作是删除当前栈顶结点并返回栈顶元素值，再使
top指向新的栈顶结点。
5. 取栈顶元素值
6.重写toString()方法
三. 测试
运行结果如下图所示：
四.时间复杂度分析
栈的入栈，出栈操作都在栈顶进行，不需要遍历单链表，所以栈的入栈操作push()，出栈操作pop()和取栈顶元素get()的时间复杂度都是O(1)。