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

【Leedcode】栈和队列必备的面试题(第二期)

【Leedcode】栈和队列必备的面试题(第二期)


文章目录

  • 【Leedcode】栈和队列必备的面试题(第二期)
  • 一、题目(用两个队列实现栈)
  • 二、思路+图解
    • 1.定义两个队列
    • 2.初始化两个队列
    • 3.往两个队列中放入数据
    • 4.两个队列出数据
    • 5.显示栈顶信息
    • 6.判断栈或者队列是否为空
    • 7.销毁栈或者队列
  • 三、总代码展示
  • 总结


一、题目(用两个队列实现栈)

Leedcode链接


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述
这几个接口使我们需要实现的我会一 一实现并讲解!


二、思路+图解

注意:这里会用到很多栈和队列接口实现的一些知识,这里不再深究,如果想了解可以去下面两个博客!
栈的接口模拟实现 + 队列的接口模拟实现


做本题需要的接口和结构体声明!

代码如下(示例):

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}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);//取尾数据
size_t QueueSize(Queue* pq);//计算数据个数
bool QueueEmpty(Queue* pq);//判断队列是不是空void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)//销毁队列
{assert(pq);//创建一个cur指针 指向队列头 用于挨个释放空间QueueNode* cur = pq->head;//当cur不为NULL 一直循环执行  挨个释放列表成员空间while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}//当循环结束 将 head与tail 置为NULLpq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)//放入数据
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL; if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq)//删除数据
{assert(pq);assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);if (pq->head == pq->tail){pq->tail = NULL;}pq->head = next; 
}QDataType QueueFront(Queue* pq)//取头数据
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)//取尾数据
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
size_t QueueSize(Queue* pq)//计算数据个数
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;int n = 0;while (cur){cur = cur->next;n++;}return n;
}bool QueueEmpty(Queue* pq)//判断队列是不是空
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

1.定义两个队列

代码如下(示例):

typedef struct{Queue q1;Queue q2;
} MyStack;

2.初始化两个队列

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述

代码如下(示例):

MyStack* myStackCreate() {MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&st->q1);QueueInit(&st->q2);return st;
}

3.往两个队列中放入数据


在这里插入图片描述


在这里插入图片描述


代码如下(示例):

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

4.两个队列出数据

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


代码如下(示例):

int myStackPop(MyStack* obj) {Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){nonemptyQ = &obj->q1;emptyQ = &obj->q2;}while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ, QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int ret = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return ret;
}

5.显示栈顶信息

在这里插入图片描述

代码如下(示例):

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

6.判断栈或者队列是否为空

在这里插入图片描述

代码如下(示例):

bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

7.销毁栈或者队列

在这里插入图片描述


在这里插入图片描述

代码如下(示例):

