题目链接

解题思路

栈的结构特点是后入先出。

本题核心思路是：

1. 入数据时，往不为空的队列入数据，保持另一个队列为空。
2. 出数据，依次出掉队头数据到另一个队列，留下最后一个数据，pop

图解

1. 定义两个队列q1和q2，第一步压入1, 2，3,4
   
2. 弹出4（后入的数据）
   
3. 压入 5，6,7
   

栈结构

本题中我们考虑到一个因素，函数是在栈区开辟的，栈帧随着函数结束而销毁，所以初始化的栈要放在堆区。

代码题解

typedef int QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;// 初始化队列
void QueueInit(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType x);
// 队头出队列
void QueuePop(Queue* pq);
// 判断队列是否为空
bool QueueEmpty(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列尾部元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// 创建新结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->next = NULL;newnode->data = x;// 尾插// 空链表if (pq->head == NULL){pq->head = pq->tail = newnode;}else{// 非空链表pq->tail->next = newnode;pq->tail = newnode;}
}void QueuePop(Queue* pq)
{assert(pq);// 空链表assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){// 链表此时已经为空pq->tail = NULL;}
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}int QueueSize(Queue* pq)
{assert(pq);int n = 0;QueueNode* cur = pq->head;while (cur)  // cur指向NULL的时候退出循环{++n;cur = cur->next;}return n;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}// 每一个结点都要释放了，把head和tail置为NULLpq->head = pq->tail = NULL;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&st->q1);QueueInit(&st->q2);return st;
}void myStackPush(MyStack* obj, int x) {// 入数据到不为空的队列if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {// 把队列中数据都转移到另一个队列，再pop剩余的一个数字Queue* emptyQueue = &obj->q1;Queue* notemptyQueue = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQueue = &obj->q2;notemptyQueue = &obj->q1;}while(QueueSize(notemptyQueue) > 1){QueuePush(emptyQueue, QueueFront(notemptyQueue));QueuePop(notemptyQueue);}int ret = QueueFront(notemptyQueue);QueuePop(notemptyQueue);return ret;
}int myStackTop(MyStack* 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) {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);
*/

重点分析小结

1. 取栈头元素，只需要调用非空队列的尾指针

2. 针对测试用例报错

在写代码的时候遇到了一个报错

这时候，就需要逐行分析。

因为获得栈顶元素还可以通过把队头元素都转移到空队列，然后把最后一个数据的值直接返回。
但是！
在这里，我忘记了把这个元素压入队列里，导致了这样的错误。