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;
else
return true;
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
}
结尾：今天的分享到此结束，喜欢的朋友如果感觉有帮助可以点赞三连支持，咱们共同进步!
