文章目录
一、栈
💦 栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。 栈中的数据元素遵守后进先出LIFO (Last In First Out) 的原则；同时对于栈来说，一种入栈顺序对应多种出栈顺序
栈有两个经典的操作
1️⃣ 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
2️⃣ 出栈：栈的删除操作叫做出栈。出数据也在栈顶 。
💦 栈的实现
这里对于栈的实现我们既可以选择数组也可以和选择链表两者的效率都差不多，但是还是建议使用数组
1.初始化
函数原型
函数实现
void StackInit(ST* ps) { assert(ps); //初始化 ps->a = NULL; ps->top = 0; ps->capacicy = 0; }
2.插入
函数原型
函数实现
void StackPush(ST* ps, STDatatype x) { assert(ps); //检查空间，满了就增容 if (ps->top == ps->capacicy) { //第一次开辟空间容量为4，其它次容量为当前容量*2 int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2; //第一次开辟空间，a指向空，realloc的效果同malloc STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity); //检查realloc //realloc失败 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } //realloc成功 ps->a = tmp; ps->capacicy = newcapacity; } //插入数据 ps->a[ps->top] = x; ps->top++; }
3.判空
函数原型
函数实现
bool StackEmpty(ST* ps) { assert(ps); //等于0是真，否则为假 return ps->top == 0; }
4.删除
函数原型
函数实现
void StackPop(ST* ps) { assert(ps); //删除的话得保证指向的空间不为空 assert(!StackEmpty(ps)); //删除 --ps->top; }
5.长度
函数原型
函数实现
int StackSize(ST* ps) { assert(ps); //此时的top就是长度 return ps->top; }
6.栈顶
函数原型
函数实现
STDatatype StackTop(ST* ps) { assert(ps); //找栈顶的话得保证指向的空间不为空 assert(!StackEmpty(ps)); //此时的top-1就是栈顶数据 return ps->a[ps->top - 1]; }
7.销毁
函数原型
函数实现
void StackDestory(ST* ps) { assert(ps); //a为真代表它指向动态开辟的空间 if (ps->a) { free(ps->a); } ps->a = NULL; ps->top = 0; ps->capacicy = 0; }
💦 完整代码
这里需要三个文件
1️⃣ Static.h，用于函数的声明
2️⃣ Static.c，用于函数的定义
3️⃣ Test.c，用于测试函数
🧿 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 capacicy; //容量 }ST; //函数 //注意链表和顺序表我们写Print，但是栈不写，因为如果栈可以Print的话，就不符合后进先出了 //初始化 void StackInit(ST* ps); //插入 void StackPush(ST* ps, STDatatype x); //判空 bool StackEmpty(ST* ps); //删除 void StackPop(ST* ps); //长度 int StackSize(ST* ps); //栈顶 STDatatype StackTop(ST* ps); //销毁 void StackDestory(ST* ps);
🧿 Stack.c
#include"Stack.h" void StackInit(ST* ps) { assert(ps); //初始化 ps->a = NULL; ps->top = 0; ps->capacicy = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); //检查空间，满了就增容 if (ps->top == ps->capacicy) { //第一次开辟空间容量为4，其它次容量为当前容量*2 int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2; //第一次开辟空间，a指向空，realloc的效果同malloc STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity); //检查realloc //realloc失败 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } //realloc成功 ps->a = tmp; ps->capacicy = newcapacity; } //插入数据 ps->a[ps->top] = x; ps->top++; } bool StackEmpty(ST* ps) { assert(ps); //等于0是真，否则为假 return ps->top == 0; } void StackPop(ST* ps) { assert(ps); //删除的话得保证指向的空间不为空 assert(!StackEmpty(ps)); //删除 --ps->top; } int StackSize(ST* ps) { assert(ps); //此时的top就是长度 return ps->top; } STDatatype StackTop(ST* ps) { assert(ps); //找栈顶的话得保证指向的空间不为空 assert(!StackEmpty(ps)); //此时的top-1就是栈顶数据 return ps->a[ps->top - 1]; } void StackDestory(ST* ps) { assert(ps); //a为真代表它指向动态开辟的空间 if (ps->a) { free(ps->a); } ps->a = NULL; ps->top = 0; ps->capacicy = 0; }
🧿 Test.c
#include"Stack.h" int main() { ST st; //初始化 StackInit(&st); //插入+删除 StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); StackPop(&st); StackPop(&st); //长度 StackSize(&st); //栈顶 StackTop(&st); //销毁 StackDestory(&st); return 0; }
二、队列
💦 队列的概念及结构
相比栈，队列的特性和栈是相反的。 它只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO (First In First Out) 的特性。 入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头 对于队列来说，一种入队顺序，只有一种出队顺序
队列的拓展：
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
为了能使用Q.rear == Q.front 来区别是队空还是队满,我们常常认为出现左图时的情况即为队空的情况，此时: rear == front；而右图的情况即为队满的情况，此时：rear + 1 == front
关于环形队列在下面的的栈和队列面试题中会讲到
队列的应用：
1️⃣ 实际中要保证公平排队的地方可以用它
2️⃣ 广度优先遍历
💦 队列的实现
这里对于队列的实现我们使用链表的方式
1.初始化
函数原型
函数实现
void QueueInit(Queue* pq) { assert(pq); //把2个指针置空 pq->phead = pq->ptail = NULL; }
2.插入
函数原型
函数实现
void QueuePush(Queue* pq, QDataType x) { assert(pq); //malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; //第一次插入 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } //非第一次插入 else { pq->ptail->next = newnode; pq->ptail = newnode; } }
3.判空
函数原型
函数实现
bool QueueEmpty(Queue* pq) { assert(pq); //空链表返回true，非空链表返回false return pq->phead == NULL; }
4.删除
函数原型
函数实现
void QueuePop(Queue* pq) { assert(pq); //链表为空时不能删除 assert(!QueueEmpty(pq)); //只有一个节点的情况 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } //多个节点的情况 else { QueueNode* next = pq->phead->next; free(pq->phead) ; pq->phead = next; } }
5.长度
函数原型
函数实现
QDataType QueueSize(Queue* pq) { assert(pq); //如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度 int sz = 0; QueueNode* cur = pq->phead; while (cur) { sz++; cur = cur->next; } return sz; }
6.取头
函数原型
函数实现
QDataType QueueFront(Queue* pq) { assert(pq); //链表为空时不能取头 assert(!QueueEmpty(pq)); return pq->phead->data; }
7.取尾
函数原型
函数实现
QDataType QueueBack(Queue* pq) { assert(pq); //链表为空时不能取尾 assert(!QueueEmpty(pq)); return pq->ptail->data; }
8.销毁
函数原型
函数实现
void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur = pq->phead; //遍历链表 while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; }
💦 完整代码
这里需要三个文件
1️⃣ Queue.h，用于函数的声明
2️⃣ Queue.c，用于函数的定义
3️⃣ Test.c，用于测试函数
🧿 Queue.h
#pragma once //头 #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> //结构体 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; //指向下一个节点 QDataType data; //存储整型数据 }QueueNode; typedef struct Queue { QueueNode* phead;//头指针 QueueNode* ptail;//尾指针 }Queue; //函数 void QueueInit(Queue* pq); void QueuePush(Queue* pq, QDataType x); bool QueueEmpty(Queue* pq); void QueuePop(Queue* pq); QDataType QueueSize(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); void QueueDestory(Queue* pq);
🧿 Queue.c
#include"Queue.h" void QueueInit(Queue* pq) { assert(pq); //把2个指针置空 pq->phead = pq->ptail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); //malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; //第一次插入 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } //非第一次插入 else { pq->ptail->next = newnode; pq->ptail = newnode; } } bool QueueEmpty(Queue* pq) { assert(pq); //空链表返回true，非空链表返回false return pq->phead == NULL; } void QueuePop(Queue* pq) { assert(pq); //链表为空时不能删除 assert(!QueueEmpty(pq)); //只有一个节点的情况 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } //多个节点的情况 else { QueueNode* next = pq->phead->next; free(pq->phead) ; pq->phead = next; } } QDataType QueueSize(Queue* pq) { assert(pq); //如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度 int sz = 0; QueueNode* cur = pq->phead; while (cur) { sz++; cur = cur->next; } return sz; } QDataType QueueFront(Queue* pq) { assert(pq); //链表为空时不能取头 assert(!QueueEmpty(pq)); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); //链表为空时不能取尾 assert(!QueueEmpty(pq)); return pq->ptail->data; } void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur = pq->phead; //遍历链表 while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; }
🧿 Test.c
#include"Queue.h" int main() { //1、传二级指针 //2、返回值 //3、带哨兵位的头节点 //4、嵌套结构体 (这里使用这种方式) QueueNode q; //初始化 QueueInit(&q); //插入 QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //删除 QueuePop(&q); QueuePop(&q); //取头 QueueFront(&q); //取尾 QueueBack(&q); //释放 QueueDestory(&q); return 0; }
