题目地址：http://ac.jobdu.com/problem.php?pid=1512
- 题目描述：
-
用两个栈来实现一个队列，完成队列的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> typedef struct node{ int data; struct node * next; }Node; void Push (Node ** stack,int data){ Node * p = (Node *)malloc(sizeof(Node)); if (p != NULL){ p->data = data; p->next = *stack; *stack = p; //return 1; } //return 0; } int Pop (Node ** stack){ int data; Node * p = *stack; if (*stack != NULL){ data = p->data; *stack = p->next; free (p); return data; } return -1; } void EnQueue (Node ** Queue1,int data){ Push (Queue1,data); } int DeQueue (Node ** Queue1,Node ** Queue2){ int data; if (*Queue2 != NULL){ data = Pop (Queue2); return data; } else if (*Queue1 != NULL){ while (*Queue1 != NULL){ data = Pop (Queue1); Push (Queue2,data); } return Pop (Queue2); } else return -1; } int main(void){ int n; char operate[5]; char * push = "PUSH"; int data; Node * queue1 = NULL; Node * queue2 = NULL; scanf ("%d",&n); while (n-- != 0){ scanf ("%s",operate); if (strcmp (operate,push) == 0){ scanf (" %d",&data); EnQueue (&queue1,data); } else{ printf ("%d\n",DeQueue (&queue1,&queue2)); } } return 0; }
参考资料： 何海涛 -- 程序员面试题精选100题(18)－用两个栈实现队列[数据结构]
