typedef struct Node
{
	int data;
	Node *next;
}Node, *LinkStack;

//创建空栈
LinkStack CreateNULLStack(LinkStack &S)
{
	S = (LinkStack)malloc(sizeof(Node));
	if (nullptr == S)
	{
		cout << "Failed to malloc a new code" << endl;
		return nullptr;
	}

	S->data = 0;
	S->next = nullptr;

	return S;
}

//栈插入函数
LinkStack Push(LinkStack &S, int data)
{
	if (nullptr == S)
	{
		cout << "There no node in stack" << endl;
		return nullptr;
	}

	LinkStack p = nullptr;
	p = (LinkStack)malloc(sizeof(Node));
	if (nullptr == p)
	{
		cout << "Failed to malloc a new code" << endl;
		return S;
	}

	if (nullptr == S->next)
	{
		p->next = nullptr;
	}
	else
	{
		p->next = S->next;
	}

	p->data = data;
	S->next = p;

	return S;
}

//出栈函数
Node Pop(LinkStack &S)
{
	Node temp;
	temp.data = 0;
	temp.next = nullptr;

	if (nullptr == S)
	{
		cout << "There no node in stack" << endl;
		return temp;
	}

	temp = *S;

	if (nullptr == S->next)
	{
		cout << "The stack is NULL, no Pop" << endl;
		return temp;
	}
	LinkStack p = S->next;

	S->next = S->next->next;
	temp = *p;
	free(p);
	p = nullptr;

	return temp;
}

//双栈实现队列的入队函数
LinkStack StackToQueuePush(LinkStack &S, int data)
{
	Node n;
	LinkStack S1 = nullptr;
	CreateNULLStack(S1);  //创建空栈

	while (nullptr != S->next)  //S出栈入S1
	{
		n = Pop(S);
		Push(S1, n.data);
	}

	Push(S1, data);

	while (nullptr != S1->next) //S1出栈入S
	{
		n = Pop(S1);
		Push(S, n.data);
	}

	return S;
}