1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
数组栈
链式栈
链式栈分为【单链表】和【双向链表】去实现栈。双向链表的栈顶可以是头也可以是尾。
但我们一般都用单链表，因为单链表更节省资源。
单链表实现栈：栈顶只能是单链表头（头插头删很容易），栈底只能是单链表尾（尾插尾删很复杂）
接下来我们就来实现一下数组栈吧！👇
Test.c总代码
#include"Stack.h"
int main()
{
ST pst;//创建结构体
STInit(&pst);//传地址是修改结构体内部
STPush(&pst, 1);
STPush(&pst, 2);
STPush(&pst, 3);
STPush(&pst, 4);
STPush(&pst, 5);
while (!STempty(&pst))
{
printf("%d ", STTop(&pst));
STPop(&pst);
}
STDestroy(&pst);
}
注意：一定要把top处的元素出栈，才能够访问下一个！
头文件Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>函数声明Stack.h
typedef int STDataType;- 创建结构体
typedef int STDatatype;
typedef struct Stack
{
STDatatype* a;
int top;
int capacity;
}ST;- 初始化
void STInit(ST* pst);- 释放销毁
void STDestroy(ST* pst);- 压栈
void STPush(ST* pst, STDatatype x);- 出栈
void STPop(ST* pst);- 栈顶元素
STDatatype STTop(ST* pst);- 判断栈是否为NULL
bool STempty(ST* pst);- 栈内的元素个数
int STSize(ST* pst);Stack.h总代码
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 标识栈顶位置的
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);函数实现Stack.c
这里有一个点需要注意！就是初始化时top的值应该为多少？
如果初始化 top=0：表示栈内元素的个数。作为a[top]指针指向栈顶元素的下一个。
如果初始化 top=-1：表示数组元素的下标。作为a[top]指针指向栈顶元素。
初始化SLInit
#include"Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = 0;
pst->top = 0;//表示top指向栈顶元素的下一个位置
//pst->top = -1;//表示top指向栈顶元素
pst->capacity = 0;
}压栈STPush
里面包含了扩容操作！
// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}出栈STPop
void STPop(ST* pst)
{
assert(pst);
// 不为空
assert(pst->top > 0);
pst->top--;
}栈顶元素STTop
STDataType STTop(ST* pst)
{
assert(pst);
// 不为空
assert(pst->top > 0);
return pst->a[pst->top - 1];
}判断栈是否为空STempty
bool STEmpty(ST* pst)
{
assert(pst);
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}栈内元素个数STSize
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}数组栈空间释放STDestroy
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}Stack.c总代码
#include"Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
// 表示top指向栈顶元素的下一个位置
pst->top = 0;
// 表示top指向栈顶元素
//pst->top = -1;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
// 不为空
assert(pst->top > 0);
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
// 不为空
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
assert(pst);
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
