用两个队列实现栈

思路：

1. 构建队列（链表结构）；

2. 栈中包含两个队列Q1和Q2；

3. 入栈：若Q1和Q2都为空，则随便一个队列进行入队列；若某一个不为空，则不为空的那个队列进行入队列；不存在两个都不为空的情况；

4. 出栈：将不为空的队列从队首将元素复制另一个队列中，同时进行出栈 *** 作，直到只剩下一个元素为止，再进行最后一次出队列 *** 作。

源代码：

#include 
#include 
#include 
#include 

typedef int QData;

typedef struct	QNode
{
	QData data;
	struct QNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	while (pq->head)
	{
		QNode* cur = pq->head->next;
		free(pq->head);
		pq->head = cur;
	}
	pq->tail = NULL;
	printf("Queue is empty\n");
}

void QueuePush(Queue* pq, QData x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
		newnode->next = NULL;
	}
	else
	{
		pq->tail->next = newnode;
		newnode->next = NULL;
		pq->tail = pq->tail->next;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head->next;
	free(pq->head);
	pq->head = cur;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

QNode* QueueFront(Queue* pq)
{
	return pq->head;
}

QNode* QueueBack(Queue* pq)
{
	return pq->tail;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->head == NULL)
	{
		return true;
	}
	return false;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

typedef struct {
	Queue* Q1;
	Queue* Q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	obj->Q1 = (Queue*)malloc(sizeof(Queue));
	obj->Q2 = (Queue*)malloc(sizeof(Queue));
	QueueInit(obj->Q1);
	QueueInit(obj->Q2);
	return obj;
}

void myStackPush(MyStack* obj, int x) {
	if (QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2))
	{
		QueuePush(obj->Q1, x);
	}
	else if (!QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2))
	{
		QueuePush(obj->Q1, x);
	}
	else
	{
		QueuePush(obj->Q2, x);
	}
}

int myStackPop(MyStack* obj) {
	int x;
	if (!QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2))
	{
		while (obj->Q1->head->next)
		{
			int tmp = QueueFront(obj->Q1)->data;
			QueuePush(obj->Q2, tmp);
			QueuePop(obj->Q1);
		}
		x = QueueFront(obj->Q1)->data;
		QueuePop(obj->Q1);
	}
	else
	{
		while (obj->Q2->head->next)
		{
			int tmp = QueueFront(obj->Q2)->data;
			QueuePush(obj->Q1, tmp);
			QueuePop(obj->Q2);
		}
		x = QueueFront(obj->Q2)->data;
		QueuePop(obj->Q2);
	}
	return x;
}

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2))
	{
		return QueueBack(obj->Q1)->data;
	}
	else
	{
		return QueueBack(obj->Q2)->data;
	}
}

bool myStackEmpty(MyStack* obj) {
	if (QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2))
	{
		return true;
	}
	return false;
}

void myStackFree(MyStack* obj) {
	QueueDestory(obj->Q1);
	QueueDestory(obj->Q2);
	free(obj);
	obj = NULL;
}

int main()
{
	MyStack* my_stack = myStackCreate();
	myStackPush(my_stack, 1);
	myStackPush(my_stack, 2);
	myStackPush(my_stack, 3);
	myStackPop(my_stack);
	myStackPop(my_stack);
	int x = myStackTop(my_stack);	// 1
	bool x1 = myStackEmpty(my_stack);	//返回false
	myStackPop(my_stack);
	x1 = myStackEmpty(my_stack);		//返回true
	return 0;
}