链栈:栈的链式存储结构

链栈的结构体定义
服务器君一共花费了283.919 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

前面讲完了栈的顺序存储结构,我们现在来看看栈的链式存储结构,简称为链栈

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。

  • 栈是用栈顶来做插入和删除操作,那么对于链栈的栈顶放在链表的头部还是尾部呢?
  • 单链表有头指针,而栈顶指针也是必须的,那干吗不让它俩合二为一呢,所以比较好的办法是把栈顶放在单链表的头部。另外,都已经有了栈顶在头部了,单链表中比较常用的头结点也就失去了意义,通常对于链找来说,是不需要头结点的。

所以链栈的结构是这样的:

  • 对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间,如果真的发生,那此时的计算机操作系统已经面临死机崩溃的情况,而不是这个链栈是否溢出的问题。

但对于空栈来说,链表原定义是头指针指向空,那么链栈的空其实就是 top=NULL 的时候。

链栈的结构

  • 对于栈来说,结构体定义需要定义两部分。一个是 top 指针,一个是存储数据。那么链栈又应该如何设计结构体呢?
  • 与顺序栈有点区别,我们先看看以前单链表的结构体吧。

单链表的结构体定义:

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */

链栈其实也是个链表,所以可以参考它的实现,栈的结点定义为:

/* 链栈结构 */
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode,*LinkStackPtr;

以上是链栈的一个结点定义,但是我们还需要加入一个栈顶指针,所以完整的定义为:

typedef int Status;
/* SElemType类型根据实际情况而定,这里假设为int */
typedef int SElemType;

/* 链栈结构 */
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode,*LinkStackPtr;

typedef struct
{
    LinkStackPtr top;
    int count;
} LinkStack;
  • 这里怎么多声明了一个变量 count?用来干什么的吗?
  • 记录栈中元素个数,也可以将元素个数属性放在LinkStack类型中定义。

结构体定义完毕之后,后面就可以通过编程来熟悉链栈的操作了。

延伸阅读

此文章所在专题列表如下:

  1. 栈的定义与大概理解
  2. 栈的抽象数据类型ADT
  3. 顺序栈:栈的顺序存储结构
  4. 顺序栈的进栈操作
  5. 顺序栈的出栈操作
  6. 获取顺序栈的栈顶元素
  7. 链栈:栈的链式存储结构
  8. 链栈的进栈操作
  9. 链栈的初始化与遍历
  10. 链栈的出栈操作
  11. 链栈的置空操作与判断链栈是否为空
  12. 为什么要使用栈这种数据结构
  13. 递归,栈的重要应用之一
  14. 栈是如何实现递归的
  15. 接触后缀表达式(逆波兰表示法)
  16. 图解后缀表达式的计算过程
  17. 将中缀表达式转化为后缀表达式
  18. 开始学习队列这个数据结构
  19. 队列的抽象数据类型ADT
  20. 顺序队列:队列的顺序存储结构
  21. 顺序队列的入队操作
  22. 顺序队列的出队操作
  23. 顺序队列置空与判断操作
  24. 队列顺序存储结构的不足
  25. 关于循环队列的一些讲解
  26. 链队列:队列的链式存储结构
  27. 链队列的初始化操作
  28. 链队列的入队操作
  29. 链队列的出队操作
  30. 补完链队列的其它常见操作
  31. 循环队列与链队列的优劣势

本文地址:http://www.nowamagic.net/librarys/veda/detail/2290,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2290

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《高性能JavaScript》 Nicholas C. Zakas (作者), 赵泽欣 (合著者), 丁琛 (译者)

《高性能JavaScript》揭示的技术和策略能帮助你在开发过程中消除性能瓶颈。你将会了解如何提升各方面的性能,包括代码的加载、运行、DOM 交互、页面生存周期等。雅虎的前端工程师 Nicholas C. Zakas 和其他五位 JavaScript 专家介绍了页面代码加载的最佳方法和编程技巧,来帮助你编写更为高效和快速的代码。你还会了解到构建和部署文件到生产环境的最佳实践,以及有助于定位线上问题的工具。如果你使用 JavaScript 构建交互丰富的 Web 应用,那么 JavaScript 代码可能是造成你的Web应用速度变慢的主要原因。

更多计算机宝库...