一.题目
二.思路
1.后入先出的实现：
创建两个队列来实现栈（后入先出）：
两个队列，保持一个存数据，另一个为空，入数据（push）要入不为空的队列，（pop）时要把非空队列的前size-1个数据转移到空队列中，所剩下的数据就是我们要出的数据（pop）。
2.图示：
3.整体实现
这里我们将队列q1,q2封装在结构体MyStack中，所以我们的关系构架为：
(1)初始化
为了防止局部变量出作用域后销毁，这里要malloc新的结构体。
MyStack* myStackCreate()
{
MyStack* st=(MyStack*)malloc(sizeof(MyStack));
if(st==NULL)
return false;
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}(2)入数据
入数据时要入非空队列中去
void myStackPush(MyStack* obj, int x)
{
if(QueueSize(&obj->q1)!=0)
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}(3)出数据
为保证后入先出，我们将非空队列的前size-1个数据转移到空队列中去，剩下来的那一个数据就是栈顶元素。
int myStackPop(MyStack* obj)
{
Queue* tmp=&obj->q1;
Queue* notmp=&obj->q2;
if(QueueSize(notmp)==0)
{
tmp=&obj->q2;
notmp=&obj->q1;
}
while(QueueSize(notmp)>1)
{
QueuePush(tmp,QueueFront(notmp));
QueuePop(notmp);
}
QDataType res=QueueFront(notmp);
QueuePop(notmp);
return res;
}(4)返回栈顶元素
int myStackTop(MyStack* obj)
{
if(QueueSize(&obj->q1)!=0)
return QueueBack(&obj->q1);
else
return QueueBack(&obj->q2);
}(5)判空
两个队列都为空才能说明栈是空的
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}(6)销毁
要先将两个队列销毁，再销毁结构体obj。
void myStackFree(MyStack* obj)
{
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}三.参考代码
typedef int QDataType;
typedef struct QNode
{
struct QNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}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);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
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;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
if (tmp == NULL)
{
perror("malloc failed");
exit(-1);
}
tmp->next = NULL;
tmp->data = x;
if (pq->head == pq->tail && pq->head == NULL)
{
pq->head = pq->tail = tmp;
}
else
{
pq->tail->next = tmp;
pq->tail = tmp;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
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;
}
pq->size--;
}
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;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
MyStack* st=(MyStack*)malloc(sizeof(MyStack));
if(st==NULL)
return false;
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
void myStackPush(MyStack* obj, int x)
{
if(QueueSize(&obj->q1)!=0)
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj)
{
Queue* tmp=&obj->q1;
Queue* notmp=&obj->q2;
if(QueueSize(notmp)==0)
{
tmp=&obj->q2;
notmp=&obj->q1;
}
while(QueueSize(notmp)>1)
{
QueuePush(tmp,QueueFront(notmp));
QueuePop(notmp);
}
QDataType res=QueueFront(notmp);
QueuePop(notmp);
return res;
}
int myStackTop(MyStack* obj)
{
if(QueueSize(&obj->q1)!=0)
return QueueBack(&obj->q1);
else
return QueueBack(&obj->q2);
}
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
