问题：
思路：
代码实现：
（注：下面代码涉及到队列的完整代码，如果有不懂的可以看小编之前发的文章《[数据结构]队列详解》）
typedef int QDataType;// 链式结构：表示队列
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{QNode * head;QNode* tail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType x);
// 队头出队列
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;//不是带哨兵位的头结点，需要判断第一个是否为空if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;//将新节点链接到队列的最后一个节点。pq->tail = newnode;//更新尾指针，使其指向新节点。}pq->size++;
}
// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head!=NULL);if (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--;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{return pq->size == 0;
}
// 获取队列头部元素
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;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack *pts =(MyStack *)malloc(sizeof(MyStack));if(pts==NULL){perror("malloc fail");}QueueInit(&pts->q1);QueueInit(&pts->q2);return pts;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emptyQ=&obj->q1;Queue* noemptyQ=&obj->q2;//假设q1为空q2不为空if(!QueueEmpty(&obj->q1)){emptyQ=&obj->q2;noemptyQ=&obj->q1;}//导数据while(QueueSize(noemptyQ)>1){QueuePush(emptyQ,QueueFront(noemptyQ));//把非空的数据导入到空列表里面去QueuePop(noemptyQ);}int top=QueueFront(noemptyQ);QueuePop(noemptyQ);//删除非空队列里面的那个数据（出栈）return top;
}int myStackTop(MyStack* obj) {if(QueueEmpty(&obj->q1)){return QueueBack(&obj->q2);}else{return QueueBack(&obj->q1);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}
