数据结构-----栈、顺序栈、链栈

在软件应用中，栈这种后进先出数据结构的应用是非常普遍的。比如用浏览器上网时，不管什么浏览器都有一个“后退”键，你点击后可以按访问顺序的逆序加载浏览过的网页。即使从一个网页开始，连续点了几十个链接跳转，你点“后退”时，还是可以像历史倒退一样，回到之前浏览过的某个页面。在很多类似的软件，都有撤销的的操作，也是使用栈这种方式来实现的。

1、定义

栈是限定仅在表尾进行插入和删除操作的线性表。

特点：数据是先进后出、后进先出

2、结构及类型

2.1 栈的类型？

满减栈
满增栈
空减酸
空增栈

满栈，top指示的是，最后一次入栈的元素

空栈，不含任何元素的栈。top指示的是，新元素待插入的位置

增栈，随着元素的push，top地址变大

减栈，随着元素的push，top地址变小

2.2 结构

栈顶：允许插入和删除的一端

栈底：另一端

2.3 说明

栈又称为后进先出的线性表（LIFO结构），首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹

栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹

3、栈的抽象数据类型（ADT栈）

两个流程：入栈、出栈

两种常见的栈：顺序栈、链式栈

4、顺序栈

4.1 什么是顺序栈？

栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。可以简单理解为将数据存在一个数组中，只不过释放数据和存储数据有一些独特的功能。通常，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小。

4.2 图示理解顺序栈

在进行进栈和出栈时，栈顶会进行++或--处理，目的是为了调整栈的大小，++代表写入了一个节点，--代表出去了一个节点。但是栈顶++实际上指的是一个待插入的数据位置，栈顶表示插入最新的数据位置（大小）。同样的，栈顶--代表即将出去的一个节点的位置

4.3 执行代码

顺序栈这里我直接放代码，不分开说明，每个功能需要去理解一下。

typedef struct  person {char name[32];char sex;int age;int score;
}DATATYPE;
typedef struct list {DATATYPE *head;int tlen;int top;
}SeqStack;SeqStack* CreateSeqStack(int len);
int DestroySeqStack(SeqStack* ss);
int PushSeqStack(SeqStack* ss, DATATYPE* data);
int PopSeqStack(SeqStack*ss);
DATATYPE* GetTopSeqStack(SeqStack* ss);
int IsEmptySeqStack(SeqStack* ss);
int IsFullSeqStack(SeqStack* ss);
int GetSizeSeqStack(SeqStack*ss);

