【Leedcode】栈和队列必备的面试题（第三期）

【Leedcode】栈和队列必备的面试题（第三期）

---

---

一、题目（用两个栈实现队列）

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】中栈和队列必备的面试题（第三期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！