链栈的表示和实现

链栈的存储结构

//------链栈的存储结构------
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack; 

链栈的初始化

//链栈的初始化
Status InitStack(LinkStack &S){
    //构造一个空栈S，栈顶指针置空 
    S = NULL;
    return OK;
} 

链栈的入栈

（1）为入栈元素e分配空间，用指针p指向。
（2）将新结点数据域置为e。
（3）将新结点插入栈顶。
（4）修改栈顶指针为p。

//链栈的入栈
Status Push(LinkStack &S, SElemType e){
    //在栈顶插入元素e 
    p = new StackNode;  //生成新结点 
    p -> data = e;      //将新结点数据域置为e 
    p -> next = S;      //将新结点插入栈顶 
    S = p;              //修改栈顶指针为p 
    return OK;
} 

链栈的出栈

（1）判断栈是否为空，若空则返回ERROR。
（2）将栈顶元素赋给e。
（3）临时保存栈顶元素的空间，以备释放。
（4）修改栈顶指针，指向新的栈顶元素。
（5）释放原栈顶元素的空间。

//链栈的出栈
Status Pop(LinkStack &S, SElemType &e){
    //删除S的栈顶元素，用e返回其值 
    if(S == NULL){      //栈空 
        return ERROR;
    }
    e = S -> data;      //将栈顶元素赋给e 
    p = S;              //用p临时保存栈顶元素空间，以备释放 
    S = S -> next;      //修改栈顶指针 
    delete p;           //释放原栈顶元素的空间 
    return OK;
} 

取链栈的栈顶元素

与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变。

//取链栈的栈顶元素
SElemType GetTop(LinkStack S){
    //返回S的栈顶元素，不修改栈顶指针 
    if(S != NULL){         //栈非空 
        return S -> data;  //返回栈顶元素的值，栈顶指针不变 
    }
}