栈和队列的相互实现

1. 两个队列实现栈. - 力扣（LeetCode）

队列的特点是先进先出，而栈的特点是后进先出（先进后出），也就是说重点在于利用两个队列来改变“出”的顺序。

假设我们在进行入栈操作的时候将数据依次入到一个队列中。

在此基础上，获取栈顶元素比较简单，只需要利用获取队尾元素的接口即可。

但是在出栈时，被删除的栈顶元素为队尾元素，而队列没有相应的删除队尾元素的接口。

于是，我们就可以利用起另一个队列，将队尾元素之前的元素全部出队并入队到另一个队列。

这时，我们就可以对队尾元素进行出队操作了，但是不将其入队到另一个队列中。

这样我们就实现了出栈的操作。

其他的接口都很好实现，我们直接给出代码，其中队列的接口函数详见这篇博客：链队列和循环队列-CSDN博客

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);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if(!QueueEmpty(empty))
    {
        nonempty = &obj->q1;
        empty = &obj->q2;
    }

    while(QueueSize(nonempty) > 1)
    {
        QueuePush(empty, QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int ret = QueueFront(nonempty);
    QueuePop(nonempty);
    return ret;
}

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);
}

 2. 两个栈实现队列. - 力扣（LeetCode）

对队列进行操作需要对两端进行操作，而对栈进行操作只能操作一端。

注意到，将一个栈的数据依次转移到另一个队列时，栈的顶为发生了颠倒。

于是，我们用一个栈来对队头进行操作，另一个栈来对队尾进行操作。

据此思路，我们可以完成以下代码，其中栈的接口函数详见这篇博客：栈与递归的实现-CSDN博客 

enum States
{
    PUSH,
    POP
};

typedef struct {
    enum States state;
    Stack sti;//入
    Stack sto;//出
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    obj->state = PUSH;
    STInit(&obj->sti);
    STInit(&obj->sto);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    if(obj->state != PUSH)
    {
        while(!STEmpty(&obj->sto))
        {
            STPush(&obj->sti, STTop(&obj->sto));
            STPop(&obj->sto);
        }
        obj->state = PUSH;
    }

    STPush(&obj->sti, x);
}

int myQueuePop(MyQueue* obj) {
    if(obj->state != POP)
    {
        while(!STEmpty(&obj->sti))
        {
            STPush(&obj->sto, STTop(&obj->sti));
            STPop(&obj->sti);
        }
        obj->state = POP;
    }

    int ret = STTop(&obj->sto);
    STPop(&obj->sto);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(obj->state != POP)
    {
        while(!STEmpty(&obj->sti))
        {
            STPush(&obj->sto, STTop(&obj->sti));
            STPop(&obj->sti);
        }
        obj->state = POP;
    }

    int ret = STTop(&obj->sto);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return (STEmpty(&obj->sti) && STEmpty(&obj->sto));
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->sti);
    STDestroy(&obj->sto);
    free(obj);
}