【数据结构】栈的概念、结构和实现详解

本文来介绍一下数据结构中的栈，以及如何用C语言去实现。

 1. 栈的概念及结构

栈：一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。

       进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

       栈中元素遵循后进先出LIFO（Last In First Out）的原则

压栈：栈的插入操作叫做进栈/入栈/压栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

2. 实现栈的底层方法选择

没有规定栈的哪端是栈顶，只说了数据插入和删除的一端是栈顶，所以我们栈的底层实现可以用链表或者数组 。

 虽然数组和单链表都可以实现栈，但是单链表能很好入数据不好删除数据，这里单链表要删除数据就是尾删，尾删需要找到前一个结点，不是很方便。

非要用链表的话有两个解决方法，1.可以用双向链表 2.我们把单链表的头节点当作栈顶，也就是把左边当栈顶，右边当栈底，对单链表进行头插和头删的操作。

 现在有3种方法实现栈，数组，单链表，双链表，我们应该如何选？

首先排除双链表，用双链表不如用单链表，双链表因为一个节点存两个指针，比单链表的一个节点多了4个字节或者8个字节。数组实现栈和单链表实现栈有什么区别?基本没区别，都可以，非要说选一个，我们还是更倾向于数组，因为数组的唯一缺点就是内存不足时需要扩容，扩容的影响也不是特别大，最重要的是数组的缓存效率更高。所以我们就用数组实现栈。

3. 栈的实现

提前说明，如果本篇看不太懂可以先看看【数据结构】顺序表-CSDN博客，我们栈的实现和顺序表的实现差不多。

还是一样，新建一个头文件和两个源文件

 点开Stack.h文件，在这个文件里面我们要定义栈的结构，以及给类型和栈的结构取别名。

typedef int STDateType;
typedef struct Stack
{STDateType* a;//动态申请空间 调大小int top;      //用栈顶记录元素个数int capacity; //数组实现要扩容，记录空间大小
}ST;

栈一共要实现下面这7个接口，我们将一个一个来看.

void STInit(ST* pst);//栈初始化
void STDistroy(ST* pst);//栈的销毁
void STPush(ST* pst, STDateType x);//压栈
void STPop(ST* pst);//出栈
STDateType STTopDate(ST* pst);//获取栈顶元素
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//获取栈元素个数

这里是会用到的头文件，且标注了是什么会用到，被包含的头文件全放在Stack.h中

#include <stdio.h>
#include <stdlib.h>   //空间申请
#include <stdbool.h>  //布尔类型
#include <assert.h>   //断言

在Stack.c中只需要包含Stack.h

#include "Stack.h"

 准别工作做好后我们开始实现栈。

3.1 栈的初始化和销毁

在Stack.h中进行函数的声明。这里的参数需要传指针。

void STInit(ST* pst);//栈初始化
void STDistroy(ST* pst);//栈的销毁

在SeqList.c中进行函数的实现

void STInit(ST* pst)//栈初始化
{assert(pst); //判断pst是否为空pst->capacity = 0;pst->top = 0;pst->a = NULL;
}

void STDistroy(ST* pst)//栈的销毁
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}

 这里和顺序表差不多，很简单就不多说了。

3.2 压栈和出栈

在Stack.h中进行函数的声明。

void STPush(ST* pst, STDateType x);//压栈
void STPop(ST* pst);//出栈

这里的参数需要传指针，压栈的函数参数还有要插入的数据。因为栈插入数据就是从栈顶插入，这里就没有什么头插尾插的概念，直接就是Push，删除数据也是，直接栈顶删除Pop。

在SeqList.c中进行函数的实现

先说压栈

先分析空间足够的情况，初始化我们把top置为0，放进一个元素，top就是1，但是这个元素在数组中的下标为0，所以栈顶元素数组下标是top-1，而top指向的是栈顶元素的下一个位置，而不是栈顶元素。

所以我们放数据就是直接放下标为top的位置。

