uct StackNode *next; //指针域 }StackNode,*LinkStackPtr; //链栈结构 typedef struct LinkStack { LinkStackPtr top; //链栈头结点 int count; //结点个数 }LinkStack;
(2)链栈的进栈操作 算法思想： a.先为新结点s开辟一段空间，空间的大小为结点结构大小; b.将要插入的元素值e赋值给新结点s的数据域; c.将原来的栈顶元素赋值给新结点s的后继 d.使栈顶指针指向新结点e e.链栈元素增1 实现：插入元素e为新的栈顶元素
Status Push(LinkStack *S,SElemType e)
{
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); //开辟一个新的结点空间，大小为结构体StackNode大小
s->data=e; //将元素e赋值给新结点s的数据域
s->next=S->top;//把当前的栈顶元素赋值给新结点的直接后继
S->top=s; //将新的结点s赋值给栈顶指针
S->count++;//链栈元素数目加1
return OK;
}
(3)链栈的出栈操作 算法思想： a.首先判定链栈是否为空栈 b.将栈顶指针指向元素数据域数据赋值给e c.将栈顶指针原先指向的元素赋值给p d.再将栈顶指针指向后一个结点，释放p e.链栈元素数目减1 实现：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmty(*S)) //若空栈
return ERROR;
*e=S->top->data; //将栈顶元素数据赋值给指针变量e指向空间
p=S->top; //将栈顶指针指向的结点(栈顶元素)赋值给p
S->top=S->top->next; //使得栈顶指针下移一位，即此时栈顶指针指向后一个结点
free(p); //释放结点p
S->count; //链栈元素数目减1
return OK;
} 3.性能分析 (1)时间复杂度:栈的顺序结构和链式结构均为O(1); (2)空间复杂度 栈的顺序结构只有数据域，空间复杂度小，但事先需要确定一个固定的长度，可能会存在内存空间浪费问题； 栈的链式存储结构每个元素具有数据域和指针域，空间复杂度稍复杂，同时也增加了一些内存开销，但对于栈的长度无限制。 (3)如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈；反之，如果它的变化在可控范围内，建议使用顺序栈性能会更高些。