目录
![8fb442646f144d8daecdd2b61ec78ecd.png](https://aitechtogether.com/wp-content/uploads_new/2024/02/f3f3dc1c-89bf-49c8-bfe7-121c097ea0bc.webp)
一.前言
![8fb442646f144d8daecdd2b61ec78ecd.png](https://aitechtogether.com/wp-content/uploads_new/2024/02/f3f3dc1c-89bf-49c8-bfe7-121c097ea0bc.webp)
如果有友友看了我上一篇文章:数据结构——单链表,那么本篇的队列和栈你会发现到处是单链表的影子,所以我们的重心是在关于队列和栈的OJ题上。本文干货满满,高能不断,一定不要错过!码字不易,希望大家多多支持我呀!(三连+关注,你是我滴神!)
二.前文回顾
顺序表和链表的区别
三.栈
3.1 栈的概念及结构
- 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
- 压栈: 栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈,出数据也在栈顶。
3.2 栈的实现
其实数组或者链表都是可以实现栈的,二者区别无法就是实现的方式有所不同,效率各有千秋。
- 要想用数组实现的话,那数组尾部就可以作为栈顶(尾插尾删方便)。
- 要想用链表实现的话,那链表头部得作为栈顶,然后进行多次头插入栈(这样出栈时方便,用头删即可)。想想如果是栈顶是在1的位置,那到时候出栈删除1时还得找到2进行重新链接,要用到双链表。所以我们的原则是能用单链表实现就用单链表~
相对而言,数组更合适实现栈~
3.2.1 初始化函数
这里有一点需要注意,当top一开始是0的时候,入栈完top++指向下一位.这样当我们打算输入(入栈)最后一个数据时,真正的栈顶并非top所指向的数据,而是top-1的指向。
//初始化函数 void STInit(ST* ps) { assert(ps); ps->top = 0; ps->a = NULL; ps->capacity = 0; }
3.2.2 销毁函数
//销毁函数 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
3.2.3 入栈函数
在准备扩容的时候一开始空间是0为什么这里可以用realloc来代替malloc呢?realloc不是只能在已有空间基础上扩容吗?
如果一开始没有空间,那么realloc在这时候是可以代替malloc来作出对于功能的。(为空可当成malloc,不为空就realloc)
//入栈函数 void STPush(ST* ps, STDataType x) { assert(ps); //扩容准备 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)relloc(ps->a, sizeof(STDataType)*newCapacity); if (tmp == NULL) { perror("relloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } //入栈准备 ps->a[ps->top] = x; ps->top++; }
3.2.4 出栈函数
出栈挺简单,唯一要注意的就是当栈为空的时候,就不要继续出栈了。
//出栈函数 void STPop(ST* ps) { assert(ps); //空 assert(ps->top > 0); ps->top--; }
3.2.5 计算大小函数
//计算大小函数 int STSize(ST* ps) { assert(ps); return ps->top; }
3.2.6 空栈函数
//判空(栈)函数 bool STEmpty(ST* ps) { assert(ps); return ps->top==0; }
看top指向是否空,如果为空则会返回1,不为空则返回0.
3.2.7 获取栈顶函数
//获取栈顶函数 STDataType STTop(ST* ps) { assert(ps); //空 assert(ps->top > 0); return ps->a[ps->top - 1]; }
3.2.8 小测试
最后我们来测试是否满足栈的特点:后进先出
void TestStack1() { ST st; STInit(&st); STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st);//获取后一位的栈顶 } printf("\n"); STDestroy(&st); }
3.3 全部代码
//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* ps); //销毁函数 void STDestroy(ST* ps); //入栈函数 void STPush(ST* ps, STDataType x); //出栈函数 void STPop(ST* ps); //计算大小函数 int STSize(ST* ps); //空(栈)函数 bool STEmpty(ST* ps); //获取栈顶函数 STDataType STTop(ST* ps);
——————————————————————————————-——————————
//Test,c #define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" void TestStack1() { ST st; STInit(&st); STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st);//获取后一位的栈顶 } printf("\n"); STDestroy(&st); } int main() { TestStack1(); return 0; }
——————————————————————————————————————————
//Stack,c #define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" //初始化函数 void STInit(ST* ps) { assert(ps); ps->top = 0; ps->a = NULL; ps->capacity = 0; } //销毁函数 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //入栈函数 void STPush(ST* ps, STDataType x) { assert(ps); //扩容准备 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("relloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } //入栈准备 ps->a[ps->top] = x; ps->top++; } //出栈函数 void STPop(ST* ps) { assert(ps); //空 assert(ps->top > 0); ps->top--; } //计算大小函数 int STSize(ST* ps) { assert(ps); return ps->top; } //空(栈)函数 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } //获取栈顶函数 STDataType STTop(ST* ps) { assert(ps); //空 assert(ps->top > 0); return ps->a[ps->top - 1]; }
其实写到最后我们可以发现,栈其实就是顺序表的简化版,相当于定义了部分适用于栈特征的接口罢了~
四.栈的练习
4.1 有效的括号
链接:力扣——有效的括号
基本思路:
- 数量上最后再进行判断~
- 类型上:遇到右括号就进行匹配,看有没有对应的左括号。
- 顺序上:当遇到右括号时判断距离最进的括号是否为对应左括号。
那如何找到最近的括号呢?
- 左括号,入栈
- 右括号,出栈顶括号,进行匹配
//前面需要用到Stack.h与Stack.c的代码 bool isValid(char* s) { ST st; STInit(&st); char topVal; while (*s) { //左括号入栈 if (*s == '(' || *s == '[' || *s == '{') { STPush(&st, *s); } //右括号判定 else { //数量不匹配——如果栈中没有左括号, //说明在s中右括号在左括号前面,那肯定是不行的 if (STEmpty(&st)) { STDestroy(&st); return false; } //在这一步说明栈中有左括号 topVal = STTop(&st);//把栈顶的左括号存入topVal中 STPop(&st);//压栈,使得下一次取排在栈顶前一位的左括号 if ((*s == ']' && topVal != '[') || (*s == ')' && topVal != '(') || (*s == '}' && topVal != '{')) //这里我们不去判定括号与括号的对应, //去判断不对应的情况,这样筛选到最后的就是对应的 { STDestroy(&st);//如果在栈顶中取出的左括号与条件中目前 // 数组指向的右括号不对应,那就销毁栈并且返回错误 return false; } } ++s;//对数组中的每一个元素进行遍历 } //到了最后如果栈里面还有左括号,那么就说明数量对不上,在STEmpty(&st)判断为0 //如果栈里面没有左括号,那么在STEmpty(&st)判断为1 //栈不为空,flase,说明数量不匹配 bool ret = STEmpty(&st); STDestroy(&st); return ret; }
备注:千万不要想着去用switch,千万不要,除非你想要头脑风暴。。。。
五.队列
5.1队列的概念及结构
- 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。
- 入队列:进行插入操作的一端称为队尾。
- 出队列:进行删除操作的一端称为队头。
5.2 队列的实现
队列也可以用数组或链表的结构实现,使用链表的结构表现更优一些,因为数组在实现出队列(头删)效率比较低~
这里我们采用单链表结构进行实现队列,既然队列核心是一端出一端入,那我们就先预设头节点(head)与尾节点(tail)的指向。
因为是不带哨兵位,所以我们插入第一个节点时既要赋值给head,又要赋值给tail。并且还要用到二级,因为形参的改变影响不了实参。(这里也不能用return,我们这里要返回两个值。)如果有友友理解不了二级指针可以移步至这篇文章单链表,里面的尾插部分有详细讲解哦~
切回正题,在这里我们可以采用新的方法来实现二级指针的功能。
typedef struct Queue { QNode* head; QNode* tail; int size; }Que; //入队列函数 void QueuePush(Que* pq, QDataType x);
我们可以再建立一个结构体,里面放置头指针和尾指针,用结构体接收,这样就可以改变二者的指向了。
5.2.1 初始化函数
//初始化函数 void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
5.2.2 入队列函数
在我们处理好空间问题后,要进行入队列(尾插)就得先找到尾节点,不过这里还有一些小问题需要注意。
如果链表是空的呢?——赋值给它们2个
//入队列函数 void QueuePush(Que* pq, QDataType x) { assert(pq); //创造新节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } //给新节点插入数据 newnode->data = x; newnode->next = NULL; if (pq->tail==NULL)//链表为空时 { pq->head = pq->tail = newnode; } else//链表不为空时 { pq->head->next = newnode; pq->tail = newnode; } pq->size++; }
5.2.3 出队列函数
出队列其实就是头删,定义好下一位的指针next就可以实现了
不过这样写还有一个问题;在只剩下一个节点的时候,head可以顺利置空,但tail却没有置空变成了野指针。
//出队列函数 void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq));//空链表时不给删除 if (pq->head->next == NULL)//只剩下一个节点时 { pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; }
5.2.4 获取头队列函数
//获取头队列函数 QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
5.2.5 获取尾队列函数
//获取尾队列函数 QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
5.2.6 判空(队列)函数
//判空(队列)函数 bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; }
5.2.7 计算队列大小函数
//计算大小函数 int QueueSize(Que* pq) { assert(pq); return pq->size; }
5.2.8 销毁函数
//销毁函数 void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head;//创造一个方便遍历的指针 while (cur) { QNode* next = cur->next;//记录每一次销毁后一位的指针 free(cur); cur = next; } pq->head = pq->tail = NULL;//置空,避免野指针 pq->size = 0; }
5.2.9 小测试
void TestQueue() { Que q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); while (!QueueEmpty(&q))//遍历,链表不为空就继续 { printf("%d ", QueueFront(&q));//打印头队列 QueuePop(&q);//打印完就让其出队列 } printf("\n"); QueueDestroy(&q); }
成功实现先进先出。
5.3 全部代码
//Queue.h #pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que; //入队列函数 void QueuePush(Que* pq, QDataType x); //初始化函数 void QueueInit(Que* pq); //销毁函数 void QueueDestroy(Que* pq); //出队列函数 void QueuePop(Que* pq); //获取头队列函数 QDataType QueueFront(Que* pq); //获取尾队列函数 QDataType QueueBack(Que* pq); //判空(队列)函数 bool QueueEmpty(Que* pq); //计算大小函数 int QueueSize(Que* pq);
————-——————————————————————————————————————
//Queue.c #define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" //初始化函数 void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } //入队列函数 void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail==NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } //出队列函数 void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } //获取头队列函数 QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } //获取尾队列函数 QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } //判空(队列)函数 bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; } //计算大小函数 int QueueSize(Que* pq) { assert(pq); return pq->size; } //销毁函数 void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; }
———————————————————————————————————————————
//Test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" void TestQueue() { Que q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); while (!QueueEmpty(&q))//遍历,链表不为空就继续 { printf("%d ", QueueFront(&q));//打印头队列 QueuePop(&q);//打印完就让其出队列 } printf("\n"); QueueDestroy(&q); } int main() { TestQueue(); return 0; }
六.队列的练习
6.1选择题
学习完队列和栈我们可以知道,入队列是1 2 3 4 5那出队列就是1 2 3 4 5,那栈呢?也入栈1 2 3 4 5,出栈就一定是5 4 3 2 1吗?
第一问无疑是选B,那第二问又是怎么回事呢?我们看好这一句话“进栈过程可以出栈”,这意味着有多种可能性,其中最不可能的就是C选项了,3出栈前提是1 2 3入栈,那1出栈前提是1入栈,显然不符合事实。
6.2用队列实现栈
链接:力扣——用队列实现栈
typedef struct { } MyStack; MyStack* myStackCreate() { } void myStackPush(MyStack* obj, int x) { } int myStackPop(MyStack* obj) { } int myStackTop(MyStack* obj) { } bool myStackEmpty(MyStack* obj) { } void myStackFree(MyStack* obj) { }
6.2.1 整体思路:
我们先列出两个队列,然后往其中一个队列Push1 2 3 4,要想实现后入先出的栈,就得把4优先Pop出来 .
为了实现Pop4,我们可以依次出队列中队头数据把它插入到另一个队列里,当剩下最后一个数据4时再Pop掉(不继续插入到另一个队列)
当我们想让5,6入队列的时候又应该去哪里呢?——去不为空的队列,然后再重复上述的操作(把n个数据的前n-1个导走)最后Pop出6(后入先出) 。
所以大思路就是保持一个队列为空(导出数据),另一个不为空(存入数据)。
- 入队列:不为空的队列
- 出队列:不为空队列前N-1个出队列,插入空队列。删除剩余的数据。
代码解析:
MyStack* myStackCreate() {
MyStack st;
//......
return &st
}
这个接口的作用仅仅是返回&st吗?——这个局部作用域一出来那么里面的变量都会销毁,这时候传st的地址已经是没意思的了,它已经变成一个野指针了。为了保证MyStack的对象还在,我们可以改用malloc来创造节点,这样出作用域时,malloc出来的空间还是在的。
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
6.2.2 Push函数(入队列):
由于我们不知道哪个为空,哪个不为空,那么我们直接用判空条件来判断再进行入队列
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&obj->q1))//如果q1为空
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
6.2.3 Pop函数(出队列):
还是一样的逻辑,不为空的队列往空队列导入。在这里我们假设q1为空,q2不为空。如果q1不为空(判空函数)那交换即可。
int myStackPop(MyStack* obj) {
QNode* empty = &obj->q1;//假设q1为空
QNode* nonEmpty = &obj->q2;//假设q2不为空
if (!QueueEmpty(&obj->q1))//如果qi不为空
{
empty = &obj->q2;//交换
nonEmpty = &obj->q1;
}
//前size-1个导入空队列
while (QueueSize(nonEmpty) > 1)
{
QueuePush(empty, QueueFront(nonEmpty));
//进行入队列,在空队列中存入在不为空队列中的首个数据
QueuePop(nonEmpty);
//再Pop掉该数据,使下一次循环是首数据后面的数据
}//入一次出一次,直达剩下一个
//这时候只剩下一个数据,获取栈顶元素
int top = QueueFront(nonEmpty);//存储不为空队列中的元素
QueuePop(nonEmpty);//再Pop掉该元素
return top;//返回所谓的栈顶数据
//至此,该函数完全实现在2个队列入好数据后,
//结果返回的是后入队列的数据,实现了后进后出。
}
到这里大家是不是有疑惑,为什么都是&obj,到了empty传输时反而不用取地址了呢?
我们需要把类型认识清楚,q1与q2是队列的结构体,该结构体包含了头指针(head),尾指针(tail),和size。对于我们所要实现的接口(Pop,Push,Creat)而言,它们想要改变的都是结构体的指针(tail,head等)来实现自身功能。所以这里需要&obj,而empty与nonEmpty已经是结构体指针了,就相当于&obj,也就不需要&了。
6.2.4 Top函数(取栈顶):
这个函数要实现的功能是取栈顶元素,也就是取最后入队列的数据。这里我们可以直接复用前面所写的获取队列尾部数据函数( QueueBack)来轻松实现。
int myStackTop(MyStack* obj) {
//哪个队列不为空就去取该队列的尾部数据
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
6.2.5 Empty函数(判空):
在这里的判空应该是两个队列都为空,那才是空。一个为空的不算空。
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
6.2.6 Free(释放空间)函数:
这里我们不能直接free掉obj,因为在obj里面有两个队列q1,q2而这两个队列的底层是链表,所以我们在free之前记得使用销毁函数(QueueDestroy)(销毁链表)
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
6.2.7 全部代码
注:想要写题解或者测试,请自行添加上文关于Queue.c与Queue.h的代码段(下面代码能够复用的前提)
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&obj->q1))//如果q1为空
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj)
{
QNode* empty = &obj->q1;//假设q1为空
QNode* nonEmpty = &obj->q2;//假设q2不为空
if (!QueueEmpty(&obj->q1))//如果qi不为空
{
empty = &obj->q2;//交换
nonEmpty = &obj->q1;
}
//前size-1个导入空队列
while (QueueSize(nonEmpty) > 1)
{
QueuePush(empty, QueueFront(nonEmpty));
//进行入队列,在空队列中存入在不为空队列中的首个数据
QueuePop(nonEmpty);
//再Pop掉该数据,使下一次循环是首数据后面的数据
}//入一次出一次,直达剩下一个
//这时候只剩下一个数据,获取栈顶元素
int top = QueueFront(nonEmpty);//存储不为空队列中的元素
QueuePop(nonEmpty);//再Pop掉该元素
return top;//返回所谓的栈顶数据
//至此,该函数完全实现在2个队列入好数据后,
//结果返回的是后入队列的数据,实现了后进后出。
}
int myStackTop(MyStack* obj) {
//哪个队列不为空就去取该队列的尾部数据
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
最后附上结构图,帮助大家理解~
这也是我们为什么不能直接free掉obj的原因。
6.3用栈实现队列
链接:力扣——用栈实现队列
typedef struct {
} MyQueue;
MyQueue* myQueueCreate() {
}
void myQueuePush(MyQueue* obj, int x) {
}
int myQueuePop(MyQueue* obj) {
}
int myQueuePeek(MyQueue* obj) {
}
bool myQueueEmpty(MyQueue* obj) {
}
void myQueueFree(MyQueue* obj) {
}
6.3.1 整体思路:
老规矩我们先创造两个栈,其中一个依次输入1 2 3 4,要想实现队列的先进先出,那最终要Pop的数就是1.至此,我们可以沿用与上一题差不多的思路(先入栈,再出栈导到另一个栈,最后再处理1.)。
当我们把1Pop掉时再尝试Push5 6,把2 3 4导回去再入栈5 6继续重复上述操作是没问题的,那能不能不把2 3 4导回原来的栈呢?——这时候的情况就发生了变化:可以把2 3 4全部Pop掉,这样第二个栈就空了,再把5 6导入第二个栈最终可以Pop出5.
这时候我们就可以制定规则了
- pushst栈: 这个栈只能用来入栈。
- popst栈:这个栈只能用来出栈。
跟上题一样先搞出两个栈出来;
MyQueue* myStackCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
6.3.2 Push(入栈)函数
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst, x);
}
6.3.3 Peek(取头)函数
我们先来写Peek(获取头队列数据函数),要想获取首先得判断popst中是否为空,如果是空的我们需要从pushst中导出数据到popst里。这样才可以获取头队列数据。如果有友友对这里复用的函数命名不熟悉可以去目录对照查看。
int myQueuePeek(MyQueue* obj) {
//哪个队列不为空就去取该队列的尾部数据
if (STEmpty(&obj->popst))
{
//判断popst为空,开始导入数据
while (!STEmpty(&obj->pushst))
{
STPush(&obj->popst, STTop(&obj->pushst));//导入数据后再进行删除头队列数据
STPop(&obj->pushst);//导进一个删除一个,清空pushst
}
}
return STTop(&obj->popst);
}
6.3.4 Pop(出栈)函数
到这一步我们就可以发现先写Peek的好处了,因为Peek已经先判断popst是否为空,为空就把pushst的数据搬过来,所以我们只需要处理好popst里面的数据就好了。
int myQueuePop(MyQueue* obj)
{
int front = myQueuePeek(obj);//存储队列首个数据
STPop(&obj->popst);//pop掉队列的头数据
return front;//返回首个数据,达成用两个栈实现先进先出的队列
}
6.3.5 Empty(判空)函数
bool myQueueEmpty(MyQueue* obj) {
return QueueEmpty(&obj->pushst) && QueueEmpty(&obj->popst);
}
6.3.6 Free(释放空间)函数
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
free(obj);
}
6.3.7 全部代码
注:想要写题解或者测试,请自行添加上文关于Stack.h与Stack.c的代码段(下面代码能够复用的前提)
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst, x);
}
int myQueuePeek(MyQueue* obj) {
//哪个队列不为空就去取该队列的尾部数据
if (STEmpty(&obj->popst))
{
//判断popst为空,开始导入数据
while (!STEmpty(&obj->pushst))
{
STPush(&obj->popst, STTop(&obj->pushst));//导入数据后再进行删除头队列数据
STPop(&obj->pushst);//导进一个删除一个,清空pushst
}
}
return STTop(&obj->popst);
}
int myQueuePop(MyQueue* obj)
{
int front = myQueuePeek(obj);//存储队列首个数据
STPop(&obj->popst);//pop掉队列的头数据
return front;//返回首个数据,达成用两个栈实现先进先出的队列
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
free(obj);
}
6.4 设计循环队列
链接:力扣——设计循环队列
typedef struct {
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
}
int myCircularQueueFront(MyCircularQueue* obj) {
}
int myCircularQueueRear(MyCircularQueue* obj) {
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
}
void myCircularQueueFree(MyCircularQueue* obj) {
}
图像示例:
循环原则:删除完数据front–,增加完数据rear++.
循环关键就是front到rear,虽然经过增删会改变它们的位置,但在定长数组中起点就是front,终点就是rear。但需要注意[front,rear)这是左闭右开的关系。因为rear插入数据后会指向下一位。
这里用数组实现比较轻松,用链表反而会很复杂。
- 第一缺陷:用rear取队尾数据不好取,因为rear是每次插入数据后才往后移,如果想取队尾部那就得用到rear->pre了,这就变成了双向链表了。又或者再多给一个指针,变成3个指针。
- 第二缺陷:不好判满,链表为空rear与front指向同一处,而只有一个数据时,还是指向同一处。
- 第三缺陷:当链表满时rear又指向了与front一致的地方,与链表为空的情况一致,空与满判断不了。
所以为了解决这个问题,很多人选择多开一处空间,该空间不存储数据就为了让rear指到最后。
所以用链表始终存在一些问题,故而我们选择比链表适合一些的数组来实现。
6.4.1 整体思路:
这里判定满的条件就是rear+1,当rear的下标是4时可以想象+1就回到front的指向位置。所以最终的规律就是(rear+1)%(k+1)==front.
我们先来模拟一下增删:
当准备插入7时,只要我们的判满条件达成理论上是不会继续插入滴~我们继续删除数据~
当我们把6给删除后链表为空链表了,不能再继续删除了,而这时候我们发现front与rear相等,也满足了判空条件。
总结:实现循环链表的两个关键点
- 判空:front==rear
- 判满:(rear+1)%(k+1)==front
6.4.2 创造函数(Creat)
typedef struct {
int* a;//定义数组
int front;//起点
int rear;//终点
int k;//有效数字
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开一个空间方便区分空和满
obj->a = (int*)malloc(sizeof(int) * (k + 1));
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
6.4.2 判空与判满函数(Is(Empty)/(Full))
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1)%(obj->k+1) == obj->front;
}
6.4.3 EnQueue(插入)函数
在三种插入情况中我们需要注意第三种:rear循环绕到开头。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))//如果已经满了
{
return false;
}
//没满情况下
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k + 1);
//针对第三种情况当rear在下标4插入7时rear++变成5需要循环到头部
return true;
}
6.4.4 DeQueue(删除)函数
删除完数据front++,那front也会遇到跟上面rear一样的问题,当指向尾时再++需要循环绕到头部。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果已经是空的
{
return false;
}
obj->front++;
obj->front %= (obj->k + 1);
return true;
}
6.4.5 Front(取头)函数
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果已经是空的
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
6.4.6 rear(取尾)函数
取队尾函数就不像上面取队头那么好取了。正常的队尾取到rear-1就行,但如果是这种情况呢?取到-1该怎么办。
虽然可以通过if条件来判断并修改,但这里我们来引用一种巧妙的方法;
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果已经是空的
{
return -1;
}
else
{
return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}
}
6.4.7 Free(释放空间)函数
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
6.4.8 全部代码
typedef struct {
int* a;//定义数组
int front;//起点
int rear;//终点
int k;//有效数字
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开一个空间方便区分空和满
obj->a = (int*)malloc(sizeof(int) * (k + 1));
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1)%(obj->k+1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))//如果已经满了
{
return false;
}
//没满情况下
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k + 1);
//针对第三种情况当rear在下标4插入7时rear++变成5需要循环到头部
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果已经是空的
{
return false;
}
obj->front++;
obj->front %= (obj->k + 1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果已经是空的
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果已经是空的
{
return -1;
}
else
{
return obj->a[(obj->rear+ obj->k)%(obj->k+1)];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
七.结语
其实队列和栈的实现我们看作单链表的部分实现,因为我们只需要完成二者特定的结构性质就行了。所以只要单链表学扎实,想实现还是很轻松滴~另外提一嘴,4道oj题非常重要!里面可以帮助我们更加深入理解栈和队列。最后感谢大家的观看,友友们能够学习到新的知识是额滴荣幸,期待我们下次相见~
版权声明:本文为博主作者:玛丽亚后原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/fax_player/article/details/133249808