持续分享嵌入式技术，操作系统，算法，c语言/python等，欢迎小友关注支持

上篇文章我们介绍了栈的定义以及顺序栈的相关知识点，大家知道顺序栈跟顺序表很类似，那么链式栈是不是跟链表很类似呢，答案是yes！

链式栈的定义

链式栈：采用链接存储的栈结构

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行；栈顶指针Top就是链表的头指针。

我们把链表的head结点当成是栈顶指针，下面两张图就是两者的区别。

从上图我们可以看出栈链的数据都是只能在栈顶结点插入的。

链式栈的相关操作

数据结构如下

typedef int datatype;
typedef struct node
{
  datatype info;
  struct node *next;
}linknode;
typedef linknode * linkstack;
linkstack top；

取得链式栈的栈顶结点

datatype read(linkstack top)
{
  if(!top) {
  	printf("\n链式栈是空的!");
  exit(1);}
  	return (top->info);
}

向链式栈中插入一个值为x的结点

linkstack push(linkstack top,datatype x)
{
  linkstack p;
  p=(linkstack )malloc(sizeof(linknode));
  p->info=x; 
  p->next=top;
  top=p; 
  return top;
}

删除栈顶元素

linkstack pop (linkstack top)
{
  linkstack p;
  if (top==NULL){ 
    printf("\n顺序栈是空的!\n");
  	return top;
  }
  p=top;
  top=top->next; 
  free(p);
  return top;
}

顺序栈和链栈的比较

时间性能：相同，都是常数时间O(1)。

空间性能：

• 顺序栈：有元素个数的限制和空间浪费的问题。
• 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。

总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。

好了，以上就是链式栈的相关介绍，本章内容就介绍到这里，下一讲我们来讲解一下对列的相关知识点。

如果觉得这篇文章对你有帮助，请点赞关注下。如有错误欢迎指正