用双栈模拟一个队列

Neo
Neo
2020-09-21 / 0 评论 / 216 阅读

题目描述

用两个栈实现队列,支持队列的基本操作。

输入描述:

第一行输入一个整数N,表示对队列进行的操作总数。
下面N行每行输入一个字符串S,表示操作的种类。
如果S为"add",则后面还有一个整数X表示向队列尾部加入整数X。
如果S为"poll",则表示弹出队列头部操作。
如果S为"peek",则表示询问当前队列中头部元素是多少。

输出描述:

对于每一个为"peek"的操作,输出一行表示当前队列中头部元素是多少。

示例1

输入
6
add 1
add 2
add 3
peek
poll
peek

输出
1
2

解题

/*
定义两个栈,一个栈专门用来模拟入队,一个栈用来模拟出队
add:a栈直接入栈
poll:b栈如果不为空就直接重b栈出栈元素,b栈如果为空就把a栈所有元素全部压入到b栈,再从b栈出栈
peek:过程跟poll一样
*/

import java.util.*;
import java.io.*;
 
public class Main{
     
    private static Stack<Integer> aStack =new Stack<>();
    private static Stack<Integer> bStack =new Stack<>();
     
    public static void main(String[] args) throws IOException{
         
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(in.readLine());
         
        StringBuilder result = new StringBuilder();
         
        while(n-- >0){
            String str= in.readLine();
            switch(str){
                case "peek":
                    result.append(peek()).append("\n");
                    break;
                case "poll":
                    poll();
                    break;
                default:
                    add(Integer.parseInt(str.split(" ")[1]));
            }
        }
        System.out.println(result.substring(0));
    }
     
    private static void add(int num){
        aStack.push(num);
    }
     
    private static void aTob(){
        if(bStack.isEmpty()){
            while(!aStack.isEmpty()){
                bStack.push(aStack.pop());
            }
        }
    }
     
    private static int poll(){
        aTob();
        return bStack.pop();
    }
     
    private static int peek(){
        aTob();
        return bStack.peek();
    }
     
}