实战oj题——用队列实现栈

前言：Leetcode栈和队列的习题，用两个队列实现栈。

在这里插入图片描述

【由于我们是用C语言完成这道题，所以我们要将关于队列的实现代码插入到题中，在创建一个栈，栈里包含两个队列。】

思路：我们用两个队列来实现，因为我们的栈是后入先出，而我们的队列是先入先出，所以我们在入栈的时候先将元素插入到一个非空的队列，我们要删除栈顶元素就将该队列的除了最后一个入队列的元素外，全部入到另外一个队列之中，在删除队列的队首元素并返回。核心思路是两个队列得配合使用。

入栈：

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
       QueuePush(&obj->q1,x);
    }
    QueuePush(&obj->q2,x);
}

移除并返回栈顶：

int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;
    Queue* nonempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int top=QueueFront(nonempty);
    QueuePop(nonempty);
    return top;
    
}

返回栈顶元素：

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else{
        return QueueBack(&obj->q2);
    }
    
}

这里我们的一个队列为空，另外一个队列不为空，我们就取另外一个队列的队尾，队尾元素就是我们的栈最后入的元素，也就是栈顶。

判断栈是否为空：

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    
}

如果两个队列都为空则返回真，有一个不为空则返回假。

销毁栈：

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
    
}

完整代码展示：

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);

    return pst;

    
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
       QueuePush(&obj->q1,x);
    }
    QueuePush(&obj->q2,x);
}

int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;
    Queue* nonempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int top=QueueFront(nonempty);
    QueuePop(nonempty);
    return top;
    
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else{
        return QueueBack(&obj->q2);
    }
    
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
    
}