栈的链式结构(C语言实现)

是不是很奇怪,和线性表不同,栈的运算方向是确定的那为什么还要区分顺序结构和链式结构呢。其实这是从内存来考虑的。采用链栈不必预先估计栈的最大容量,只要系统有可用空间,链栈就不会出现溢出。采用链栈时,栈的各种基本操作的实现与单链表的操作类似,对于链栈,在使用完毕时,应该释放其空间。

链栈的结构可用 C 语言定义如下:

typedef struct node 
{ 
    StackElementType  data;           
    struct node   *next; 
}LinkStackNode; 

typedef  LinkStackNode  *LinkStack; 

关于链栈的初始化,其实可以参考之前线性表的链式结构,区别不大。至于存入和弹出的操作,由于涉及指针操作,和顺序结构还是有很大不同的。不过理解的要点还是一样,就是考虑top指针的位置以及指向。(个人的理解是把top指针理解为线性表的头指针差不多)

//进栈操作 
int Push(LinkStack top, StackElementType x) 
/* 将数据元素 x 压入栈 top 中 */   
{ 
    LinkStackNode * temp; 
    temp=(LinkStackNode * )malloc(sizeof(LinkStackNode));  
    if(temp==NULL)  
          return(FALSE);   /* 申请空间失败 */  
    temp->data=x;
    temp->next=top->next; 
    top->next=temp;   /* 修改当前栈顶指针 */  
    return(TRUE); 
} 

//出栈操作 
int Pop(LinkStack top, StackElementType *x) 
{  /* 将栈 top 的栈顶元素弹出,放到 x 所指的存储空间中 */ 
      LinkStackNode * temp;
      temp=top->next; 
      if(temp==NULL)  /*栈为空*/      
         return(FALSE); 
      top->next=temp->next; 
      *x=temp->data; 
       free(temp);   /* 释放存储空间 */ 
      return(TRUE); 
} 

如果要操作多栈,其实只需要搞一个指针数组,然后每个格子里装一个栈的top指针就可以了。