两个栈实现队列

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。

输入：

每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。

输出：

对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。

样例输入：

3
PUSH 10
POP
POP

样例输出：

10
-1

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
#include<stdbool.h> 

typedef struct Node
{
	int data;
	struct Node *pNext;
}Node,*pNode;

typedef struct Stack
{
	pNode pTop;
	pNode pBottom;
}Stack,*pStack;

/*创建一个空栈，并返回指向该栈的指针*/

pStack createStack()
{
	pStack ps=(pStack)malloc(sizeof(Stack));
	ps->pTop=(pNode)malloc(sizeof(Node));
	if(ps==NULL||ps->pTop==NULL)
		return NULL;
	else
	{
		ps->pBottom=ps->pTop;
		ps->pBottom->pNext=NULL;
	}
	return ps;
}
/*判断该栈是否为空 */
bool isEmpty(pStack ps)
{
	if(ps->pTop==ps->pBottom)
		return true;
	else
		return false;
}

/*向ps指针指向的栈中压入数据val*/
void  pushStack(pStack ps,int val)
{
	pNode pNew =(pNode)malloc(sizeof(Node));
	if(pNew==NULL)
		return ;
	else
	{
		pNew->data=val;
		pNew->pNext=ps->pTop;
		ps->pTop=pNew;
	} 
	return;
}
/*从栈中退出数据,并将数据的保存在pData指针指向的位置*/
bool popStack(pStack ps,int* pData)
{
	if(isEmpty(ps))
		return false;
	else
	{
		pNode p = ps->pTop;
		*pData=p->data;
		ps->pTop=p->pNext;
		free(p);
		p=NULL;
		return true;
	}
}

/*清空栈,即将其还原为空栈*/

void clearStack(pStack ps)
{
	if(isEmpty(ps))
		return;
	else
	{
		pNode p = ps->pTop;
		pNode r=NULL;
		while(p!=ps->pBottom)
		{
			r=p->pNext;
			free(p);
			p=r;
		}
		ps->pTop=ps->pBottom;
	}
}

/*用两个栈模拟入队*/
void enterQueue(pStack ps,int val)
{
	pushStack(ps,val);
}

/*用两个栈模拟出对*/
bool deleteQueue(pStack ps1,pStack ps2,int *pData)
{
	if(isEmpty(ps1)&&(isEmpty(ps2)))
		return false;
	if(!isEmpty(ps2))
		popStack(ps2,pData);
	else if(!isEmpty(ps1))
	{
		while(!isEmpty(ps1))
		{
			int ps1PopData;
			popStack(ps1,&ps1PopData);
			pushStack(ps2,ps1PopData); 
		}
		popStack(ps2,pData);
	}
	return true;
}
int main()
{
	int number;      //保存操纵的个数  
    int data;   //保存输入的要push的元素  
    int pData;  //保存pop出来的元素  
    char *push = "PUSH";  
    char *pop = "POP";  
    char input[5];  
    int data_pop;  
    
    //创建两个栈
	pStack ps1 = createStack();
	pStack ps2 = createStack();
	
	scanf("%d",&number);
	
	while(number-->0)
	{
		scanf("%s",input);
		if(strcmp(input,push)==0)
		{
			scanf("%d",&data);
			enterQueue(ps1,data); 
		}
		if(strcmp(input,pop)==0)
		{
			if(deleteQueue(ps1,ps2,&pData))
				printf("%d\n",pData);
			else
				printf("-1\n"); 
		}
	} 
	clearStack(ps1);  
    clearStack(ps2);  
    return 0; 
}

结果：