Java堆栈队列获取可以查看前端的人数

Question

我有一个模拟队列的程序，其中有两种类型的输入join和leave

join输入加上一个整数，表示一个人的身高，就像join 180，而leave输入加上一个整数，表示离开队列的人数leave 3

每次调用加入或离开查询时，程序都应该返回可以查看队列前面的人数。如果在他/她前面排队的每个人都比他/她矮，或者如果他/她是队列中的第一个人，那么他/她可以看到前面

输入/输出示例如图所示

这是我的代码，我创建了两个堆栈来存储队列中的人数，以及可以查看前面的人数：

 private void run() {
        Scanner sc = new Scanner(System.in);
        int no_queries = Integer.parseInt(sc.nextLine());

        for(int i = 0; i < no_queries; i++){
            String[] queries = sc.nextLine().split(" ");
            int value = Integer.parseInt(queries[1]);
            switch(queries[0]){
                    case "join":
                        if(!height.empty()){
                            if(height.peek() < value){
                                height.add(value);
                            }
                        }else{
                            height.add(value);
                        }
                        stack.add(value);
                        System.out.println(height.size());
                    break;
                    case "leave":
                        for(int j = 0; j < value; j++){
                            stack.pop();
                            }
                        //how do i remove the height stack?
                        System.out.println(height.size());
                    break;
            }
        }
    }

这是我的输出，最后三项是错误的：

1
0
1
1
1
2
3
2
2
0
1
0

我的问题在于高度堆栈。当给出leave 3查询时，整数160、170和165将从队列堆栈中移除

然而，高度堆栈只包含两个整数160和170，并且这两个值都将被查询删除，尽管具有高度160的人不应从队列中删除，因为他在前面，而不是离开的3人的一部分

我考虑过使用Person对象来存储最高的Person变量，但是有没有更优雅的方法来解决这个问题呢

Answer 1

这里有另一种解决问题的方法。 添加到堆栈中的每个元素都被赋予一个标识符y_或n_，以指示它们是否是特定堆栈中的最高元素

private void run() {
    Scanner sc = new Scanner(System.in);
    int no_queries = Integer.parseInt(sc.nextLine());

    for(int i = 0; i < no_queries; i++){
        String[] queries = sc.nextLine().split(" ");
        int value = Integer.parseInt(queries[1]);
        switch(queries[0]){
                case "join":
                    if(stack.empty()){
                        stack.add(String.format("y_%d", value));
                        height.add(String.format("y_%d", value));  
                    }else{
                        if(!height.empty()){
                            if(Integer.parseInt(height.peek().substring(2)) < value){
                                stack.add(String.format("y_%d", value));
                                height.add(String.format("y_%d", value)); 
                            }else{
                                stack.add(String.format("n_%d", value));                                    
                            }
                        }
                    }
                    System.out.println(height.size());
                break;
                case "leave":
                    for(int j = 0; j < value; j++){
                        if(!height.empty()){
                            if(height.peek().equals(stack.pop())){
                                height.pop();
                            }
                        }
                    }
                    System.out.println(height.size());
                break;
        }
    }
}

Answer 2

我认为可以使用Person对象，而不是存储最高的人，而是使比较两个堆栈中的值成为可能。我的意思是，当你做stack.pop();的时候，你需要一种方法来检查你是否从你的堆栈中删除了最高层的人对象，如果是这样的话，也从最高层的人的堆栈中删除它

static class Person {
    int height;
    Person (int height) {
        this.height = height;
    }
}

private static void run() {
    Stack<Person> stack = new Stack<>();
    Stack<Person> highest = new Stack<>();
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.nextLine());

    for (int i = 0; i < n; i++) {
        String[] queries = sc.nextLine().split(" ");
        int value = Integer.parseInt(queries[1]);
        switch (queries[0]) {
            case "join":
                Person person = new Person(value);
                if (highest.empty()) {
                    highest.push(person);
                } else if (value > highest.peek().height) {
                    highest.push(person);
                }
                stack.push(person);
                System.out.println(highest.size());
                break;
            case "leave":
                for (int j = 0; j < value; j++) {
                    Person left = stack.pop();
                    if (left == highest.peek()) {
                        highest.pop();
                    }
                }
                System.out.println(highest.size());
                break;
        }
    }
}