void STPush(ST* pst, STDateType x)//压栈
{assert(pst);pst->a[pst->top] = x; //先放数据pst->top++;   //然后top++}

然后考虑扩容。capacity是数组大小，分析一下数组满了的情况

 

应该是top和capacity相等，此时就要扩容。

void STPush(ST* pst, STDateType x)//压栈
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity * 2;//原来空间2倍的扩容//扩容STDateType* tmp = (STDateType*)realloc(pst->a, newcapacity * sizeof(STDateType));if (tmp == NULL) //扩容失败{perror("realloc fail");return;}//扩容成功pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}

但是我们要注意这句代码 int newcapacity = pst->capacity * 2;  我们一开始capacity初始化为0，0乘任何数都是0，所以这句换我们要改一下，用一个三目操作符就能解决。

int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;

 再说出栈

出栈和顺序表是一样的，直接top--就行了，不理解的可以看看顺序表中数据的尾删

void STPop(ST* pst)//出栈
{assert(pst);assert(pst->top > 0);pst->top--;
}

在test.c中测试一下栈的初始化，压栈，出栈，栈的销毁。

#include "Stack.h"
int main()
{ST s;STInit(&s);   //初始化STPush(&s, 1);//压栈STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);for (int i = 0; i < s.top; i++){printf("%d ", s.a[i]);}printf("\n");STPop(&s);//出栈for (int i = 0; i < s.top; i++){printf("%d ", s.a[i] );}printf("\n");STPop(&s);//出栈for (int i = 0; i < s.top; i++){printf("%d ", s.a[i]);}STDistroy(&s);//销毁return 0;
}

 遵循后进先出

3.3 获取栈顶元素

在Stack.h中进行函数的声明。

STDateType STTopDate(ST* pst);//获取栈顶元素

在SeqList.c中进行函数的实现

STDateType STTopDate(ST* pst)//获取栈顶元素
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}

在test.c中测试一下

#include "Stack.h"
int main()
{ST s;STInit(&s);   //初始化STPush(&s, 1);//压栈STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);for (int i = 0; i < s.top; i++){printf("%d ", s.a[i]);}printf("\n");printf("栈顶元素：%d\n", STTopDate(&s));STPop(&s);//出栈STPop(&s);for (int i = 0; i < s.top; i++){printf("%d ", s.a[i] );}printf("\n");printf("栈顶元素：%d\n", STTopDate(&s));STDistroy(&s);//销毁return 0;
}

3.4 判断栈是否为空

在Stack.h中进行函数的声明。

bool STEmpty(ST* pst);//判断栈是否为空

这里用了bool类型，需要包含头文件stdbool.h

在SeqList.c中进行函数的实现

bool STEmpty(ST* pst)//判断栈是否为空
{assert(pst);if (pst->top == 0) //为空，返回真return true;else               //不为空，返回假return false;
}

还有一个更简单的写法，如下

 bool STEmpty(ST* pst)//判断栈是否为空
{assert(pst);return pst->top == 0;
}

 为空，返回真，不为空返回假。

在test.c中测试一下，用栈的后进先出的特点访问

#include "Stack.h"
int main()
{ST s;STInit(&s);   //初始化STPush(&s, 1);//压栈STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);//栈标准的后进先出访问方式while (!STEmpty(&s)){printf("%d ", STTopDate(&s));//先访问栈顶元素STPop(&s); //然后把栈顶元素删除}STDistroy(&s);//销毁return 0;
}

3.5 获取栈元素个数

在Stack.h中进行函数的声明。

int STSize(ST* pst);//获取栈元素个数

在SeqList.c中进行函数的实现

因为我们前面的top初始化为0，所以top就是栈的元素个数，直接返回top就行了。

int STSize(ST* pst)//获取栈元素个数
{assert(pst);return pst->top;
}

在test.c中自己测试一下，这里就不测试了

到这里这个栈就实现好了，本篇也就结束啦，拜拜~