#数据结构 链式栈

1. 概念

链式栈LinkStack

1. 逻辑结构：线性结构
2. 物理结构：链式存储
3. 栈的特点：后进先出

栈具有后进先出的特点，我们使用链表来实现栈，即链式栈。那么栈顶是入栈和出栈的地方，单向链表有头有尾，那我们将链表的头作为栈顶还是链表的尾作为栈顶呢？如果每次在链表的尾部进行插入或删除，就需要遍历整个链表来找到尾结点即终端结点。而在头部即起始结点进行插入或删除时，仅需头指针找到链表的起始结点，而无需遍历整个链表。

所以链式栈的入栈、出栈都是通过对链表进行头插、头删来实现。

既然要对单向链表进行头插、头删，那么头结点的存在会让操作变得复杂，故我们使用无头单向链表。

无头单向链表的头就是栈顶，故栈针是指向无头单向链表的起始结点的，所以我们在链式栈中将头指针H称做栈针top。top栈针永远指向无头单向链表的第一个节点，栈空的时候除外。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。

对于空栈来说，链表即H == NULL，链式栈即top == NULL

2. 接口实现

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include <stdio.h>
#include <stdlib.h>
//入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{datatype data;//数据域struct linkstack *next;//指针域
}linkstack_t;
//1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop);
//2.入栈   data是入栈的数据
//参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data);
//3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top);
//4.出栈
datatype PopLinkStack(linkstack_t **ptop);
//5.清空栈
void ClearLinkStack(linkstack_t **ptop);//用二级指针，是因为清空后需要将main函数中的top变为NULL
//6.求栈的长度
int LengthLinkStack(linkstack_t *top);//用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top);
#endif

2.1. 定义操作链式栈的结构体

//入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{datatype data;//数据域struct linkstack *next;//指针域
}linkstack_t;

2.2. 创建空的链式栈

#include "linkstack.h"
void CreateEpLinkStack(linkstack_t **ptop)
{	//top = NULL;*ptop = NULL;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{linkstack_t *top;CreateEpLinkStack(&top);return 0;
}

2.3. 入栈

思想：

开辟新结点存放入栈数据

每次都将新结点链接到无头单向链表的头

栈针top永远指向无头单向链表的头，栈空时除外

顺序栈需要判满，但链式栈无需判满

/*2.入栈   data是入栈的数据
//参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，
//那么修改main函数中的top，我们采用地址传递*/
int PushLinkStack(linkstack_t **ptop, datatype data)
{	linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));if(NULL == pnew){printf("PushLinkStack pnew malloc failed\n");return -1;}//给新节点初始化pnew->data = data;pnew->next = *ptop;      *ptop = pnew;return 0;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{linkstack_t *top;CreateEpLinkStack(&top);int i;for(i = 0; i < 5; i++){PushLinkStack(&top,i);}return 0;
}

2.4. 出栈

顺序栈需要判空即PS->top==-1

链式栈也需要判空即top == NULL

判空无需改变主函数栈针top的指向，故无需传递top的地址。

但出栈后需要移动栈针，改变top的指向，故需要传递栈针top的地址&top。

综上，出栈函数需要传递栈针top的地址&top。

//3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{return top == NULL;
}
//4.出栈
datatype PopLinkStack(linkstack_t **ptop)
{if(IsEpLinkStack(*ptop)){printf("PopLinkStack failed\n");return -1;}datatype temp;linkstack_t *pdel = NULL;
#if 0pdel = *ptop;temp = pdel->data;*ptop = pdel->next;free(pdel);pdel = NULL;return temp;
#endif
#if 1temp = (*ptop)->data;pdel = *ptop;*ptop = (*ptop)->next;free(pdel);pdel = NULL;return temp;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{linkstack_t *top;CreateEpLinkStack(&top);int i;for(i = 0; i < 5; i++){PushLinkStack(&top,i);}
#if 0for(i = 0; i < 5; i++)	printf("%d ",PopLinkStack(&top));}printf("\n");		
#endifreturn 0;
}

4 3 2 1 0 

2.5. 栈长

问：求栈长是否需要传递栈针的地址？ 无需

问：求栈长能否传递栈针的地址？ 可以

//6.求栈的有效长度
int LengthLinkStack(linkstack_t *top)//用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
{int len = 0;while(top != NULL){len++;top = top->next;}return len;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{linkstack_t *top;CreateEpLinkStack(&top);int i;for(i = 0; i < 5; i++){PushLinkStack(&top,i);}
#if 0for(i = 0; i < 5; i++){printf("%d ",PopLinkStack(&top));}printf("\n");		
#endifprintf("len:%d\n",LengthLinkStack(top));
return 0;
}

2.6. 获取栈顶数据

问：获取栈顶数据是否需要移动栈针？

问：获取栈顶数据是否需要传递栈针地址？

获取栈顶数据，部署出栈，无需移动栈针，故无需传递栈针top的地址&top

//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{if(!IsEpLinkStack(top)){return top->data;}return -1;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{linkstack_t *top;CreateEpLinkStack(&top);int i;for(i = 0; i < 5; i++){PushLinkStack(&top,i);}
#if 0for(i = 0; i < 5; i++){printf("%d ",PopLinkStack(&top));}printf("\n");		
#endifprintf("len:%d\n",LengthLinkStack(top));printf("top_data%d\n",GetTopLinkStack(top));return 0;
}

2.7. 清空

只要不空一直出栈

//5.清空栈
void ClearLinkStack(linkstack_t **ptop)//用二级指针，是因为清空后需要将main函数中的top变为NULL
{	while(!IsEpLinkStack(*ptop)){PopLinkStack(ptop);}
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{linkstack_t *top;CreateEpLinkStack(&top);int i;for(i = 0; i < 5; i++){PushLinkStack(&top,i);#if 0for(i = 0; i < 5; i++){printf("%d ",PopLinkStack(&top));}printf("\n");		
#endifprintf("len:%d\n",LengthLinkStack(top));printf("top_data%d\n",GetTopLinkStack(top));ClearLinkStack(&top);return 0;
}