郏县住房和城乡建设局网站,引流推广推广微信hyhyk1效果好,火车采集器 wordpress,有没有专门做商铺招商的网站【Leedcode】栈和队列必备的面试题#xff08;第二期#xff09; 文章目录【Leedcode】栈和队列必备的面试题#xff08;第二期#xff09;一、题目#xff08;用两个队列实现栈#xff09;二、思路图解1.定义两个队列2.初始化两个队列3.往两个队列中放入数据4.两个队列出…【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】栈和队列必备的面试题第二期 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
