数据结构之链栈

数据结构之链栈

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;

栈作为一种独特的线性数据结构，其与线性表的顺序存储和链式存储在结构上存在差异。在栈中在带链的栈中,栈顶指针的动态变化，无论是采用顺序存储还是链式存储，插入和删除操作都是在表的同一端完成的。在栈的长度变动较小的情况下数据结构之链栈，为了节省存储空间，宜选用顺序存储结构；而若栈的长度波动较大，难以准确预知其存储需求时，则应采用动态链表作为存储方式。链栈无需在头部添加额外的头结点，因为栈的所有操作都是在头部进行的，若添加头结点，则意味着需要对头结点之后的节点进行操作，这反而会增加算法的复杂性。