当前位置: 首页 > news >正文

手撕数据结构算法OJ——栈和队列

文章目录

  • 一、前言
  • 二、手撕OJ
    • 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.3用栈实现队列
      • 2.3.1初始化
      • 2.3.2入队
      • 2.3.3出队
      • 2.3.4取队头
      • 2.3.5判空
      • 2.3.6销毁
      • 2.3.7整体代码
  • 四、总结

一、前言

兄弟们,今天的你们还在学习吗?快快跟随up的脚步,让up和大家一起长脑子吧!俗话说得好:一日学一日功,一日不学十日空。好啦言归正传,前面up已经给大家讲解完了栈和队列这两个数据结构,不知道你有没有把它们吃透呢?今天呢咱们就来手撕与之相关的算法OJ题。

二、手撕OJ

2.1有效的括号

力扣20题 有效的括号链接
在这里插入图片描述
条件限制:
1、只能有这三种括号( ) 、[ ]、{ }
2、左括号必须用相同类型的右括号闭合
3、左括号必须以正确的顺序闭合
4、每个右括号都有一个对应的相同类型的左括号
画图展示(用栈解决):
注意阅图顺序:先从左往右,在从上往下。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
注意:因为此题是用栈来实现,关于栈的各功能up在上一次已经给大家书写过一次了,所以这里我们就直接复制粘贴。(如有疑问请查看上一节分享)
代码展示:

typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
void StackInit(ST* ps)//栈初始化
{assert(ps);ps->arr = NULL;ps->top = 0;ps->capacity;
}
void StackPush(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->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){printf("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}
bool Stackempty(ST* ps)//判空
{assert(ps);return ps->top == 0;
}
void StackPop(ST* ps)//出栈
{assert(!Stackempty(ps));--ps->top;
}
STDataType StackFront(ST* ps)//取栈顶
{assert(!Stackempty(ps));return ps->arr[ps->top - 1];
}
int StackSIze(ST* ps)//有效个数
{assert(ps);return ps->top;
}
void StackDestroy(ST* ps)//销毁
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}
//.......................以上为栈的各功能实现代码
bool isValid(char* s) {ST st;StackInit(&st);char* pi = s;while(*pi!='\0'){if(*pi == '(' || * pi == '[' || *pi =='{'){StackPush(&st,*pi);}else{if(Stackempty(&st)){StackDestroy(&st);return false;}char top = StackFront(&st);if((top == '(' && *pi != ')')||(top == '[' && *pi != ']')||(top == '{' && *pi != '}')){StackDestroy(&st);return false;}StackPop(&st);}pi++;}bool ret = Stackempty(&st) ? true : false;StackDestroy(&st);return ret;
}

思路:定义一个pi从第一个括号开始,若pi为左括号则直接进栈,如果没有左括号只有右括号则注定无法匹配,return false;待遇到右括号就与栈顶的左括号进行匹配,如果没有右括号或者匹配不成功直接返回false,若匹配成功就出栈,继续用下一个右括号与栈顶进行匹配,当pi走到空并且栈中也没有元素的时候,说明全部括号匹配成功,return true.

提交通过
在这里插入图片描述

2.2用队列实现栈

力扣225 用队列实现栈链接
在这里插入图片描述

2.2.1初始化

代码展示:

MyStack* myStackCreate() {//初始化MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}

2.2.2入栈

画图展示:
在这里插入图片描述
思路:找到不为空的队列,把要进行入栈操作的元素直接入队即可。

代码展示:

void myStackPush(MyStack* obj, int x) {//入栈if(!Queueempty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

2.2.3出栈

画图展示:
在这里插入图片描述
思路:找到不为空的队列,把队列的前size-1个元素入队到另外一个空队列中,待原先不为空的队列只剩一个元素的时候,把最后一个元素保存直接出栈掉即可,再反复进行以上操作,直到一 一出栈。

代码展示:

int myStackPop(MyStack* obj) {//出栈Queue* emp = &obj->q1;Queue* noneEmp = &obj->q2;if(Queueempty(&obj->q2)){emp = &obj->q2;noneEmp = &obj->q1;}while(QueueSize(noneEmp)>1){QueuePush(emp,QueueFront(noneEmp));QueuePop(noneEmp);}int top = QueueFront(noneEmp);QueuePop(noneEmp);return top;
}

2.2.4取栈顶

画图展示:
在这里插入图片描述
思路:直接返回不为空的队列中的队尾元素即为所需要的栈顶元素。
代码展示:

int myStackTop(MyStack* obj) {//取栈顶if(!Queueempty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

2.2.5判空

思路:当队列1和队列2同时都不为空则栈不为空,反之有一个为空则栈为空。

代码展示:

bool myStackEmpty(MyStack* obj) {//判空return Queueempty(&obj->q1) && Queueempty(&obj->q2);
}

2.2.6销毁

思路:把队列1和队列2销毁掉,再把存放这两个队列的空间释放掉,最后再置为空即可。

代码展示:

void myStackFree(MyStack* obj) {//销毁QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}

2.2.7整体代码

注意:队列的实现是直接复制粘贴上一节的代码。

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;
}Queue;
void QueueInit(Queue* pq)//初始化
{assert(pq);pq->phead = NULL;pq->ptail = NULL;
}
void QueuePush(Queue* pq,QDataType x)//入队
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){printf("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}
}
bool Queueempty(Queue* pq)//判空
{assert(pq);return pq->phead == NULL;
}
void QueuePop(Queue* pq)//出队
{assert(!Queueempty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}
QDataType QueueFront(Queue* pq)//取队头
{assert(!Queueempty(pq));return pq->phead->data;
}
QDataType QueueBack(Queue* pq)//取队尾
{assert(!Queueempty(pq));return pq->ptail->data;
}
int QueueSize(Queue* pq)//有效个数
{assert(pq);QueueNode* pcur = pq->phead;int size = 0;while (pcur){size++;pcur = pcur->next;}return size;
}
void QueueDestroy(Queue* pq)//销毁
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = NULL;pq->ptail = NULL;
}typedef struct {Queue q1;Queue 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)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emp = &obj->q1;Queue* noneEmp = &obj->q2;if(Queueempty(&obj->q2)){emp = &obj->q2;noneEmp = &obj->q1;}while(QueueSize(noneEmp)>1){QueuePush(emp,QueueFront(noneEmp));QueuePop(noneEmp);}int top = QueueFront(noneEmp);QueuePop(noneEmp);return top;
}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);obj = NULL;
}

提交通过
在这里插入图片描述

2.3用栈实现队列

力扣232 用栈实现队列链接
在这里插入图片描述

2.3.1初始化

代码展示:

MyQueue* myQueueCreate() {//初始化MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->pushST);StackInit(&pq->popST);return pq;
}

2.3.2入队

画图展示:
在这里插入图片描述
思路:直接把要入队的元素入栈即可。

代码展示:

void myQueuePush(MyQueue* obj, int x) {//入队StackPush(&obj->pushST,x);
}

2.3.3出队

画图展示:
在这里插入图片描述
思路:把原来不为空的栈中的元素依次入栈到另外一个空栈中,此时原先的空栈的栈顶元素就是要出队的元素,直接把队头出队即可

代码展示:

int myQueuePop(MyQueue* obj) {//出队if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}int top = StackFront(&obj->popST);StackPop(&obj->popST);return top;
}

2.3.4取队头

画图展示:
在这里插入图片描述
思路:把原来不为空的栈中的元素依次入栈到另外一个空栈中,此时原先的空栈的栈顶元素就是队头。

代码展示:

int myQueuePeek(MyQueue* obj) {//取队头if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}return StackFront(&obj->popST);
}

2.3.5判空

思路:两个栈同时不为空即队列不为空,反之有一个栈为空则队列为空。

代码展示:

bool myQueueEmpty(MyQueue* obj) {//判空return Stackempty(&obj->pushST) && Stackempty(&obj->popST);
}

2.3.6销毁

思路:把两个栈销毁掉,再把存放这两个栈的空间释放掉,最后再置为空即可。

代码展示:

void myQueueFree(MyQueue* obj) {//销毁StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);obj = NULL;
}

2.3.7整体代码

注意:栈的各功能实现是直接复制粘贴上一节的代码。

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
void StackInit(ST* ps)//栈初始化
{assert(ps);ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}
void StackPush(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->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){printf("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}
bool Stackempty(ST* ps)//判空
{assert(ps);return ps->top == 0;
}
void StackPop(ST* ps)//出栈
{assert(!Stackempty(ps));--ps->top;
}
STDataType StackFront(ST* ps)//取栈顶
{assert(!Stackempty(ps));return ps->arr[ps->top - 1];
}
int StackSIze(ST* ps)//有效个数
{assert(ps);return ps->top;
}
void StackDestroy(ST* ps)//销毁
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}typedef struct {ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->pushST);StackInit(&pq->popST);return pq;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST,x);
}int myQueuePop(MyQueue* obj) {if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}int top = StackFront(&obj->popST);StackPop(&obj->popST);return top;
}int myQueuePeek(MyQueue* obj) {if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}return StackFront(&obj->popST);
}bool myQueueEmpty(MyQueue* obj) {return Stackempty(&obj->pushST) && Stackempty(&obj->popST);
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);obj = NULL;
}

