3.4 的链式存储结构★3◎3

3.4 栈的链式存储结构★3◎3　　同样地，我们也可以采用线性链表来表示栈，如图3-3所示。　　以带头结点的单链

作者

次阅读

2010-11-17

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)。