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

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

---

---

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

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