void myStackFree(MyStack* obj) 
{QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

三、总代码展示

代码如下(示例):

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}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);//取尾数据
size_t QueueSize(Queue* pq);//计算数据个数
bool QueueEmpty(Queue* pq);//判断队列是不是空void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)//销毁队列
{assert(pq);//创建一个cur指针 指向队列头 用于挨个释放空间QueueNode* cur = pq->head;//当cur不为NULL 一直循环执行  挨个释放列表成员空间while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}//当循环结束 将 head与tail 置为NULLpq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)//放入数据
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL; if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq)//删除数据
{assert(pq);assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);if (pq->head == pq->tail){pq->tail = NULL;}pq->head = next; 
}QDataType QueueFront(Queue* pq)//取头数据
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)//取尾数据
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
size_t QueueSize(Queue* pq)//计算数据个数
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;int n = 0;while (cur){cur = cur->next;n++;}return n;
}bool QueueEmpty(Queue* pq)//判断队列是不是空
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}//定义两个队列
typedef struct{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {//函数内定义变量出了函数就没了,所以我们在这里选择用malloc开辟动态空间 并将这个空间的地址返回给函数MyStack* st = (MyStack*)malloc(sizeof(MyStack));//调用自己的队列初始化函数 将定义的2个队列初始化QueueInit(&st->q1);QueueInit(&st->q2);//函数要求 返回新开辟的地址(栈地址)return st;
}void myStackPush(MyStack* obj, int x) {//往栈中放入数据if(!QueueEmpty(&obj->q1))//当q1不是空的时 将数据放入q1队列中{//调用队列函数,自定义函数传过来的是栈的指针,所以要&obj的地址指向q1QueuePush(&obj->q1, x);}else//当q2不是空的时 将数据放入q1队列中  由于这里是else 所以假设q1 q2都是空也会将数据放入q2队列中{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//emptyQ表示空队列   nonEmptuQ 表示有元素队列//先假设定义队列 q1为空 q2 非空Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;//然后调用判断是否为空函数if(!QueueEmpty(&obj->q1))//如果队列q1 非空进入循环{//向q1道歉 将q1改为非空  将q2改为空nonemptyQ = &obj->q1;emptyQ = &obj->q2;}//此时 nonempyuQ 与 emptyQ 经历了修正 队列nonempyuQ 是非空 emptyQ是空 (特殊情况下两者都是空)while(QueueSize(nonemptyQ)>1)//循环条件 非空的nonemptyQ队列数据个数最少是大于1就可以进入循环,假设等于或小于1不进入循环{//将非空nonemptyQ队列元素数据放入,空emptyQ队列中QueuePush(emptyQ, QueueFront(nonemptyQ));//放进去一个就删除一个非空nonemptyQ队列元素QueuePop(nonemptyQ);}//当循环结束来到这里nonempty内只有一个元素,这个元素也表示的是栈顶的元素(特殊情况下nonempty也是空的)int ret = QueueFront(nonemptyQ);QueuePop(nonemptyQ);//最后删除这个元素(表达出栈行为)return ret;//函数要求返回这个被删除的元素数据
}
int myStackTop(MyStack* obj) {//显示栈顶信息if(!QueueEmpty(&obj->q1))//栈顶不为空进入{//返回q1队列尾部数据return QueueBack(&obj->q1);}else{//返回q2队列尾部数据return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {//当q1为空 并且 q2为空 则返回真 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {//先将q1 和 q2 空间销毁QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);//最后释放obj空间free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

总结

以上就是今天要讲的内容,本文为【Leedcode】栈和队列必备的面试题(第二期)
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!
在这里插入图片描述

http://www.lryc.cn/news/25042.html

相关文章:

  • Elasticsearch实战之(商品搜索API实现)
  • 剑指 Offer 14-剪绳子
  • 泰克示波器|MSO64示波器的应用
  • 1.4 黑群晖安装:SataPortMap和DiskIdxMap两种获取方式
  • JVM虚拟机概述(2)
  • Intel CSME 简述
  • 复位理论基础
  • Python基础知识——列表
  • 如何使用工时表管理项目和非项目的资源?
  • 项目经理如何做好质量保证与标准维持?非技术项目经理如何做好质量管控?
  • [文件操作] File 类的用法和 InputStream, OutputStream 的用法
  • 索莫菲模型的一些理解 Smomerfeld Model
  • SAP ERP系统MM模块常用增强之四:采购申请输入字段的校验检查
  • STM32C0介绍(1)----概述
  • windows无盘启动技术开发之传统BIOS(Legacy BIOS)引导程序开发之一
  • mysql实现if语句判断功能的六种使用形式
  • 在Vue3这样子写页面更快更高效
  • 做软件测试,如何才能实现月入20K?
  • mysql last lesson
  • 一、Redis入门概述(是什么,能干嘛,去哪下,怎么玩)
  • (六十二)当我们在SQL里进行分组的时候,如何才能使用索引?
  • python字符串练习
  • Java-封装、继承、多态
  • 问题三十二:离散二维傅立叶变换(Discrete Fourier Transformation)
  • 恢复谷歌翻译的究极方法
  • string函数以及string常用接口
  • 分享一篇由C语言实现《数据结构》无头无循环单链表
  • C盘爆满?两个超简单的解决办法
  • ThreadLocal
  • Java基础:JDK7-时间Date