1、栈
1.1栈的概念及结构
栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶（top），表头端称为栈低（bottom）。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，所以栈又被称为后进先出的线性表（简称LIFO:Last in, First out.结构）。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。时间复杂度更小。
一般我们以能实现动态增长的栈为标准，以下为需要实现的栈操作：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //动态顺序
int top; //栈顶的位置
int capacity; //容量
}ST;
//栈的初始化
void StackInit(ST* ps);
//栈的销毁
void StackDesroy(ST* ps);
// push就是放栈顶
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps); //删除
STDataType StackTop(ST* ps); //查看栈顶的数据
//栈内的个数
int StackSize(ST* ps);
//检查是否为空
bool StackEmpty(ST* ps);
注意我们在判空的时候需要使用布尔值，头文件需要包含一个#include<stdbool.h>
1.2.1栈的初始化
栈的初始化，我们的栈顶可以设置为-1或者0，如果设置为-1，那么top就是栈顶的下标，如果设置为0，那么栈顶的下标就是top-1。本文选用的是top=0。然后容量我们设为0，在push 压栈的时候判断增容。我们的数组指针置为NULL，防止野指针出现。
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
1.2.2栈的销毁
因为通过malloc动态开辟的数组存储数据，基本上地址是连续的也就是原地扩容（也存在异地扩容），那么我们释放的时候要释放malloc返回的指针地址。
void StackDesroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
}
1.2.3 进栈操作（个人理解成尾插）
在插入之前判断是否容量满了，满了就扩容
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//增容 //如果栈的capacity为0 就先赋成4 如果不是就扩容两倍
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //三目操作判断
//数组扩容
STDataType* tmp =(STDataType*)realloc(ps->a, sizeof(STDataType)* newCapacity);
//增加程序健壮性
if (tmp == NULL)
{
perror("realloc fail");
return;
}
//把新的空间给到a
ps->a = tmp;
ps->capacity = newCapacity; //更新容量
}
ps->a[ps->top] = x; //插入数据
ps->top++; //更新top
}
1.2.4出栈操作（个人理解为尾删）
相当于顺序表的尾删，只需要改变top就可以,一定要注意空栈问题，所以要断言ps->top
void StackPop(ST* ps)
{
assert(ps);
//有一个问题就是最后的空栈
//暴力检查
assert(ps->top);
ps->top--;
}
1.2.5查看栈顶的数据
一定要判空，因为会怕越界，所以进行暴力断言来判空
STDataType StackTop(ST* ps)
{
assert(ps);
//如果删空了怎么办
//那么返回的是随机数
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
1.2.6查看栈内的个数
返回top就可以
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
1.2.7判空
bool StackEmpty(ST* ps)
{
/*if (ps->top == 0)
{
return true;
}
else
{
return false;
}*/
return ps->top == 0;
}
2、整体代码实现
Stack.h
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //动态顺序
int top; //栈顶的位置
int capacity; //容量
}ST;
//栈的初始化
void StackInit(ST* ps);
//栈的销毁
void StackDesroy(ST* ps);
// push就是放栈顶
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps); //删除
STDataType StackTop(ST* ps); //查看栈顶的数据
//栈内的个数
int StackSize(ST* ps);
//检查是否为空
bool StackEmpty(ST* ps);
Stack.c
#include"Stack.h"
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//增容 //如果单钱capacity为0 就先赋成4 如果不是就扩容两倍
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//数组扩容
STDataType* tmp =(STDataType*)realloc(ps->a, sizeof(STDataType)* newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
//把新的空间给到a
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
//有一个问题就是最后的空栈
//暴力检查
if (ps->top > 0)
{
ps->top--;
}
}
STDataType StackTop(ST* ps)
{
assert(ps);
//如果删空了怎么办
//那么返回的是随机数
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
/*if (ps->top == 0)
{
return true;
}
else
{
return false;
}*/
return ps->top == 0;
}
void StackDesroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
}
test.c
// 进出数据的地方叫栈顶 栈是先进后出 后进先出
// 数组栈 、 链式栈
//如果用尾做栈顶 尾插尾删 要设计成双向链表 否则删除数据效率低
//如果用头做栈顶 头插头删 就可以设计成单链表
//顺序栈
#include"Stack.h"
#include<stdio.h>
void TestSatck()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
int ret=StackSize(&st);
printf("%d", ret);
}
int main()
{
TestSatck();
return 0;
}
代码运行图片
