一、题目
函数原型：
typedef struct {
} MyStack;
MyStack* myStackCreate()
void myStackPush(MyStack* obj, int x)
int myStackPop(MyStack* obj)
int myStackTop(MyStack* obj)
bool myStackEmpty(MyStack* obj)
void myStackFree(MyStack* obj)
二、思路
利用队列实现栈：
1.我的栈的结构
“我的栈”是一个结构体，存放两个队列即可
2.我的栈创建及其初始化
函数返回值是“我的栈”结构体指针，动态申请一个“我的栈”大小内存空间，然后初始化“我的栈”结构体中中的两个队列，最后返回“我的栈”的结构体指针
3.我的栈入栈
“我的栈”中有两个队列，选择一个空队列进行存储数据。由于栈的入栈和队列的入队都是从尾部进行存储数据的，所以直接对空队列进行入队操作即可。
如何找到空队列？
利用假设法，假设q1为空队列，q2为非空队列；判断q1是否为空，如果不为空，则将空队列设为q2，非空队列设为q1.
4.我的栈出栈
由于栈删除元素是从栈顶删除，而队列删除元素是从队头删除，所以需要先将非空队列中的前n-1个元素出队并入队到空队列中，第n个元素直接出队无需入队。即可完成“我的栈”的出栈。
5.我的栈取栈顶元素
取栈顶元素是在栈尾部进行的，所以可以对非空队列的取队尾元素。
6.我的栈判空
只要对两个队列判空即可，只有当两个队列都为空时，“我的栈”才判断为空。
7.我的栈销毁
首先对“我的栈”中两个队列进行队列销毁，然后再对动态申请的“我的栈”空间进行动态内存释放。
三、代码
typedef int QDataType; //队列的结构定义 typedef struct QueueNode{ QDataType val; struct QueueNode *next; }QNode; //用结构体管理队列 typedef struct Queue{ QNode* phead; QNode* ptail; int size; }Queue; //队列的初始化 void QueueInit(Queue* pq) { pq->phead=NULL; pq->ptail=NULL; pq->size=0; } //入队 void QueuePush(Queue *pq,QDataType x) { assert(pq); QNode *newnode=(QNode*)malloc(sizeof(QNode)); if(newnode==NULL) { perror("malloc fail"); exit(-1); } newnode->val=x; newnode->next=NULL; if(pq->phead==NULL)//队列为空 pq->phead=pq->ptail=newnode; else { pq->ptail->next=newnode; pq->ptail=newnode; } pq->size++; } //出队 void QueuePop(Queue* pq) { assert(pq); assert(pq->phead);//空队列 if(pq->phead==pq->ptail) { pq->ptail=NULL; } QNode* tmp=pq->phead; pq->phead=tmp->next; free(tmp); tmp=NULL; pq->size--; } //取队头元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } //取队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } //判空 bool QueueEmpty(Queue *pq) { assert(pq); return pq->phead==NULL; } //销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode *cur=pq->phead; while(cur) { QNode* tmp=cur; cur=cur->next; free(tmp); tmp=NULL; } pq->phead=pq->ptail=NULL; pq->size=0; } typedef struct { Queue q1; Queue q2; } MyStack; //我的栈创建及其初始化 MyStack* myStackCreate() { MyStack *ps=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&ps->q1); QueueInit(&ps->q2); return ps; } void myStackPush(MyStack* obj, int x) { //利用假设法 Queue *empty=&obj->q1; Queue *noneempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noneempty=&obj->q1; } QueuePush(noneempty,x); //QueuePush(&obj->q1,x); } //我的栈-出栈 int myStackPop(MyStack* obj) { // while(obj->q1.size>1) // { // QueuePush(&obj->q2,QueueFront(&obj->q1)); // QueuePop(&obj->q1); // //QueuePush(&obj->q2,QueuePop(&obj->q1)); // } // int stackpop=QueueFront(&obj->q1); // QueuePop(&obj->q1); // while(obj->q2.size) // { // QueuePush(&obj->q1,QueueFront(&obj->q2)); // QueuePop(&obj->q2); // //QueuePush(&obj->q1,QueuePop(&obj->q2)); // } // return stackpop; //利用假设法 Queue *empty=&obj->q1; Queue *noneempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noneempty=&obj->q1; } while(noneempty->size>1) { QueuePush(empty,QueueFront(noneempty)); QueuePop(noneempty); } int stackpop=QueueFront(noneempty); QueuePop(noneempty); return stackpop; } //我的栈-出栈 int myStackTop(MyStack* obj) { Queue* empty=&obj->q1; Queue* noneempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noneempty=&obj->q1; } return QueueBack(noneempty); } //我的栈-判空 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); */
