我们已经学习过了【线性表】中的顺序表和链表。今天开始进入栈和队列。栈和队列是顺序表和链表的延续，也是一种线性表（线性表在逻辑上也是连续的）。大体结构上都很相似，所以大家学习起来也会很容易的。但是栈和队列也有自己独特的性质，学习也需要特别注意哦。
栈的概念及其结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守 后进先出 / 后进先出 LIFO（Last In First Out）的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
【先进后出/后进先出】可以类比【弹夹】
栈的实现
了解了栈的概念，如何实现栈呢？
根据前面博文我们可以【数组栈】和【链式栈】
数组栈
数组栈比较简单，也是快速容易实现，首先就是【数组栈】实现。
链式栈
链式栈分为【单链表】和【双向链表】去实现栈。毋庸置疑，【双向链表实现】栈顶可以是尾巴，也可以是头，因为双向链表的头插/头删和尾插/尾删都是很方便的。
但是为了节省资源，我们用【单链表】该怎样去设计呢？
单链表实现栈：栈顶只能是单链表头（头插/头删易），栈底只能是单链表尾（头删很复杂）
栈的常见接口实现
- 断言NULL/Pop==0情况
- 改变结构体用指针
- top的指向
- 单个数据直接用，多个数据用结构体包含起来
- 数组的数据访问用数组下标即可访问
- pst和pst->a搞清楚！
- 入栈顺序是只有一种，但是出栈顺序有多种！！
主函数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); }
由于栈是其只允许在固定的一端进行插入和删除元素操作。所以栈的访问是必须先Pop弹出元素才能访问下一个元素。
while (!STempty(&pst)) { printf("%d ", STTop(&pst)); STPop(&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);
- 判断栈是否为NULL
bool STempty(ST* pst);
- 栈内的元素个数
int STSize(ST* pst);
函数实现Stack.c
初始化SLInit
如果初始化 top=0：表示栈内元素的个数。作为a[top]指针指向栈顶元素的下一个。
如果初始化 top=-1：表示数组元素的下标。作为a[top]指针指向栈顶元素。
#include"Stack.h" void STInit(ST* pst) { assert(pst); pst->a = 0; //表示top指向栈顶元素的下一个位置 pst->top = 0; //表示top指向栈顶元素 //pst->top = -1; pst->capacity = 0; }
扩容Createcapacity
void Createcapacity(ST* pst) { //扩容 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(ST) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } }
压栈STPush
void STPush(ST* pst, STDatatype x) { assert(pst); Createcapacity(pst); 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); return pst->top == 0;//为0就是true 为！=0就是为flase }
栈内元素个数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 = 0; pst->capacity = 0; }
数组栈总代码
//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); } //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 #include"Stack.h" void STInit(ST* pst) { assert(pst); pst->a = 0; pst->top = 0; pst->capacity = 0; } void Createcapacity(ST* pst) { //扩容 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity; ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } } void STPush(ST* pst, STDatatype x) { assert(pst); Createcapacity(pst); 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); return pst->top == 0;//为0就是true 为！=0就是为flase } int STSize(ST* pst) { assert(pst); return pst->top; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; }
✔✔✔✔✔最后，感谢大家的阅读，若有错误和不足，欢迎指正！各位小伙伴乖乖敲代码哦。
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱：2784139418@qq.com】