提交通过:
在这里插入图片描述

四、总结

宝子们,怎么样?是否被这三道OJ题震撼到了呢?相信你在看完up的分析之后,可能会感慨——原来栈和队列还能这么用,真NB。不过震撼归震撼,下来还是得深入理解。up期待大家更上一层楼。

这世界上,最富有的人是跌倒最多的人;最勇敢的人是每次跌倒都能站起来的人;最成功的人是那些每次跌倒,不单能站起来,还能够坚持走下去的人
在这里插入图片描述

http://www.xdnf.cn/news/8677.html

相关文章:

  • eNSP无法启动AR报错码40,而且按照eNSP帮助手册排查都没用,我的处理方法【自己存档版】
  • 2N60-ASEMI功业控制与自动化专用2N60
  • python中,处理多分类时,模型之间的参数设置
  • sort和swap函数
  • 数据结构之稀疏矩阵与三元组表示法
  • 23种设计模式全面解析
  • 告别Feign:基于Spring 6.1 RestClient构建高可靠声明式HTTP客户端
  • 今日多肽之——订书肽
  • Linux文件类型
  • 建筑科技的未来图景:探究中建海龙的创新基因
  • C语言超详细结构体知识
  • 工程化实践:Flutter项目结构与规范
  • 广东中级消防设施操作员理论考试精选题
  • SpringAI+DeepSeek大模型应用开发——5 ChatPDF
  • 相比其他缓存/内存数据库(如 Memcached, Ehcache 等),Redis 在微服务环境中的优势和劣势是什么?
  • 【RK3588 嵌入式图形编程】-SDL2-扫雷游戏-结束和重新开始游戏
  • string函数的应用
  • Python 写生成 应用商店(2025版) 网页 方便收集应用 ,局域网使用
  • 极狐GitLab 外部授权控制机制是怎样的?
  • 【前端知识】今天聊一聊web的事件机制
  • SpringBoot学习(properties、yml(主流)、yaml格式配置文件)(读取yml配置文件的3种方式)(详解)
  • Kafka消费者端重平衡流程
  • 中间件--ClickHouse-9--MPP架构(分布式计算架构)
  • kafka菜鸟教程
  • GEE学习笔记 29:基于GEE的多源Landsat合成与植被指数时序提取
  • axios 模拟实现
  • 【HFP】蓝牙HFP协议音频连接核心技术深度解析
  • 【2】CICD持续集成-k8s集群中安装Jenkins
  • 8.观察者模式:思考与解读
  • 【SAP ME 44】在 HANA DB中报废SFC时的SHOP_ORDER表记录锁定