💓1.栈
💞1.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
💞2.栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
💞 3.代码实现
💘1.总体实现
1.栈的初始化
void STInit(ST* pst);
2.释放了动态数组中的空间
void STDestroy(ST* pst);
3.入栈操作
void STPush(ST* pst, STDataType x);
4. 栈顶元素删除
void STPop(ST* pst);
5.获取栈顶元素
STDataType STTop(ST* pst);
6.判断栈（ST）是否为空
bool STEmpty(ST* pst);
7.获取栈大小
int STSize(ST* pst);
💘2.详细解析
💔1.栈的初始化
void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = 0; // 表示top指向栈顶元素的下一个位置 pst->top = 0; // 表示top指向栈顶元素 //pst->top = -1; }
这是一个栈的初始化函数，函数定义如下：
void STInit(ST* pst);
其中，ST是一个结构体类型，包含栈元素的数组指针a，栈的容量capacity，以及指向栈顶元素的下一个位置的指针top。
函数内部的实现如下：
assert(pst); // 检查指针参数是否为NULL pst->a = NULL; // 初始化栈元素数组指针为NULL pst->capacity = 0; // 初始化栈的容量为0 // 表示top指向栈顶元素的下一个位置 pst->top = 0; // 表示top指向栈顶元素 //pst->top = -1;
函数内部的注释提供了两种实现方式，表示top指针的指向方式：
pst->top = 0; 表示top指向栈顶元素的下一个位置。例如，初始状态下栈被认为是空的，因此top指向数组的第一个位置（即下标为0的位置）。
pst->top = -1; 表示top指向栈顶元素。例如，初始状态下栈被认为是空的，因此top指向数组最后一个位置（即下标为capacity-1的位置）。在这种情况下，当向栈中压入第一个元素时，需要先将top指向0，表示栈中有一个元素，而不是-1。
💔2.释放了动态数组中的空间
void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; }
该函数释放了动态数组中的空间，并将栈中保存的指针置为 NULL，防止出现悬挂指针的情况。
具体分析：
assert(pst);
该语句使用 assert 宏函数判断传入的指针 pst 是否为空，如果为空将会出现错误。
free(pst->a);
该语句使用 free 函数释放了动态数组 a 所占用的空间。
pst->a = NULL;
将栈中保存的数组指针 a 置为 NULL，防止出现悬挂指针的情况。
pst->top = pst->capacity = 0;
将栈中保存的元素数量 top 和数组容量 capacity 置为 0，表示栈已经被清空了。
💔3.入栈操作
该函数用于将元素x压入栈中。
函数中的assert(pst)用于确保输入的栈指针pst不为空。
当栈已满时，需要重新分配更大的内存空间以存储更多的元素。在这里，使用动态内存分配函数realloc()来重新分配空间。如果分配失败，则会输出错误信息并返回。
当空间分配成功后，元素x将被添加到栈的顶部，pst->top会自增，表示该栈顶指针已向上移动一位。
最后，该函数会在操作完成后返回。
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++; }
💔4. 栈顶元素删除
首先使用assert宏函数对传入的指针pst进行断言，确保其不为空。然后再次使用assert宏函数，判断栈顶指针top是否大于0，确保栈中有元素可以弹出。最后将top指针减1，实现弹出栈顶元素的操作。
void STPop(ST* pst) { assert(pst); // 不为空 assert(pst->top > 0); pst->top--; }
💔 5.获取栈顶元素
首先使用断言（assert）判断指针是否为空，如果为空则程序会崩溃。
接着判断栈顶是否大于0，如果不大于0则说明栈中无元素，也会导致程序崩溃。
最后返回栈顶元素，由于是取栈顶元素，所以要使用栈顶指针（top）减1来访问栈顶元素。
STDataType STTop(ST* pst) { assert(pst); // 不为空 assert(pst->top > 0); return pst->a[pst->top - 1]; }
💔6.判断栈（ST）是否为空
函数中的参数 pst 是一个指向栈的指针，使用 assert 宏对其进行断言，确保其不为空。
这个函数主要通过判断栈顶指针（top）是否为 0 来确定栈是否为空。如果 top 等于 0，那么栈中没有任何元素，函数返回 true，表示栈为空；否则返回 false，表示栈中还有元素。
STDataType STTop(ST* pst) { assert(pst); // 不为空 assert(pst->top > 0); return pst->a[pst->top - 1]; }
💔7.获取栈大小
栈的大小是指当前栈中元素的数量。
参数pst是一个指向栈的指针，函数内部调用了assert(pst)来判断指针是否为空，如果为空则直接终止程序的执行。
函数返回值为栈的大小，即栈顶指针top的值。在使用该函数之前，需要确保栈已经被初始化。
int STSize(ST* pst) { assert(pst); return pst->top; }
💘3.整体代码
💔1.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);
💔2.Stach.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; }
💔3.test.c
#include"Stack.h" int main() { ST s; STInit(&s); STPush(&s, 1); STPush(&s, 2); STPush(&s, 3); printf("%d ", STTop(&s)); STPop(&s); printf("%d ", STTop(&s)); STPop(&s); STPush(&s, 4); STPush(&s, 5); // 一 对 多 // 入栈顺序 -- 出栈顺序 while (!STEmpty(&s)) { printf("%d ", STTop(&s)); STPop(&s); } printf("\n"); return 0; }
💓2.队列
💞1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
💞2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
💞3.代码实现
💘1.总体实现
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
💘2. 详细解析
💔1.初始化队列
参数是一个指向Queue结构体的指针。
首先利用assert()函数检查pq指针是否为空，若为空则程序会终止运行，避免出现不可预知的错误。
然后，将队列的头指针phead和尾指针ptail都置为空，即队列初始时是空的。队列的大小size也被初始化为0，表示队列中没有元素。
整个函数的逻辑比较简单，主要目的是将队列的各个成员变量初始化为合适的初始值，以便后续实现队列的相关操作。
void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; }
💔2.销毁队列
参数是一个指向队列的指针。
首先，使用 assert 函数检查指针 pq 是否为空，如果为空则程序直接终止。
然后，定义一个指针 cur 指向队列头部元素。使用 while 循环，遍历整个队列：将 cur 的下一个元素指向 next，再将 cur 释放掉。cur 等于 next，继续遍历。 最后将队列的头部指针 pq->phead 和尾部指针 pq->ptail 都指向 NULL，队列大小 pq->size 置为 0。
这个函数的作用是遍历整个队列，逐个释放节点所占用的空间，防止内存泄漏。
void QueueDestroy(Queue* 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; }
💔3.往队列中插入一个元素
函数参数说明：
- pq：指向队列的指针，需要保证指针非空。
- x：插入队列的元素值。
函数实现：
1. 判断指向队列的指针是否为空，如果为空，则直接返回。
2. 申请一个新节点，并判断申请是否成功。如果申请失败，则打印错误信息并返回。
3. 设置新节点的值为要插入的元素值x，将新节点的next指针置为NULL。
4. 如果队列为空，则将队列的头指针和尾指针都指向新节点。
5. 如果队列非空，则将尾节点的next指针指向新节点，然后将尾节点指针指向新节点。
6. 更新队列的元素数量。
7. 函数结束。
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { pq->ptail = pq->phead = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
💔4.队列的出队
第一行代码使用断言(assert)来确保队列指针pq的非空性，若为空则会停止程序运行。
第二行代码使用断言(assert)来确保队列头指针(pq->phead)的非空性，若为空则会停止程序运行。
第三行代码定义一个结构体指针del，用来指向将要被删除的节点。
第四行代码将队列头指针(pq->phead)指向下一个节点，即将队头出队，并将该节点的内存释放。
第五至八行代码判断队列是否为空队列，如果是则将队尾指针(pq->ptail)也置为空指针，否则不需要做任何操作。
最后一行代码将队列的大小(size)减少1。
void QueuePop(Queue* pq) { assert(pq); // assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); del = NULL; if (pq->phead == NULL) pq->ptail = NULL; pq->size--; }
💔5.获取队列头部元素
输入参数为一个指向队列的指针pq，返回值为队列头部元素的值。其中使用了assert宏来进行断言，确保pq和pq->phead都不为NULL，如果其中任意一个为NULL则会触发断言失败，程序会崩溃。最后返回pq->phead的值。
QDataType QueueFront(Queue* pq) { assert(pq); // assert(pq->phead); return pq->phead->val; }
💔6.获取队列最后一个元素
函数签名说明：
QDataType是一个数据类型，用于表示队列中元素的类型；
Queue是一个结构体类型，表示队列；
Queue* pq表示指向队列的指针。
函数实现：
首先，使用assert()宏函数对传入的参数进行断言处理，确保指针pq和队列的尾指针ptail都不为空。
然后，返回队列尾部节点（即最后一个元素）的值，即pq->ptail->val。由于队列的尾指针指向的就是队列的尾部节点，所以可以直接通过ptail获取队列尾部节点的值。
整个函数逻辑简单，实现了获取队列最后一个元素的功能。
QDataType QueueBack(Queue* pq) { assert(pq); // assert(pq->ptail); return pq->ptail->val; }
💔7.判断队列是否为空
参数pq是一个指向Queue类型的指针，assert(pq)用于判断pq是否为空。函数返回队列的头节点是否为空，如果为空则队列为空，返回true；否则返回false。
bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
💔8.获取队列当前元素数量
它接受一个指向队列结构体的指针作为参数。
第一行使用了assert宏，它会检查参数pq是否为空指针，如果是则程序会中止运行并输出错误信息。
第三行直接返回队列结构体中的size成员，即队列当前的元素数量。
int QueueSize(Queue* pq) { assert(pq); return pq->size; }
💘3.整体代码
💔1.Queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq);
💔2.Queue.c
#include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* 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; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { pq->ptail = pq->phead = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } // 17:10 void QueuePop(Queue* pq) { assert(pq); // assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); del = NULL; if (pq->phead == NULL) pq->ptail = NULL; pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); // assert(pq->phead); return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq); // assert(pq->ptail); return pq->ptail->val; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
💔3.Test.c
#include"Queue.h" int main() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); printf("%d ", QueueFront(&q)); QueuePop(&q); printf("%d ", QueueFront(&q)); QueuePop(&q);
