数据结构之链栈
数据结构之链栈
2、链栈
链栈是一种特殊形式的单链表，它仅允许在表头进行插入和删除操作。链栈可以具备头节点，也可以不包含头节点。
栈的结构采用链表形式呈现，其中链表（不含头结点）的首个指针指向s，这表明s是栈顶位置，而链表的最后一个节点则对应栈底。
初始化阶段在带链的栈中,栈顶指针的动态变化，s变量被赋值为NULL，即无头结点；随后，通过malloc函数分配LStack结构体的大小，并将结果赋值给s，此时s指向一个带有头结点的栈结构；s的头结点指针被设置为NULL。
栈顶指针可以通过变量s（若未设置头结点）或s->next（若设置了头结点）来访问，而栈顶数据的访问则分别通过s->data（若未设置头结点）或s->next->data（若设置了头结点）来实现。
栈为空的条件是s为空（无头节点）或者s的下一个节点为空（有头节点）。
进栈操作和出栈操作与单链表在开始结点的插入和删除操作一致。
栈的链式存储结构的C语言描述
#include
#include
typedef int ElemType;
typedef struct stnode{
ElemType data;
struct stnode *next;
}LStack;
2.3、链栈基本函数算法描述
注：以上程序在VC6.0+WIN2K下测试通过。
2.3.1、初始化
void initstack(LStack **s)
*s=NULL;
2.3.2、入栈
定义函数push，其参数为指向指针的指针s和元素类型x在带链的栈中,栈顶指针的动态变化，用于向栈中插入元素。
动态分配了LStack结构体大小的内存空间，并将该空间的首地址赋值给指向LStack类型的指针变量p。
p->data=x;
p->next=*s;
*s=p;
return 1;
2.3.3、出栈
定义一个名为pop的函数，该函数接受两个参数：一个指向指针的指针s，一个指向元素类型数据的指针x。
LStack *p;
if(s==NULL)
printf("underflow/n");
return 0;
else
p=*s;
*s=(*s)->next;
*x=p->data;
free(p);
return 1;
2.3.4、读取栈顶元素
实现获取栈顶元素的功能，函数名为gettop，它接受一个指向LStack类型的指针s和一个指向ElemType类型的指针x。
if(s==NULL)
printf("underflow/n");
return 0;
else
*x=s->data;
return 1;
2.3.5、判栈空
int isempty(LStack *s)
if(s==NULL)
return 1;
else
return 0;
2.3.6、显示链栈中的所有元素
执行函数ShowLinkStack，传入链表栈指针s。
while(s!=NULL)
输出信息显示，栈内各元素按顺序排列为：%d数据结构之链栈，具体数值如下。
s=s->next;
2.3.7、测试程序
int main()
LStack *s;
ElemType x;
initstack(&s);
if(isempty(s))
printf("此栈为空/n");
push(&s,1);
push(&s,2);
push(&s,3);
ShowLinkStack(s);
gettop(s,&x);
printf("栈顶元素为:%d/n",x);
pop(&s,&x);
printf("弹出的元素为:%d/n",x);
pop(&s,&x);
printf("弹出的元素为:%d/n",x);
ShowLinkStack(s);
gettop(s,&x);
printf("栈顶元素为:%d/n",x);
return 0;
栈作为一种独特的线性数据结构，其与线性表的顺序存储和链式存储在结构上存在差异。在栈中在带链的栈中,栈顶指针的动态变化，无论是采用顺序存储还是链式存储，插入和删除操作都是在表的同一端完成的。在栈的长度变动较小的情况下数据结构之链栈，为了节省存储空间，宜选用顺序存储结构；而若栈的长度波动较大，难以准确预知其存储需求时，则应采用动态链表作为存储方式。链栈无需在头部添加额外的头结点，因为栈的所有操作都是在头部进行的，若添加头结点，则意味着需要对头结点之后的节点进行操作，这反而会增加算法的复杂性。
