算法-06由两个栈组成的队列

2022/1/9 22:33:37

本文主要是介绍算法-06由两个栈组成的队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

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

输入描述:

第一行输入一个整数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

思路

栈的特点是先进后出,队列的特点是先进先出,用俩个栈正好能把顺序发过来实现类似队列的操作。

1)一个栈作为压入栈,在压入时只往这个栈中压入,另一个栈作为弹出栈,在弹出数据的时候只从这个栈弹出。

2)因为数据压入栈的时候顺序是先进后出的,那么只要把压入栈的数据再压入到弹出栈,顺序就变回来了。

 

import java.util.Stack;
import java.util.Scanner;

class TwoStacksQueue{
    public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;
    
    public TwoStacksQueue(){
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }
    
    public void pushToPop(){
        if(stackPop.empty()){
            while(!stackPush.empty()){
                stackPop.push(stackPush.pop());
            }
        }
    }
    
    public void add(int pushInt){
        stackPush.push(pushInt);
        pushToPop();
    }
    
    public int poll(){
        if(stackPop.empty() && stackPush.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        pushToPop();
        return stackPop.pop();
    }
    
    public int peek(){
        if(stackPop.empty() && stackPush.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        pushToPop();
        return stackPop.peek();
    }
}

public class Main{
    public static void main(String[] args){
        
        TwoStacksQueue twostacksqueue = new TwoStacksQueue();
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        for(int i=0;i<n;i++){
            String op = scanner.next();
            if(op.equals("add")){
                int x = scanner.nextInt();
                twostacksqueue.add(x);
            }else if(op.equals("poll")){
                twostacksqueue.poll();
            }else if(op.equals("peek")){
                System.out.println(twostacksqueue.peek());
            }
        }
    }
}

 



这篇关于算法-06由两个栈组成的队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程