什么是链式栈介绍

链式栈是一种数据存储结构，可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

链式栈介绍

栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底（push），最后的数据在栈顶（top），需要读数据的时候从栈顶开始弹出数据（top）最后一个数据被第一个读出来。链式栈中的元素以Node的形式存储，节点Node中存有此节点存于栈中的元素以及指向下个节点的指针。链式栈的数据成员只用保存指向栈顶节点的指针 *top_node。

顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用光而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用；而对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间开始，另外当某个项不使用时也可将内存返还给系统。

链式栈代码

1、链式栈的类型定义

typedef struct node{       datatype data;               struct node * next;     }linkStack;                 

2、判断空栈

int StackEmpty(linkStack *top){       return (top?0:1);}//返回0，则不为空。

3、取栈顶元素

datatype GetTop(linkStack *top){              if(!top)              {                printf(\"/n链表是空的!\");                return 0;                    }              return top->data;}

4、入栈

//入栈linkStack *Push(linkStack *top,datatype x){       linkStack *p;       p=(linkStack *)malloc(sizeof(linkStack));//分配空间       p->data=x;                p->next=top;              top=p;                    return top;}

5、出栈

//出栈linkStack *Pop(linkStack *top){       linkStack *p;       if(!top)       {              printf(\"/n链栈是空的!\");              return NULL;       }  //判断是否为空栈n       p=top;  //指向被删除的栈顶       top=top->next; //修改栈顶指针       free(p);       return top;}