Leetcode 【225】 用队列实现栈 C语言

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种 *** 作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本 *** 作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些 *** 作。

你所使用的语言也许不支持队列。

 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列 *** 作即可。

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

用队列实现栈我们只要用队列先进先出的原则来模拟栈的先进后出，用到两个栈相互倒元素就可以了。

因为是C语言所以接口都是现写的很费时间

typedef int Datatype;

typedef struct QueueNode{
    struct QueueNode* next;
    Datatype data;
} QueueNode;

typedef struct Queue{
    struct QueueNode * front;
    struct QueueNode * back;
} Queue;

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

//创建一个队列节点
QueueNode* CreateQueue(Datatype data){
    QueueNode* NewQueueNode = (QueueNode* )malloc(sizeof(QueueNode));
    if(NULL == NewQueueNode){
        assert(0);
        return NULL;
    }
    NewQueueNode->next = NULL;
    NewQueueNode->data = data;
    return NewQueueNode;
}

//队列的初始化
void QueueInit(Queue* p){
    assert(p);
    p->front = CreateQueue(0);
    p->back = p->front;

}
//尾插一个新节点
void QueuePush(Queue* p,Datatype data){
    assert(p);
    QueueNode* NewNode = CreateQueue(data);
    p->back->next = NewNode;
    p->back = NewNode;
}

//头删一个节点
void QueuePop(Queue* p){
    assert(p);
    if(QueueEmpty(p)){
        return;
    }
    QueueNode* DelNode = NULL;
    DelNode = p->front->next;
    p->front->next = DelNode->next;
    if(DelNode == p->back){
        p->back = p->front;
    }
    free(DelNode);
}

//队列是否为空
int QueueEmpty(Queue* p){
    assert(p);
    return p->front == p->back;
}

//获取队头元素
Datatype QueueFront(Queue* p){
    assert(p);
    return p->front->next->data;
}

//获取队尾元素
Datatype QueueBack(Queue* p){
    assert(p);
    return p->back->data;
}

//销毁队列
void QueueDestory(Queue* p){
    assert(p);
    QueueNode* cur = p->front->next;
    while(cur){
        p->front->next = cur->next;
        free(cur);
        cur = p->front->next;
    }

    free(p->front);
    p->back = NULL;
    p->front = NULL;
}

//获取队列长度
int QueueSize(Queue* p){
    assert(p);
    int count = 0;
    QueueNode* cur = p->front->next;
    while(cur){
        count++;
        cur = cur->next;
    }
    return count;
}

MyStack* myStackCreate() {
    MyStack* Stack = (MyStack* )malloc(sizeof(MyStack));
    if(NULL == Stack)
    {
        return NULL;
    }
    QueueInit(&Stack->q1);
    QueueInit(&Stack->q2);
    return Stack;
}

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);
    int ret = 0;
    if(!QueueEmpty(&obj->q1)){
        while(QueueSize(&obj->q1) > 1){
            QueuePush(&obj->q2,QueueFront(&obj->q1));
            QueuePop(&obj->q1);
        }

        ret = QueueFront(&obj->q1);
        QueuePop(&obj->q1);
    }
    else{
        while(QueueSize(&obj->q2) > 1){
            QueuePush(&obj->q1,QueueFront(&obj->q2));
            QueuePop(&obj->q2);
        }

        ret = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
    }
    return ret;
}

int myStackTop(MyStack* obj) {
    assert(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) {
    assert(obj);
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

终于考完试了 来刷上一道简单题找找感觉!