力扣 225. 用队列实现栈(C语言实现)

1.解题思路
这道题如果使用C++会好写的多，因为可以使用C++提供的队列来实现，但如果使用C语言则必须手写一个队列来实现，在这里我用了我前面文章中实现好的队列来解答，首先因为队列是先进先出，而栈是后进后出，因此我们可以设计两个队列，其中一个队列放数据，另一个队列为空，当使用POP接口出栈时，则可将队列一的前N-1个数据挪到队列二上，这样一来，队列一剩余的那个数就为要出栈的数，即这道题的精髓就是两个队列之间数据的传递.

2.代码实现
队列实现代码:

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
    struct QListNode* _next;
    QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

void QueueInit(Queue* q)
{
    assert(q);
    q->_front = NULL;
    q->_rear = NULL;

}
void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    if (q->_front == NULL)
    {
        QNode* tmp = (QNode*)malloc(sizeof(QNode));
        tmp->_data = data;
        tmp->_next = NULL;
        q->_front = q->_rear = tmp;
    }
    else
    {
        QNode* tmp = (QNode*)malloc(sizeof(QNode));
        tmp->_data = data;
        tmp->_next = NULL;
        q->_rear->_next = tmp;
        q->_rear = tmp;
    }


}
void QueuePop(Queue* q)
{
    assert(q->_front != NULL);
    QNode* tmp = q->_front->_next;
    free(q->_front);
    q->_front = tmp;

}
QDataType QueueFront(Queue* q)
{
    assert(q->_front);
    return q->_front->_data;


}
QDataType QueueBack(Queue* q)
{
    assert(q->_rear);
    return q->_rear->_data;
}
int QueueSize(Queue* q)
{
    QNode* tmp = q->_front;
    int num = 0;
    while (tmp)
    {
        num++;
        tmp = tmp->_next;
    }
    return num;

}
bool QueueEmpty(Queue* q)
{
    return q->_front == NULL;

}
void QueueDestroy(Queue* q)
{
    QNode* tmp = q->_front;
    while (tmp)
    {
        QNode* next = tmp->_next;
        free(tmp);
        tmp = next;
    }

}

解题接口代码:

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


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

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

int myStackPop(MyStack* obj) {
    Queue* p1 = &obj->q1;
    Queue* p2 = &obj->q2;
    if (!QueueEmpty(&obj->q2))
    {
        p1 = &obj->q2;
        p2 = &obj->q1;
    }
    while (QueueSize(p1)>1)
    {
        QueuePush(p2, QueueFront(p1));
        QueuePop(p1);
    }
    int tmp = p1->_front->_data;
    QueuePop(p1);
    return tmp;
}

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

}

bool myStackEmpty(MyStack* obj) {
    if (!QueueEmpty(&obj->q1) || QueueEmpty(&obj->q2))
        return false;
    else
        return true;
}

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

结尾：今天的分享到此结束，喜欢的朋友如果感觉有帮助可以点赞三连支持，咱们共同进步!