225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)
先看题目要求，用两个队列实现栈，我们先把之前写过的队列相关的一些函数拿来：
typedef int QDataType;
typedef struct QNode
{
QDataType data;
struct queue* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* q)
{
assert(q);
return q->head == NULL;
}
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
这里用两个队列实现，所以我们创建一个结构体：
typedef struct MYStack
{
Queue q1;
Queue q2;
}MyStack;
结构体里面两个指针，每一个指针对应一个队列，然后我们正式开始写这道题
--------
先从初始化函数开始：MyStack* myStackCreate() {
}
单看函数，它需要返回一致MyStack* 的指针，既然要返回指针，那我们就得用malloc开辟空间，然后开辟好的MyStack结构体其中的Queue结构体，我们可以直接调用其初始化函数，然后即可。
MyStack* myStackCreate() {
//开辟空间
MYStack* obj = (MYStack*)malloc(sizeof(MyStack));
//最好判断一下开辟成功没
assert(obj);
//初始化obj结构体里面的Queue结构体
QueueInit(&obj->q1);
QueueInit(&obj->q2);
//返回初始化好的结构体
return obj;
}
将元素X压入栈顶：
先说说思路：
我们现在有两个队列，两个队列分别有头尾指针，假设现在要将 1 2压入栈，那我们找其中一个不是空的队列压进去：
这样方便我们之后的一系列操作：
void myStackPush(MyStack* obj, int x) {
assert(obj);
//判断obj->q1是否为空，不为空压q1
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
//其他情况压q2
else
{
QueuePush(&obj->q2,x);
}
}
移除并返回栈顶元素：
还是先看思路，我们要移除并且返回栈顶的元素，因为栈是先后后出，所以我们刚刚压进来的 1 2出的时候就应该是 2 1。
按照之前玩单链表的思路，我们就应该是先找到最后一个节点，保存里面的值，然后释放掉最后节点，但是这题要用到第二个队列，所以这样做就有点跑题，这里我们换一种办法。
已知 q1 里面有 1 2，我们要返回 2
我们拿q2来接收q1里面的值，直到q1 里面只剩一个值位置，然后我们保存这个值再将其释放掉，下一次压栈压的就是q2的位置，如果还要移除的话就把q2的值移到q1里面。
将q1的1拿过来：
然后返回q1里面的值，再将其置为空：
假设现在要尾插 3 4 5：
然后再出来就把1 3 4 移到q1里面：
重复即可，然后我们就来实现代码：
int myStackPop(MyStack* obj) {
assert(obj);
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
noempty = &obj->q1;
empty = &obj->q2;
}
while(QueueSize(noempty) > 1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int data = QueueFront(noempty);
QueuePop(noempty);
return data;
}
一行一行看：
先判断obj不为空指针，然后假设空的那个队列是q1，非空的是q2，然后判断，如果q1是非空的，那就让非空的指向q1，空的指向q2
如果非空链表里面留下的节点数量大于1，说明我们还要移动
我们在空链表的后面尾插，尾插的是非空链表的元素
比方说刚刚的 1 2
那我们就把1移过去
每次移完记得删掉原本节点，不然程序会死循环
当循环结束，就意味着非空队列里面只有一个元素了，我们获取到这个元素之后再将这个节点也删掉，返回我们获得的元素。
返回栈顶元素：返回栈顶元素，也就是返回我们最后压进去的元素，正因为我们每次压栈都是在非空队列尾插，所以我们可以直接返回非空节点的最后一个元素即可：
int myStackTop(MyStack* obj) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
return QueueBack(&obj->q2);
}
判断栈是否为空：
我们只需要判断两个队列即可，调用一下我们之前写的判断队列的函数：
ibool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1)&& QueueEmpty(&obj->q2);
}
销毁栈：
这个更是简单，我们还是直接调用销毁队列的两个函数，最后释放掉我们的obj即可
void myStackFree(MyStack* obj) {
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
这里放上全部代码，有需要可以复制：
typedef int QDataType;
typedef struct QNode
{
QDataType data;
struct queue* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
typedef struct MYStack
{
Queue q1;
Queue q2;
}MyStack;
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* q)
{
assert(q);
return q->head == NULL;
}
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
assert(obj);
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
assert(obj);
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
noempty = &obj->q1;
empty = &obj->q2;
}
while(QueueSize(noempty) > 1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int data = QueueFront(noempty);
QueuePop(noempty);
return data;
}
int myStackTop(MyStack* obj) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
return QueueBack(&obj->q2);
}
bool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1)&& QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
