思路
思路：用两个队列实现栈后进先出的特性 ，两个队列为空时，先将数据都导向其中一个队列。
当要模拟出栈时，将前面的元素都导入另一个空队列，再将最后一个元素移出队列
实现
实现： 因为C语言没有库可以现成使用，所以我们将写好的队列导入
先创建MyStack结构体，包含两个队列结构体。再malloc动态申请MyStack结构体的空间，最后将两个队列传入初始化函数，进行初始化（记得要加上&取地址符号）
压栈过程，我们就先判断队列q1是否为空，如果不为空，则往q1中导入数据（因为不为空，证明前面已经有数据放进去了）；如果为空，则证明要么两个队列都是空，要么一开始向q2导入了数据，这时我们就将数据导入队列q2中。
一句话总结：谁有数据就放谁，都无数据放q2（一开始随便放哪个都行，这里我们选择q2）
出栈过程，就分为两个部分。第一个部分，是创建空队列和非空队列指针（因为我们不知道此时q1和q2哪个是空，哪个非空），后面加上判断，如果初始赋值错误，则翻转过来。
第二个部分，就是一开始的核心思路，利用循环，将前面的元素都导入另一个空队列，再获取最后一个元素（注意，每次导入一个元素，就要进行出队操作pop）
获取栈顶元素，就是出栈过程的删减版，判断完空与非空队列，直接取出非空队列队尾的元素即可
判断栈是否为空，只要当两个队列q1和q2全为空时，栈才为空，返回true，否则返回false
最后，释放栈空间，可能有人只写了最后一句也给过了，但是其实这是不对的。正确做法是，先将两个队列都销毁（销毁链表），再将MyStack空间给释放掉，这样才不会造成内存泄漏
完整代码附上：
typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //入队 void QueuePush(Queue* pq, QDataType x); //出队 void QueuePop(Queue* pq); //获取队头元素 QDataType QueueFront(Queue* pq); //获取队尾元素 QDataType QueueBack(Queue* pq); //检测队列中有效元素个数 int QueueSize(Queue* pq); //检测队列是否为空 bool QueueEmpty(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); if (obj == NULL) { perror("malloc fail"); return NULL; } QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { Queue* pEmptyQ = &obj->q1; Queue* pNonEmptyQ = &obj->q2; if (!QueueEmpty(&obj->q1)) { pEmptyQ = &obj->q2; pNonEmptyQ = &obj->q1; } while (QueueSize(pNonEmptyQ) > 1) { QueuePush(pEmptyQ, QueueFront(pNonEmptyQ)); QueuePop(pNonEmptyQ); } int top = QueueFront(pNonEmptyQ); QueuePop(pNonEmptyQ); return top; } int myStackTop(MyStack* obj) { Queue* pEmptyQ = &obj->q1; Queue* pNonEmptyQ = &obj->q2; if (!QueueEmpty(&obj->q1)) { pEmptyQ = &obj->q2; pNonEmptyQ = &obj->q1; } int top = QueueBack(pNonEmptyQ); return top; } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); } /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */
