🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）
目录
栈
引入
介绍
为什么栈用顺序表而不用数组？
栈的实现
stack.h：结构体，栈的声明与定义
stack.c：栈的具体实现代码
栈的初始化
压入
弹出
取栈顶元素
栈的大小
判断栈是否为空
栈的销毁
Test.c：栈的测试
队列
引入
介绍
为什么队列选择链表而不用数组？
队列实现
Queue.h：结构体，队列的声明和定义
Queue.c：队列函数具体实现
队列初始化
队尾入队列（数据）
队头出队列（数据）
获取队列头部元素
获取队列尾部元素
判断队列是否为空
队列中有效元素个数
队列销毁
Test.c：队列的测试
栈
引入
介绍
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）
的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
为什么栈用顺序表而不用数组？
由于栈只用在同一端进行插入和删除，因此我们优先选择使用顺序表，因为在顺序表的末尾插入和删除的时间复杂度都是O(1)，并且操作简单
栈的实现
stack.h：结构体，栈的声明与定义
typedef int STDatatype;
typedef struct stack
{
STDatatype* a;
int top; //栈顶
int capacity; //容量
}ST;
//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//压入
void STPush(ST* ps, STDatatype x);
//弹出/出栈
void STPop(ST* ps);
//取栈顶元素
STDatatype STTPop(ST* ps);
//栈的大小
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);
stack.c：栈的具体实现代码
栈的初始化
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}压入
void STPush(ST* ps, STDatatype x)
{
assert(ps);
//如果栈顶 = 容量，满了
if (ps->top == ps->capacity)
{
//扩容
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDatatype* tmp = (STDatatype*)realloc(ps->a, newcapacity * sizeof(STDatatype));
if (tmp == NULL)
{
perror("realloc");
return;
}
//赋值
ps->a = tmp;
ps->capacity = newcapacity;
}
//新数据给值
ps->a[ps->top] = x;
ps->top++;
}弹出
void STPop(ST* ps)
{
assert(ps);
//判断栈是否为空
assert(!STEmpty(ps));
//栈顶元素删除
ps->top--;
}取栈顶元素
STDatatype STTPop(ST* ps)
{
assert(ps);
//判断栈是否为空
assert(!STEmpty(ps));
return ps->a[ps->top - 1];//栈顶元素下标
}栈的大小
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}判断栈是否为空
bool STEmpty(ST* ps)
{
assert(ps);
//为空返回True,不为空返回False
return ps->top == 0;
}栈的销毁
void STDestroy(ST* ps)
{
//判断穿的指针是否有效
assert(ps);
//先释放，后置空
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
Test.c：栈的测试
int main()
{
ST st;
//初始化
STInit(&st);
//压入
STPush(&st, 1);//1
STPush(&st, 2);//1 2
STPush(&st, 3);//1 2 3
STPush(&st, 4);//1 2 3 4
//取栈顶元素
int top = STTPop(&st);//4
//printf("%d ", top);//4
//弹出
STPop(&st);//1 2 3
//压入
STPush(&st, 5);//1 2 3 5
STPush(&st, 6);//1 2 3 5 6
while (!STEmpty(&st))//栈不为空
{
int top = STTPop(&st);//6 5 3 2 1
printf("%d ", top); //6 5 3 2 1
STPop(&st);
}
//摧毁
STDestroy(&st);
return 0;
}
队列
引入
介绍
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
为什么队列选择链表而不用数组？
由于队列需要在队列两端进行插入或删除，因此我们优先选择链表来进行实现。当然使用数组实现也可以，只是数组在头部插入和删除元素需要O(n)的时间复杂度，因此选择链表更优。
队列实现
Queue.h：结构体，队列的声明和定义
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QueDatatype;
typedef struct QueueNode
{
int val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Que;
//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);
// 队尾入队列
void QueuePush(Que* pq, QueDatatype x);
// 队头出队列
void QueuePop(Que* pq);
//获取队列头部元素
QueDatatype QueueFront(Que* pq);
//获取队列尾部元素
QueDatatype QueueBack(Que* pq);
//判断队列中有效元素
bool QueueEmpty(Que* pq);
//队列中有效元素个数
int QueueSize(Que* pq);
Queue.c：队列函数具体实现
队列初始化
void QueueInit(Que* pq)
{
assert(pq);
//一开始队列为空
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0; //队列大小
}队尾入队列（数据）
void QueuePush(Que* pq, QueDatatype x)
{
assert(pq);
//扩容
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
//给值
newnode->val = x;
newnode->next = NULL;
//队列不止一个元素
if (pq->ptail)
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
//队列只有一个元素
else
{
pq->phead = pq->ptail = newnode;
}
pq->size++;
}队头出队列（数据）
void QueuePop(Que* pq)
{
assert(pq);
assert(pq->phead);
//队列中不止一个元素
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
//队列中只有一个元素
else
{
//先记录队头的下一个元素
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}获取队列头部元素
QueDatatype QueueFront(Que* pq)
{
assert(pq);
//判断队列是否为空
assert(pq->phead);
return pq->phead->val;
}
获取队列尾部元素
QueDatatype QueueBack(Que* pq)
{
assert(pq);
//判断队列是否为空
assert(pq->ptail);
return pq->ptail->val;
}
判断队列是否为空
bool QueueEmpty(Que* pq)
{
assert(pq);
//为空返回True，不为空返回False
return pq->size == 0;
}队列中有效元素个数
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;//队列大小
}队列销毁
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->phead;
//依次释放节点
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
//置为空
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
Test.c：队列的测试
#include"Queue.h"
int main()
{
Que q;
//初始化
QueueInit(&q);
//队尾进入队列
QueuePush(&q, 1);//1
QueuePush(&q, 2);//1 2
QueuePush(&q, 3);//1 2 3
QueuePush(&q, 4);//1 2 3 4
printf("%d ", QueueFront(&q));//1
printf("%d ", QueueBack(&q));//4
//对头出队列
QueuePop(&q);//2 3 4
printf("%d ", QueueFront(&q));//2
printf("%d ", QueueBack(&q));//4
printf("%d", QueueSize(&q));//3
//while (!QueueEmpty(&q))
//{
// printf("%d ", QueueFront(&q));
// QueuePop(&q);
//}
//销毁
QueueDestroy(&q);
return 0;
}
***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:“没有永恒的梅雨季，只有久违的艳阳天”。
我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！
好了划走吧。
