使用堆栈的交换机路由(java语言)

Question

我一直在做我的大学作业，关于java中的栈，但是我似乎找不到这个作业的帮助。这是关于switchbox routing的，我需要使用stack来完成这个任务。作业明天就要交了，但是没有必要急于寻找答案，因为我只是在寻找答案，而不是成绩。因为这个问题不是用英语写的，所以我将给出简短的解释。

开关盒包含4n个针脚，盒的两边各有n个针脚。仅当连接一对端号的线路中没有一条与另一对端号相交时，开关盒才可布线。输入将是成对连接的引脚编号。

我找到了一些可能的解决方案，但无法理解: 1.问题可以用类似于圆括号匹配的算法来解决2.将引脚编号放入堆栈和数组中并进行比较(这是最令人困惑的一个)

到目前为止我的代码(尝试第二种算法)：

import java.util.Scanner;
import java.util.Stack;
public class Tester {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int cases=sc.nextInt();
        for(int i=0;i<cases;i++){            
            int pin=sc.nextInt();
            SwitchBox box=new SwitchBox(pin);
            for(int j=0;j<pin*4;j++){
                box.add(sc.nextInt());
            }            
            boolean res=box.isRoutable();
            if(res){
                System.out.println("routable");
            }
            else{
                System.out.println("not routable");
            }
        }
    }
    static class SwitchBox{
        Stack<Integer> pins;
        int[] pairs;
        int[] comparator;
        public SwitchBox(int pin){            
            this.pins=new Stack<Integer>();
            this.pairs=new int[(pin*4)];
            this.comparator=new int[this.pairs.length];
        }
        public boolean isRoutable(){
            Stack<Integer> s=new Stack<Integer>();
            for(int i=0;i<pairs.length;i++){
                pairs[i]=pins.peek();
                s.push(pins.pop());
            }
            for(int i=pairs.length-1;i>=0;i--){
                if(pairs[i]!=s.pop()){
                    return true;
                }
            }
            return false;
        }
        public void add(int pinNum){
            if(pins.isEmpty()){
                pins.push(pinNum);
            }
            else{
                Stack<Integer> temp=new Stack<Integer>();
                int top=(int)pins.peek();
                while(top>pinNum){
                    temp.push(pins.pop());
                    if(pins.isEmpty()) top=pinNum;
                    else top=(int)pins.peek();
                }
                pins.push(pinNum);
                while(!temp.isEmpty()){
                    pins.push(temp.pop());
                }
            }
        }
    }

}

Answer 1

在您的add方法中，else块是错误的。我不能理解你想做什么，但你需要做下一件事

public void add(int pinNum) {
    if (pins.isEmpty()) {
        pins.push(pinNum);
    } else {
        Integer last = pins.peek();
        if (last == pinNum) {
            pins.pop();
        } else {
            pins.push(pinNum);
        }
    }
}

在此之后，isRoutable方法只需要检查pins堆栈。如果它是空的，那么一切都好。否则就会有相交的线。