题目：

225. 用队列实现栈 - 力扣（LeetCode）

准备工作

这题明确说明了需要用队列来实现栈，介于C语言没有队列的库，所以在此之前我们需要用调用之前学的队列，详见队列

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(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->head = pq->tail = NULL;
}void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}// 队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}// 队头出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);// 1、一个// 2、多个if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){++size;cur = cur->next;}return size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}

看懂题

这样之后，我们有些小伙伴觉得自己英语不好，看不懂那些函数名，从而放弃这题，其实这里和英语好不好是没有太多关系的。注意看：

我们通过观察返回值，从而进一步确认意思。

创建结构体

“typedef struct”这个函数，有过对数据结构的基础认识，看到“struct”肯定是创建结构体。创建出的结构体决定了我们之下来的解题思路。

所以我们先来了解一下实现这题的基本思路：

基本思路

我们如此反复倒数据，每次到最后一个元素就把它pop掉，所以我们避免不了要用到两个指针，指向两个链表的指针。

如此一来“typedef struct”这个函数就容易实现了。

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

创建空间

“MyStack* myStackCreate() “：我们有了结构体，一定要初始化，不初始化会导致结构体内部的值不确定，容易出错。现在最新的“vs”如果不初始化，都编译不了了。

MyStack* myStackCreate() 
{MyStack* pq = (MyStack*)malloc(sizeof(MyStack));if(pq == NULL){perror("malloc:");exit(-1);}QueueInit(&pq->q1);QueueInit(&pq->q1);return pq;
}

入栈

这个比较简单，谁不为空就进谁

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

出栈

首先我们要注意我们不能知道是q1是空的还是q2是空的，所以我们干脆假设一个是空的，然后再来判断，又由于我们队列是可以直接头删，我们直接倒到空的那一个。

int myStackPop(MyStack* obj) 
{Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(&obj->q1)){empty = &obj->q2;nonempty = &obj->q1;}while(QueueSize(nonempty) > 1){QueuePush(empty, QueueFront(empty));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) 
{retun QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

释放空间

释放两个链表的同时，不要忘记释放两个指针，避免内存泄漏。

void myStackFree(MyStack* obj) 
{QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(ps);ps = NULL;
}

总结

我们可以发现原理（几幅图就能搞定）都不难，主要是代码的实现，需要注意许多细节，一定要注意避免内存泄漏。

欢迎大家点赞和评论。