链栈的表示和实现

准备工作

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>

//函数结果状态字符
#define TRUE  1 
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE   -1
#define OVERFLOW     -2

链栈是运算受限的单链表，只能在链表头部进行操作

1.链表的头指针就是栈顶

2.不需要头结点

3.基本不存在栈满的情况

4.空栈相当于头指针指向空

5.插入和删除仅在栈顶处执行

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;

链栈的初始化

void InitStack(LinkStack &S)
{
    //构造一个空栈
    S = NULL;
    return OK;
}

判断链栈是否为空

Status StackEmpty(LinkStack S)
{
    if(S==NULL) return TRUE;
    else return FALSE;
}

链栈的入栈（头插法）

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

链栈的出栈

Status Pop(LinkStack &S, SElemType &e)
{
    if(S==NULL)  return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

取栈顶元素

SElemType GetTop(LinkStack S)
{
    if(S!=NULL)
    return S->data;
}