// 创建一个顺序栈，并初始化
SeqStack* CreateSeqStack(int len)
{// 分配内存给SeqStack结构体SeqStack* ss = (SeqStack*)malloc(sizeof(SeqStack));if(NULL == ss){perror("CreateSeqStack malloc 1"); // 打印错误信息return NULL;}// 分配内存给存储数据的数组ss->head = (DATATYPE*)malloc(sizeof(DATATYPE) * len);if(NULL == ss->head){perror("CreateSeqStack malloc 2"); // 打印错误信息free(ss); // 释放已分配的SeqStack结构体内存return NULL;}ss->tlen = len; // 初始化栈的总长度ss->top = 0;    // 初始化栈顶指针return ss;      // 返回创建好的顺序栈指针
}// 入栈操作
int PushSeqStack(SeqStack* ss, DATATYPE* data)
{// 判断栈是否已满if(IsFullSeqStack(ss)){return 1; // 栈已满，无法入栈}// 将数据复制到栈顶，并更新栈顶指针memcpy(&ss->head[ss->top++], data, sizeof(DATATYPE));return 0; // 入栈成功
}// 出栈操作
int PopSeqStack(SeqStack* ss)
{// 判断栈是否为空if(IsEmptySeqStack(ss)){return 1; // 栈为空，无法出栈}// 出栈操作，更新栈顶指针ss->top--;return 0; // 出栈成功
}// 判断栈是否已满
int IsFullSeqStack(SeqStack* ss)
{return ss->top == ss->tlen; // 当栈顶指针等于总长度时，表示栈已满
}// 判断栈是否为空
int IsEmptySeqStack(SeqStack* ss)
{return 0 == ss->top; // 当栈顶指针为0时，表示栈为空
}// 获取栈顶元素的指针
DATATYPE* GetTopSeqStack(SeqStack* ss)
{if(IsEmptySeqStack(ss)) // 如果栈为空，则返回NULL{return NULL;}// 返回栈顶元素的指针return &ss->head[ss->top - 1];
}// 获取栈的大小（元素个数）
int GetSizeSeqStack(SeqStack* ss)
{return ss->top; // 栈的大小即为栈顶指针的值
}// 销毁顺序栈，释放内存
void DestroySeqStack(SeqStack* ss)
{if(ss != NULL){if(ss->head != NULL){free(ss->head); // 释放存储数据的数组内存}free(ss); // 释放SeqStack结构体内存}
}

5、链栈

栈的链式存储结构，与顺序栈不同的是链栈是由一个个节点拼接而成，并非连续的数组。

5.1 用到的结构体

1.数据结构体

typedef struct {//公共数据
}DATATYPE;

这个结构体是链栈中存储的数据类型，即每个节点的数据部分。在这个结构体中可以定义链栈节点存储的具体数据内容。

2.节点结构体

typedef struct node{DATATYPE data;//数据体struct node *next;//指向下一个节点的指针
}LinkStackNode

LinkStackNode：这个结构体定义了链栈的节点类型。每个节点包含两部分信息：

DATATYPE类型的变量，用于存储节点的数据；

指向下一个节点的指针。

解释struct node *next而非其他类型的指针：

struct node *nex表示指针指向的是另一个struct node类型的节点。这是因为链栈中每个节点都是由struct node定义的，因此指向下一个节点的指针应该是指向struct node类型的指针。

int *: 这表示指针指向的是一个整数。在链栈中，不是在每个节点中存储整数数据，而是在data字段中存储整数数据。

因此next指针应该指向另一个节点，而不是一个整数。

3.链栈结构体

typedef struct  {LinkStackNode* top;//指向链栈顶部节点的指针，通过这个指针可以访问链栈中的最顶部节点，也就是最后一个入栈的节点。int clen;          //栈当前的长度：其中包含的节点数量
}LinkStackList;

这个结构体定义了链栈本身的结构。

4.下面从图片解释上面结构体之间的关系

因为栈是一个线性表，这里LinkStackList结构体用来确定栈的头在哪里，clen记录了这个栈所包含节点的个数，就是所谓的长度。LinkStackNode结构体确定每个节点的内容，其包括下一个节点的位置指针以及本节点的data数据，DATATYPE是存放数据的结构体。需要注意的是，无论是List中的*top还是节点Node的*next，都是指向下一个整体节点的位置，而非节点中某个成员。

5. 那么为什么要用三个结构体？

        首先 DATATYPE结构体是公共数据，用来存放每个节点所包含的数据，可以灵活定义节点中存储的数据内容。如果未来需要修改节点数据的结构或添加额外的数据字段，只需修改这个结构体，而不必改动其他部分。所以不能省略；（必要的）

  LinkStackNode结构体用来存放数据和指向下一个节点的指针，这样的设计使得节点本身具有了独立的意义，可以单独操作节点，而不必担心节点的具体数据类型或链栈的实现细节。（必要的）

  LinkStackList结构体的作用是可以明确找到栈的顶部指针和长度信息，如果将长度信息clen放在Node节点中，也可以实现知道具体的长度，如果想要知道clen，这就要求要在Node每个节点中++进行计算，使得计算流程更加复杂，并且每次想要获取数据的时候就要从头开始重新遍历一遍。而放在List结构体中，只要将最开始创建栈的时候将创建节点的个数存在clen中就可以了，将链栈的结构信息独立出来，更方便调用。（非必要但建议有）

5.2 执行代码

.h文件

typedef struct {char name[32];char sex;int age;int score;
}DATATYPE;typedef struct stack_node {DATATYPE data;struct stack_node *next;
}LinkStackNode;typedef struct  {LinkStackNode* top;int clen;
}LinkStackList;LinkStackList* CreateLinkStack();
int DestroyLinkStackList(LinkStackList**ls);
int PushLinkStack(LinkStackList* ls, DATATYPE*data);
int PopLinkStack(LinkStackList*ls);
DATATYPE* GetTopLinkStack(LinkStackList*ls);
int IsEmtpyLinkStack(LinkStackList* ls);
int GetSizeLinkStack(LinkStackList*ls);

.c文件

#include "linkstack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 创建一个新的链式栈并返回指针
LinkStackList* CreateLinkStack()
{// 分配内存空间给链式栈LinkStackList* ls = (LinkStackList*)malloc(sizeof(LinkStackList));if (NULL == ls){perror("CreateLinkStack malloc");return NULL;}// 初始化链式栈的顶部指针为空，长度为0ls->top = NULL;ls->clen = 0;return ls;
}// 销毁链式栈
int DestroyLinkStackList(LinkStackList** ls)
{// 获取链式栈的长度int len = GetSizeLinkStack(*ls);int i = 0;// 逐个弹出链式栈中的元素for (i = 0; i < len; i++){PopLinkStack(*ls);}// 释放链式栈的内存空间free(*ls);*ls = NULL;return 0;
}// 将数据压入链式栈
int PushLinkStack(LinkStackList* ls, DATATYPE* data)
{// 分配内存空间给新的节点LinkStackNode* newnode = (LinkStackNode*)malloc(sizeof(LinkStackNode));if (NULL == newnode){perror("PushLinkStack malloc");return 1;}// 将数据拷贝到新节点中memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;// 如果链式栈为空，直接将新节点设为顶部if (IsEmtpyLinkStack(ls)){ls->top = newnode;}else{// 否则，将新节点插入到链式栈顶部并更新顶部指针newnode->next = ls->top;ls->top = newnode;}// 链式栈长度加一ls->clen++;return 0;
}// 弹出链式栈顶部的元素
int PopLinkStack(LinkStackList* ls)
{// 如果链式栈为空，返回1表示失败if (IsEmtpyLinkStack(ls)){return 1;}// 保存顶部节点的指针LinkStackNode* tmp = ls->top;// 更新顶部指针为下一个节点ls->top = ls->top->next;// 释放原顶部节点的内存空间free(tmp);// 链式栈长度减一ls->clen--;return 0;
}// 获取链式栈顶部元素的指针
DATATYPE* GetTopLinkStack(LinkStackList* ls)
{// 如果链式栈为空，返回NULLif (IsEmtpyLinkStack(ls)){return NULL;}// 否则，返回顶部节点的数据指针return &ls->top->data;
}// 判断链式栈是否为空
int IsEmtpyLinkStack(LinkStackList* ls)
{return 0 == ls->clen;
}// 获取链式栈的长度
int GetSizeLinkStack(LinkStackList* ls)
{return ls->clen;
}

//调用
#include "linkstack.h"
#include <stdio.h>int main(int argc, char *argv[])
{DATATYPE data[]={{"zhansan",'m',20,90},{"lisi",'f',22,87},{"wangmazi",'m',21,93},{"guanerge",'m',40,60},{"liuei",'m',42,83},};LinkStackList* ls = CreateLinkStack();int i = 0 ;for(i = 0 ;i<5;i++){PushLinkStack(ls,&data[i]);}int len = GetSizeLinkStack(ls);for(i = 0 ;i<len;i++){DATATYPE* tmp = GetTopLinkStack(ls);printf("%s %d\n",tmp->name ,tmp->score );PopLinkStack(ls);}DestroyLinkStackList(&ls);return 0;
}