栈的链式存储结构及实现
程序员文章站
2022-06-05 13:42:31
...
栈的链式存储结构,简称为链栈,如图所示:
对于链栈来说,基本不存在栈满的情况,除非内存以没有存储空间。
链栈的结构代码如下:
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack;
链栈的操作和普通的单链表类似,仅在插入和删除操作上不同。
对于链栈的的进栈push操作,代码如下:
/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, SElemType e)
{
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(Node));
s->data =e;
s->next = S->top; //首先把当前的栈顶指针赋给 新结点的直接后继
S->top = s; //然后将新的结点s赋给栈顶指针
S->count++;
return OK;
}
至于链栈的出栈pop操作,也是三个步骤。假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可。
/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(LinkStack *S, SElemType *e)
{
LinkStackPtr p;
if(StackEmpty( *S))
return ERROR;
*e = S->top->data;
p = S->top; //将栈顶结点赋值给p
S->top = S->top->next; //栈顶指针下移一位,指向后一结点
free(p); //释放p
S->count--;
return OK;
}
如果栈在使用过程中元素变化不可预料,可能会有很多个,可能又比较少,那么推荐使用链栈;反之,如果变化范围可控,那么使用顺序栈会好一些。