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

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

THE END