1 栈的概念及结构
栈是一种特殊的线性表，其特点是只允许在固定的一端进行插入和删除操作。进行操作的一端称为栈顶，另一端称为栈底。
栈中的元素遵循后进先出（LIFO，Last In First Out） 原则。
- 压\入\进栈（Push）：在栈顶插入元素的操作
- 出栈（Pop）：从栈顶删除元素的操作
2 栈的实现
栈可以通过数组或链表实现，数组实现更为高效（尾插尾删的时间复杂度为 O (1)）。
2.1 栈的结构定义及声明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef 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 StackPop(ST* pst);// 获取栈顶元素
STDataType STTop(ST* pst);// 栈的判空
bool STEmpty(ST* pst);// 栈的大小(获取栈中数据个数)
int STSize(ST* pst);2.2 核心操作实现
1.初始化
// 初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0; // 设定初始栈顶为0，表示无元素ps->capacity = 0;
}2.销毁
// 销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}3.入栈操作
原本栈为空时，top 为-1，为了便于写代码，令为 0
原本 top 指向栈顶元素的，没有元素时候，指向 -1，不指向 0。
所以对于上述两种情况，
情况一：
top 指向栈顶数据。
情况二：
top 指向栈顶数据的下一个位置。
// 插入数据（入栈）
void STPush(ST* ps, STDataType x)
{assert(ps);// 检查容量，不足则扩容if (ps->top == ps->capacity)//相等就扩容{int newCapacity = ps->capacity == 0 ? 4 : ps->capacity* 2;//最初时候都是0，刚开始开空间开4个STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newCapacity;}// 存入数据后栈顶上移ps->a[ps->top] = x;ps->top++;
}
4.出栈操作
void StackPop(ST* ps)
{assert(ps);// 栈顶下移即完成出栈 ps->top--;
}
5.获取栈顶元素
// 获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);//assert(!STEmpty(ps));assert(ps->top > 0);//避免空栈return ps->a[ps->top - 1];
}6.栈的判空
// 栈的判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}7.栈的大小
// 栈的大小(获取栈中数据个数)
int STSize(ST* ps)
{assert(ps);return ps->top;
}
2.3 测试一下
#define _CRT_SECURE_NO_WARNINGS 1
#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 ", STTop(&s));STPop(&s);}STDestroy(&s);return 0;
}
