【数据结构：栈】——栈的实现（C语言）
1、什么是栈？
栈： 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
详细了解：栈的详解
2、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
数组结构：
链表结构：
3、代码实现
Stack.h文件
typedef int STDataType;
typedef struct Stack
{
STDataType* _array;
size_t _top;
size_t _capacity;
}Stack;
void StackInit(Stack* ps);//初始化
void StackDestory(Stack* ps);//销毁
void StackPush(Stack* ps, STDataType x);//尾插
void StackPop(Stack* ps);//尾删
STDataType StackTop(Stack* ps);//取到当前栈顶元素
int StackEmpty(Stack* ps);//判断栈是否为空
int StackSize(Stack* ps);//判断栈中的元素个数
void StackPrint(Stack* ps);//从栈中取出元素
void PintfStack(Stack* ps);//查看栈中元素
void Test();//测试
Stack.c文件
void StackInit(Stack* ps)//初始化
{
assert(ps);
ps->_array = NULL;
ps->_capacity = ps->_top = 0;
}
void StackDestory(Stack* ps)//销毁
{
assert(ps && ps->_array != NULL);
free(ps->_array);
ps->_array = NULL;
ps->_capacity = ps->_top = 0;
}
void StackPush(Stack* ps, STDataType x)//尾插
{
assert(ps);
if (ps->_top == ps->_capacity)//判断容量是否够用
{
size_t new_capacity = ps->_array == 0 ? 8 : (ps->_capacity) * 2;//三目运算符判断容量是否够用
ps->_array = (STDataType*)realloc(ps->_array, new_capacity*sizeof(STDataType));
assert(ps->_array);//判断是否申请到内存
ps->_capacity = new_capacity;
}
//插入数据
ps->_array[ps->_top] = x;
ps->_top++;
}
void StackPop(Stack* ps)//尾删
{
assert(ps && ps->_array != NULL);
--ps->_top;//把栈顶指针向前移动一位，完成出栈
}
STDataType StackTop(Stack* ps)//取到当前栈顶元素
{
assert(ps && ps->_array != NULL);
return ps->_array[ps->_top - 1];
}
int StackEmpty(Stack* ps)//判断栈是否为空
{
assert(ps);
return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack* ps)//判断栈中的元素个数
{
assert(ps);
return ps->_top;
}
void StackPrint(Stack* ps)//从栈中取出元素
{
assert(ps && ps->_array != NULL);
while (StackEmpty(ps))
{
printf("%d->",StackTop(ps));//每次取出栈顶元素
StackPop(ps);
}
printf("NULL");
printf("\n");
}
void PintfStack(Stack* ps)//查看栈中元素
{
assert(ps);
if (ps->_top == 0)
{
printf("栈中为空！！！\n");
}
else
{
for (size_t n = 0; n < ps->_top; n++)
{
printf("%d->", ps->_array[n]);
}
printf("NULL\n");
}
}
void Test()
{
Stack pl;
StackInit(&pl);//初始化
//尾插
StackPush(&pl, 0);
StackPush(&pl, 1);
StackPush(&pl, 2);
StackPush(&pl, 3);
StackPush(&pl, 4);
StackPush(&pl, 5);
//取出栈中元素
//销毁栈
StackDestory(&pl);
}
main.c文件
#include"Stack.h"
int main()
{
Test();
system("pause");
return 0;
}
运行截图
