admin 
3.4 栈的链式存储结构★3◎3
同样地，我们也可以采用线性链表来表示栈，如图3-3所示。
以带头结点的单链表为例，当采用链式结构存储栈时，栈的各类操作的实现方法如表3-4所示。
表3-4 带头结点单链表实现栈
|
操作 |
实现方法 |
时间复杂度 |
| 栈初始化 | 初始化链表L；top=L； | |
| 获取栈元素数 | 遍历链表 | O(n) |
| 栈空判断 | L->next==NULL | |
| 栈满判断 | 无 | |
| 入栈时关键操作 | 在链表L头插入一个结点：ListInsert_L(L, 1, E)； Top=L不变 |
O(1) |
| 出栈时关键操作 | 删除链表L的第一个结点：ListDelete_L(L, 1, E)； Top=L不变 |
O(1) |
栈链式存储结构的特点：
（1）入栈、出栈操作的时间复杂度为常数。
（2）只要存储空间足够，就没有最大数据元素数的限制。
（3）只需头指针或头结点就可以完成栈的各类操作。
（4）在不增加新的存储空间的情况下，获取栈中元素数的算法时间复杂度为O(n)。
评论列表 人参与