数据结构篇四：栈
文章目录
前言
前面学习的一些结构都比较普通，今天就让我们来看一个比较特殊的结构——栈，它的特殊之处是后进先出，也就是后进来的数据先出去。
1.栈
1.1 栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.栈功能的解析及实现
2.1 栈的创建
我们采用数组的形式进行实现。
typedef int DataType;
typedef struct Stack
{
DataType* data;
int top; //栈顶
int capacity;容量
}Stack;
2.2 初始化
将所有数据赋个初值。
void StackInit(Stack* ps)
{
assert(ps);
ps->data = NULL;
ps->top = 0; //指向栈顶元素的下一个位置，同时也代表这栈中有多少元素
ps->capacity = 0;//栈的容量
}
2.3 入栈
入栈也就是要增加元素，那么首先需要做的就是判断容量够不够，不够的话就需要增容，然后再将元素放进去即可。
void StackPush(Stack* ps, DataType x)
{
assert(ps);
//判断是否需要增容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
DataType* tmp = (DataType*)realloc(ps->data,sizeof(DataType) * newcapacity);
if (tmp == NULL)
{
return;
}
ps->data = tmp;
ps->capacity = newcapacity;
}
ps->data[ps->top] = x;
ps->top++;
}
2.4 出栈
出栈的话我们只能从栈顶出元素，不能从其他位置出。既然要删除元素，那么我们就需要判断栈中是否还有剩余元素，没有的话就不需要删除。这里我写了一种方式，不过后面还会写一个判断栈是否为空的函数，大家看个人喜好采用。
void StackPop(Stack* ps)
{
assert(ps);
//assert(ps->top > 0);
assert(!StackEmpty(ps));
ps->top--;
}
2.5 检查栈是否为空
写的比较简洁，返回的是ps->top == 0，也就是如果条件成立，这个表达式就代表着true（也就是栈为空），如果不成立就代表着false（栈不为空）。
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
2.6 获取栈顶元素
我们的top指向的是栈顶元素的下一个位置，所以在数组中最后一个元素也就是栈顶的元素位置是top - 1。
DataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断是否为空
return ps->data[ps->top - 1];
}
2.7 栈中的有效元素个数
在创建栈哪里就提到了，top既指向栈顶元素的后一个位置，也代表着栈中的元素个数。
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
2.8 销毁
动态开辟的空间在程序结束时都需要被回收，用来防止出现内存泄漏。
void StackDestroy(Stack* ps)
{
ps->top = 0;
ps->capacity = 0;
free(ps->data);
ps->data = NULL;
}
3.代码实现
3.1 Stack.h
栈的创建以及各个函数声明。
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int DataType;
typedef struct Stack
{
DataType* data;
int top;
int capacity;
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, DataType x);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
DataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
3.2 Stack.c
栈的各功能的函数。
#include"Stack.h"
void StackInit(Stack* ps)
{
assert(ps);
/*DataType* tmp = (DataType*)malloc(sizeof(DataType));
if (tmp == NULL)
{
return;
}*/
ps->data = NULL;
ps->top = 0; //指向栈顶元素的下一个位置，同时也代表这栈中有多少元素
ps->capacity = 0;
}
void StackPush(Stack* ps, DataType x)
{
assert(ps);
//判断是否需要增容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
DataType* tmp = (DataType*)realloc(ps->data,sizeof(DataType) * newcapacity);
if (tmp == NULL)
{
return;
}
ps->data = tmp;
ps->capacity = newcapacity;
}
ps->data[ps->top] = x;
ps->top++;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPop(Stack* ps)
{
assert(ps);
//assert(ps->top > 0);
assert(!StackEmpty(ps));
ps->top--;
}
DataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->data[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
void StackDestroy(Stack* ps)
{
ps->top = 0;
ps->capacity = 0;
free(ps->data);
ps->data = NULL;
}
3.3 test.c
用来测试实现的栈功能有没有问题。
#include"Stack.h"
void test()
{
Stack st;
StackInit(&st);//初始化
StackPush(&st, 1);//测试:入栈
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while(!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("n");
StackPush(&st, 5);//入栈一些元素进行测试
StackPush(&st, 6);
StackPop(&st);//测试:中途出栈的效果,实际就是将6提前出栈
StackPush(&st, 7);
StackPush(&st, 8);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("n");
StackPush(&st, 1);//入栈一些数据进行测试
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
int sz = StackSize(&st);//测试:计算栈中元素个数
printf("%dn", sz);
StackDestroy(&st);
}
int main()
{
test();
return 0;
}
4.总结
单纯从代码实现角度来看，栈的实现还是比较简单的，因此可以不用在代码实现方面下太大的功夫，将更多的注意力转移到做题方面，感觉会有更好的效率性。
栈的讲解就先告一段落了，如果发现文章哪里有问题可以在评论区提出来或者私信我嗷。接下来我会继续深入学习数据结构的其他知识，开启新的篇章，那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励喔！！