【九度】题目1512：用两个栈实现队列

本文主要是介绍【九度】题目1512：用两个栈实现队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：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

这个题有必要说一下。
两个栈实现队列。
栈是先进后出，队列是先进先出。
stack1存储数据，stack2用做辅助栈。
PUSH操作简单，直接入栈。
POP的时候，判断stack2是否为空，如果不为空直接pop数据。
否则判断stack1是否为空，如果为空，说明没数据了，直接输出-1
不为空，就将数据全部入stack2.弹出栈顶元素。
C++ AC

#include <stdio.h>
#include <stack>   
#include <string.h>
#include <string>
using namespace std; 
int n,i; int main(){while(scanf("%d",&n) != EOF){stack<int> stack1;stack<int> stack2;for(i = 0; i < n; i++){char operate[5];scanf("%s",operate);if(strcmp(operate,"PUSH") == 0){int k;scanf("%d",&k);stack1.push(k);}else{if(!stack2.empty()){int top = stack2.top(); printf("%d\n",top);stack2.pop();}else{if(stack1.empty()){printf("-1\n");}else{while(!stack1.empty()){int top = stack1.top();stack1.pop();stack2.push(top);}printf("%d\n",stack2.top());stack2.pop();}}}}          }return 0;
}  
/**************************************************************Problem: 1512User: wangzhenqingLanguage: C++Result: AcceptedTime:70 msMemory:1184 kb
****************************************************************/

Java AC

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;public class Main {/** 1522*/public static void main(String[] args) throws Exception {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));while (st.nextToken() != StreamTokenizer.TT_EOF) {int n = (int) st.nval;Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();for (int i = 0; i < n; i++) {st.nextToken();String a = st.sval;if (a.equals("POP")) {if (stack2.isEmpty()) {while(!stack1.isEmpty()){stack2.push(stack1.pop());}}if (stack2.isEmpty()) {System.out.println(-1);}else {System.out.println(stack2.pop());}}else if (a.contains("PUSH")) {st.nextToken();int tempNum = (int) st.nval;stack1.push(tempNum);}}}}
}
/**************************************************************Problem: 1512User: wangzhenqingLanguage: JavaResult: AcceptedTime:1370 msMemory:42204 kb
****************************************************************/

这篇关于【九度】题目1512：用两个栈实现队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---