第三章栈和队列——栈的链式存储表示（4）

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 }