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

1.解题思路

这道题如果使用C++会好写的多，因为可以使用C++提供的队列来实现，但如果使用C语言则必须手写一个队列来实现，在这里我用了我前面文章中实现好的队列来解答，首先因为队列是先进先出，而栈是后进后出，因此我们可以设计两个队列，其中一个队列放数据，另一个队列为空
在这里插入图片描述
当使用POP接口出栈时，则可将队列一的前N-1个数据挪到队列二上，这样一来，队列一剩余的那个数就为要出栈的数

即这道题的精髓就是两个队列之间数据的传递.

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;elsereturn true;
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);
}