目录一、栈1.1 栈的基本概念1.2 栈的代码实现1.2.1 定义结构体成员以及方法1.2.2 初始化栈1.2.3 销毁栈1.2.4 插入数据1.2.5 判断栈是否存入数据1.2.6 弹出栈顶元素1.2.7 查看栈的当前有效长度1.2.8 查看当前栈顶元素1.2.9 测试二、队列2.1 队列的基本概念2.2 队列的代码实现2.2.1 定义结构体成员以及方法2.2.2 初始化队列2.2.3 销毁队列2.2.4 插入数据2.2.5 弹出队头元素2.2.6 查看当前有效长度2.2.7 判断队列是否存入数据2.2.8 查看队头元素2.2.9 查看队尾元素2.2.10 测试三、总结一、栈1.1 栈的基本概念栈Stack是只允许在一端进行插入或删除的线性表。首先栈是一种线性表但限定这种线性 表只能在某一端进行插入和删除操作。栈顶Top线性表允许进行插入删除的那一端。栈底Bottom固定的不允许进行插入和删除的另一端。空栈不含任何元素的空表。栈又称为后进先出Last In First Out的线性表简称LIFO结构就像图中这样1.2 栈的代码实现了解完上面的概念之后我们就可以用代码来实现它。(请注意下面的代码均是用 C 语言来编写的)1.2.1 定义结构体成员以及方法代码如下#pragma once #includestdio.h #includestdlib.h #includestdbool.h #includeassert.h typedef int STDataType; typedef struct Stack { //a指向动态分配数组的指针用于存储栈中的元素数据。 //top表示栈顶的位置通常指向栈顶元素的下一个位置或当前栈顶元素的位置同时也可以表示栈中元素的个数。 //capacity表示当前动态数组的总容量即最多能存储多少个元素。 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); //查看栈的当前长度 int STSize(ST* ps); //判断栈是否为 NULL bool STEmpty(ST* ps); //查看当前栈顶元素 STDataType STTop(ST* ps);有人看完代码之后可能会感到疑问为啥要使用数组来存储栈的元素了链表不可以吗理由如下因为栈只在一端也就是在栈顶上进行插入和删除数组的尾部操作时间复杂度为 O(1)且内存连续、缓存命中率高、性能更好。链表虽然也能实现但每个节点需要额外存储指针内存开销大且频繁申请释放节点效率较低。数组实现更简单高效所以通常选用数组。1.2.2 初始化栈代码如下void STInit(ST* ps) { assert(ps); // 初始化栈给 ps-a 分配4个元素空间 ps-a (STDataType*)malloc(sizeof(STDataType) * 4 ); if (ps-a NULL) { perror(malloc error); return NULL; } //ps-top -1; //代表当前栈顶元素 ps-top 0;//这个代表是栈顶元素的下一个位置 //代表当前可以存放4个元素 ps-capacity 4; }1.2.3 销毁栈代码如下void STDestroy(ST* ps) { //判断传来的值是否为NULL assert(ps); //ps-a 指向的是一整块连续动态分配的内存数组 //所以直接 free(ps-a) 就可以完成 free(ps-a); ps-top 0; ps-capacity 0; }1.2.4 插入数据代码如下void STPush(ST* ps, STDataType x) { assert(ps); //检查当前容量是否满了 if (ps-top ps-capacity) { //满了的话就扩容两倍这个是内存扩容 STDataType* tmp (STDataType*)realloc(ps-a,sizeof(STDataType) * ps-capacity * 2); if (tmp NULL) { perror(realloc error); return NULL; } //将新扩容容量的地址赋值给ps-a ps-a tmp; //将原来的容量扩大二倍改变原来的值这个是值扩大二倍不影响内存的 ps-capacity * 2; } //将新元素放入栈顶 ps-a[ps-top] x; //top往上移动一位等待下一个栈顶元素的到来 ps-top; }1.2.5 判断栈是否存入数据代码如下bool STEmpty(ST* ps) { assert(ps); //就看当前有没有栈顶元素 //top 0 就表示当前没有元素存入 return ps-top 0; }1.2.6 弹出栈顶元素代码如下void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); //防止栈里面没有元素 ps-top--;//直接让 top 的位置往下移一位 }1.2.7 查看栈的当前有效长度代码如下int STSize(ST* ps) { assert(ps); //如果初始化定义top 0的话top的值就是栈的有效长度(也就是当前存入了多少值) //如果初始化定义top -1的话top 1的值就是栈的有效长度 //跟数组下标求长度一个道理 return ps-top; }1.2.8 查看当前栈顶元素代码如下STDataType STTop(ST* ps) { assert(ps);//防止栈里面没有元素 assert(!STEmpty(ps)); //因为 top 表示栈顶元素的下一个位置所以就用 ps-top - 1 来表示栈顶元素 return ps-a[ps-top - 1]; }1.2.9 测试测试代码#includeStack.h void test() { ST ps; STInit(ps); STPush(ps, 1); STPush(ps, 22); STPush(ps, 3); STPop(ps); STDataType x STTop(ps); printf(栈顶元素为%d\n, x); int size STSize(ps); printf(当前有效长度为%d\n, size); STDestroy(ps); } int main() { test(); return 0; }这里不需要将ps置为NULL的原因是因为 ps 是在 main 函数中定义的局部变量ST ps不是指针。STDestroy(ps) 传入的是 ps 的地址函数内部释放了 ps.a 指向的动态内存并将 ps.top 和 ps.capacity 置 0但 ps 本身作为局部变量在 test 函数返回后会自动销毁其生命周期结束所以不需要将 ps 置为 NULL。测试结果执行销毁栈函数之前执行销毁栈函数之后打印的结果二、队列2.1 队列的基本概念队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。队头Front允许删除的一端又称队首。队尾Rear允许插入的一端。空队列不包含任何元素的空表。2.2 队列的代码实现2.2.1 定义结构体成员以及方法代码如下#pragma once #includestdio.h #includestdlib.h #includestdbool.h #includeassert.h typedef int QDatatype; typedef struct QueueNode { QDatatype data; struct QueueNode* next; }QNode; typedef struct Queue { //为了确定单链表的头后面简称队头 QNode* head; //为了确定单链表的尾后面简称队尾 QNode* tail; int size; }Queue; //初始化 void QueueInit(Queue* pq); //销毁队列 void QueueDestroy(Queue* pq); //插入数据 void QueuePush(Queue* pq, QDatatype x); //弹出队头元素 void QueuePop(Queue* pq); //查看当前有效长度 int QueueSize(Queue* pq); //判断队列是否存入数据 bool QueueEmpty(Queue* pq); //查看队头元素 QDatatype QueueFront(Queue* pq); //查看队尾元素 QDatatype QueueBack(Queue* pq);为啥使用单链表而不使用双链表或数组理由如下因为队列只需要在队尾插入在队头删除单链表正好满足这个需求。使用单链表的原因时间复杂度最优单链表有 head 和 tail 指针入队在 tail 后插入O(1)出队在 head 后删除O(1)效率最高。不需要双向队列不需要从后往前遍历或删除尾部节点所以不需要 prev 指针单链表更节省内存。动态扩展方便链表节点按需分配无需像数组那样考虑扩容问题。结构简单单链表实现比双链表或循环链表更简洁。为啥要定义两个结构体理由如下因为一个结构体只能描述单一对象而队列需要两种不同的对象节点结构体QNode描述每个元素本身包含数据和指向下一个节点的指针。队列结构体Queue描述整个队列的管理信息包含头指针、尾指针和大小。如果只用一个结构体要么只能表示单个节点无法管理整条链要么只能表示队列头尾无法存储每个元素的数据和链接无法同时满足两个需求。所以必须用两个结构体。2.2.2 初始化队列代码如下void QueueInit(Queue* pq) { assert(pq); //因为此时没有元素插入就将它们指向 NULL 即可 pq-head pq-tail NULL; pq-size 0; }2.2.3 销毁队列代码如下void QueueDestroy(Queue* pq) { assert(pq); QNode* cur pq-head; while (cur) { QNode* next cur-next; free(cur); cur next; } //因为 free(cur) 释放的是每个节点指向的动态内存 //但 pq-head 和 pq-tail 这两个指针变量本身存储的地址值并没有被清空 //它们仍然指向已经被释放的内存地址。将 pq-head 和 pq-tail 置为 NULL //是为了防止后续误用这两个野指针。 pq-head pq-tail NULL; pq-size 0; }2.2.4 插入数据代码如下void QueuePush(Queue* pq, QDatatype x) { assert(pq); //将 x 转换为单链表节点 QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc error); return; } newnode-data x; newnode-next NULL; //判断是否为第一个元素插入 if (pq-head NULL) { //是的话就将队头和队尾指向这个节点 assert(pq-tail NULL); pq-head pq-tail newnode; } else { //不是的话就只需要移动队尾就可以了队头不需要动 pq-tail-next newnode; pq-tail newnode; } //然后有效长度 1 pq-size; }2.2.5 弹出队头元素代码如下void QueuePop(Queue* pq) { assert(pq); //这一步判断是防止 pq 这个单链表里面有没有存入数据 assert(pq-head ! NULL); //看是否只有队头一个元素 if (pq-head-next NULL) { //如果是就释放队头元素的内存空间 free(pq-head); //将它俩置为 NULL防止后面变成野指针 pq-head pq-tail NULL; } else { //如果不是 //就查看队头的下一个元素将它记录一下 QNode* next pq-head-next; //然后释放队头元素的内存空间 free(pq-head); //将新队头指向到原来的队头的下一个元素 pq-head next; } //有效长度 -1 pq-size--; }2.2.6 查看当前有效长度代码如下int QueueSize(Queue* pq) { assert(pq); return pq-size; }2.2.7 判断队列是否存入数据代码如下bool QueueEmpty(Queue* pq) { assert(pq); //有效长度等于0即为队列里面没有数据 return pq-size 0; }2.2.8 查看队头元素代码如下QDatatype QueueFront(Queue* pq) { assert(pq); //这一步判断是防止 pq 这个单链表里面有没有存入数据 assert(!QueueEmpty(pq)); //然后就直接返回 队头 元素就好了 return pq-head-data; }2.2.9 查看队尾元素代码如下QDatatype QueueBack(Queue* pq) { assert(pq); //这一步判断是防止 pq 这个单链表里面有没有存入数据 assert(!QueueEmpty(pq)); //然后直接返回队尾元素就好了 //所以这就是定义两个结构体的好处 //不然你取队尾元素的话还需要遍历链表才能取到最后一个节点。 return pq-tail-data; }2.2.10 测试测试代码#include Queue.h void test(Queue* pq) { QueueInit(pq); QueuePush(pq, 1); QueuePush(pq, 2); QueuePush(pq, 3); QueuePush(pq, 4); QueuePush(pq, 5); QueuePop(pq); int length QueueSize(pq); QDatatype front QueueFront(pq); QDatatype tail QueueBack(pq); printf(队列长度为%d ,队头元素是%d,队尾元素是%d, length,front, tail); QueueDestroy(pq); } int main() { Queue node; test(node); return 0; }测试结果执行销毁队列函数之前执行销毁队列函数之后三、总结以上便是我对栈和队列部分的全部理解了。有啥不好的地方也欢迎大家积极指出希望大家早日被自己喜欢的offer录取。那我们就下一个博客见。