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

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


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

  以带头结点的单链表为例,…

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

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

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

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部