1 栈的链式表示

栈的链式存储结构称为链栈，是运算受限的单链表。

其插入和删除操作只能在表头位置上进行。

因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。

 

 

 

 

 

 

 

1 链栈的结点类型说明如下：
2 typedef  struct  Stack_Node
3 {  ElemType   data ;
4 struct Stack_Node  *next ;
5 } Stack_Node ;

2 链栈基本操作的实现

1 (1) 栈的初始化
2 Stack_Node  *Init_Link_Stack(void)
3 {    Stack_Node  *top ;
4 top=(Stack_Node  *)malloc(sizeof(Stack_Node )) ;
5 top->next=NULL ; 
6 return(top) ;
7 }

 1 压栈(元素进栈)
 2 Status push(Stack_Node *top , ElemType  e)
 3 {   Stack_Node  *p ;
 4 p=(Stack_Node  *)malloc(sizeof(Stack_Node)) ; 
 5 if (!p)  return  ERROR; 
 6 /*  申请新结点失败，返回错误标志 */
 7 p->data=e ; 
 8 p->next=top->next  ; 
 9 top->next=p ;    /*  钩链  */
10 return OK;
11 }

 

 1 弹栈(元素出栈)
 2 Status pop(Stack_Node  *top , ElemType *e)
 3 /*  将栈顶元素出栈  */
 4 {   Stack_Node  *p ;
 5 ElemType  e ;
 6 if  (top->next==NULL )
 7 return ERROR ;    /*  栈空，返回错误标志    */
 8 p=top->next ; e=p->data ;    /*  取栈顶元素  */
 9 top->next=p->next ;     /*  修改栈顶指针  */
10 free(p) ; 
11 return OK ;
12 }