目录

一、基本概念

1.定义

2.优点

二、链栈的表示

 三、链栈的基本操作

 1.创建空链栈

 2.链栈的判空操作

 3.链栈的入栈操作

 4.链栈的出栈操作

 5.取链栈的栈顶元素

一、基本概念

1.定义

栈可以采用链接的方式表示，把栈组织成一个单链表，这种数据结构称为链接栈。即采用链式存储的栈称链栈。

2.优点

便于多个栈共享存储空间和提高效率，且不存在栈上溢的情况 。

二、链栈的表示

类似于单链表，可以把栈直接定义为指向栈结点的指针，这个指针同时也是栈顶指针。

为了强调栈顶是栈的一个属性，对栈进行了封装，引入了LinkStack结构。

typedef int ElemType;struct Node {      //单链表节点定义ElemType data; //数据域struct Node* next;    //指针域};struct LinkStack { //链栈类型定义struct Node* top;};typedef struct LinkStack* PLinkStack; //链栈类型的指针类型

 三、链栈的基本操作

1.创建空链栈

类似于单链表的创建。动态申请一个栈顶结点内存，并使栈顶指针指向空，表示创建的栈为空栈。

PLinkStack CreateLinkStack(void){PLinkStack plstack = (PLinkStack)malloc(sizeof(struct LinkStack));  //申请一个节点空间if (plstack == NULL)  //节点申请失败，返回空指针{return NULL;}plstack->top = NULL;  //申请成功，栈顶指针为空return plstack;//返回空链栈}

 2.链栈的判空操作

栈顶指针指向空，表示栈空。

bool EmptyLinkStack(PLinkStack plstack){return (plstack->top == NULL); //判断栈顶指针是否为空}

 3.链栈的入栈操作

不用担心链栈已满，上溢的问题，因为链表不存在这个问题。

在栈顶插入元素，即在单链表的表头插入元素。动态申请一个结点，存入数据后，插入队头（即单链表的表头），再把栈顶指针指向新插入的结点。

bool Push(PLinkStack plstack, ElemType e){struct Node* p = (struct Node*)malloc(sizeof(struct Node));if (p == NULL)      //申请新节点空间失败{return false;}//不用判断栈是否已满p->data = e;p->next = plstack->top;   //新节点连接到链栈栈顶指针之后，plstack->top = p;  //链栈栈顶指针指向新增节点return true;}

 4.链栈的出栈操作

与入栈操作不同之处在于，链栈的出栈操作需要判断是否栈空（即top == NULL)。

栈不空时，先用e存储栈顶元素，再让栈顶指针指向栈中的第二个结点，最后释放第一个结点的内存空间。

bool Pop(PLinkStack plstack, ElemType* e){struct Node* p;if (plstack->top == NULL)  //链栈为空，报错{return false;}*e = plstack->top->data;  //e记录出栈的元素p = plstack->top;  //p指向第一个节点plstack->top = p->next;   //栈顶指针指向第二个接点free(p);    //释放出栈节点的内存空间return true;}

 5.取链栈的栈顶元素

与链栈的出栈操作类似，不同在于不用修改栈顶指针。

bool GetTopElem(PLinkStack plstack, ElemType* e){if (plstack->top == NULL)  //链栈为空，报错{return false;}*e = plstack->top->data;   //e记录栈顶的元素return true;}

 The life of a man is the process of trying.

The more one tries, the better his life will be.