网站制作公司浩森宇特,官方在家做兼职的网站,友情链接检测结果,丹东做网站的公司【Leedcode】栈和队列必备的面试题#xff08;第三期#xff09; 文章目录【Leedcode】栈和队列必备的面试题#xff08;第三期#xff09;一、题目#xff08;用两个栈实现队列#xff09;二、思路图解1.定义两个栈2.初始化两个数组栈3. 将数据放入pushST数组栈中4.删除…【Leedcode】栈和队列必备的面试题第三期 文章目录【Leedcode】栈和队列必备的面试题第三期一、题目用两个栈实现队列二、思路图解1.定义两个栈2.初始化两个数组栈3. 将数据放入pushST数组栈中4.删除队列数据4.返回队列顶的数据5.判断队列是否为空6.释放销毁队列三、整体源代码总结一、题目用两个栈实现队列
Leedcode链接 这几个接口使我们需要实现的我会一 一实现并讲解
二、思路图解
注意这里会用到很多栈和队列接口实现的一些知识这里不再深究如果想了解可以去下面两个博客 栈的接口模拟实现 队列的接口模拟实现 做本题需要的接口和结构体声明 代码如下示例 typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}Stack;void StackInit(Stack* ps);//初始化栈
void StackDestroy(Stack* ps);//销毁栈
void StackPush(Stack* ps, STDataType x);//存放栈
void StackPop(Stack* ps);//删除栈
STDataType StackTop(Stack* ps);//获取栈顶信息
int StackSize(Stack* ps);//获取栈内数据个数
bool StackEmpty(Stack* ps);//判断栈是否为空 如果是空返回truevoid StackInit(Stack* ps)//初始化栈
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void StackDestroy(Stack* ps)//销毁栈
{assert(ps);free(ps-a);ps-top 0;ps-capacity 0;
}void StackPush(Stack* ps, STDataType x)//存放栈数据
{assert(ps);if (ps-top ps-capacity){//增容//capacity 如果是0 那么就定义为4 如果不是0 则capacity乘以 2 三目操作符 ? :int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){printf(realloc fail);exit(-1);}//拿到新开辟的空间地址 - 更新增容后的最大空间数量 ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void StackPop(Stack* ps)//删除栈
{assert(ps);assert(!StackEmpty(ps));ps-top--;
}STDataType StackTop(Stack* ps)//获取栈顶信息
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top-1];
}int StackSize(Stack* ps)//获取栈内数据个数
{assert(ps);return ps-top;
}bool StackEmpty(Stack* ps)//判断栈是否为空 如果是空返回true
{assert(ps);//if (ps-top 0)//{// return true;//}//else// return false;return ps-top 0;
}1.定义两个栈 代码如下示例 typedef struct {Stack pushST;Stack popST;
} MyQueue;2.初始化两个数组栈 代码如下示例 MyQueue* myQueueCreate() {MyQueue* q (MyQueue*)malloc(sizeof(MyQueue));StackInit(q-pushST);StackInit(q-popST);return q;
}3. 将数据放入pushST数组栈中 代码如下示例 void myQueuePush(MyQueue* obj, int x) {StackPush(obj-pushST, x);
}4.删除队列数据 代码如下示例 int myQueuePop(MyQueue* obj) {if(StackEmpty(obj-popST)){while(!StackEmpty(obj-pushST)){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}int front StackTop(obj-popST);StackPop(obj-popST);return front;
}4.返回队列顶的数据
这里接口实现和删除队列数据很详细这里不用删除直接返回即可 代码如下示例 int myQueuePeek(MyQueue* obj) {if(StackEmpty(obj-popST)){while(!StackEmpty(obj-pushST)){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}return StackTop(obj-popST);
}5.判断队列是否为空 代码如下示例 bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-popST) StackEmpty(obj-pushST);
}6.释放销毁队列 代码如下示例 void myQueueFree(MyQueue* obj) {StackDestroy(obj-popST);StackDestroy(obj-pushST);free(obj);
}三、整体源代码 代码如下示例 typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}Stack;void StackInit(Stack* ps);//初始化栈
void StackDestroy(Stack* ps);//销毁栈
void StackPush(Stack* ps, STDataType x);//存放栈
void StackPop(Stack* ps);//删除栈
STDataType StackTop(Stack* ps);//获取栈顶信息
int StackSize(Stack* ps);//获取栈内数据个数
bool StackEmpty(Stack* ps);//判断栈是否为空 如果是空返回truevoid StackInit(Stack* ps)//初始化栈
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void StackDestroy(Stack* ps)//销毁栈
{assert(ps);free(ps-a);ps-top 0;ps-capacity 0;
}void StackPush(Stack* ps, STDataType x)//存放栈数据
{assert(ps);if (ps-top ps-capacity){//增容//capacity 如果是0 那么就定义为4 如果不是0 则capacity乘以 2 三目操作符 ? :int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){printf(realloc fail);exit(-1);}//拿到新开辟的空间地址 - 更新增容后的最大空间数量 ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void StackPop(Stack* ps)//删除栈
{assert(ps);assert(!StackEmpty(ps));ps-top--;
}STDataType StackTop(Stack* ps)//获取栈顶信息
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top-1];
}int StackSize(Stack* ps)//获取栈内数据个数
{assert(ps);return ps-top;
}bool StackEmpty(Stack* ps)//判断栈是否为空 如果是空返回true
{assert(ps);//if (ps-top 0)//{// return true;//}//else// return false;return ps-top 0;
}typedef struct {Stack pushST;Stack popST;
} MyQueue;MyQueue* myQueueCreate() {//动态开辟一个空间MyQueue* q (MyQueue*)malloc(sizeof(MyQueue));//初始化两个数组栈StackInit(q-pushST);StackInit(q-popST);return q;
}void myQueuePush(MyQueue* obj, int x) {//将数据放入pushST数组栈中StackPush(obj-pushST, x);
}int myQueuePop(MyQueue* obj) {//如果popST数组栈是空的 就从pushST数组栈中尝试取数据//然后popST数组栈顶部就是第一个元素。删除第一个元素就符合队列先进先出的逻辑了if(StackEmpty(obj-popST)){//循环条件 只要pushST不为空就进入循环while(!StackEmpty(obj-pushST)){//将pushST数组栈中的数据放入popst数组栈中StackPush(obj-popST, StackTop(obj-pushST));//数据已经拷贝到popst数组栈中 pushST数组栈中的整个数据就可以删除了StackPop(obj-pushST);}}//将准备删除的数据放入局部变量front这个元素是队列的头元素int front StackTop(obj-popST);//删除头元素队列删出头元素的行为StackPop(obj-popST);//函数要求返回整个被删除的头元素return front;
}int myQueuePeek(MyQueue* obj) {//如果popST数组栈是空的 就从pushST数组栈中尝试取数据//然后popST数组栈顶部就是第一个元素。删除第一个元素就符合队列先进先出的逻辑了if(StackEmpty(obj-popST)){while(!StackEmpty(obj-pushST)){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}//函数要求返回数据 返回popST数组栈的栈顶元素的数据return StackTop(obj-popST);
}bool myQueueEmpty(MyQueue* obj) {//当popST 与 pushST 都是空时 return返回真true 否则为假 falsereturn StackEmpty(obj-popST) StackEmpty(obj-pushST);
}void myQueueFree(MyQueue* obj) {//将popST 与 pushST 的空间先销毁 后 释放 obj指针指向的空间StackDestroy(obj-popST);StackDestroy(obj-pushST);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj myQueueCreate();* myQueuePush(obj, x);* int param_2 myQueuePop(obj);* int param_3 myQueuePeek(obj);* bool param_4 myQueueEmpty(obj);* myQueueFree(obj);
*/ 总结
以上就是今天要讲的内容本文介绍了【Leedcode】中栈和队列必备的面试题第三期 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
