How to get the intersection of two queues?-CodePudding

In a third queue, I need the intersection of 2 queues and they are ordered from minor to major pls Ex: Q1: [2,2,3,3] & Q2: [1,2,3,3,3,4] == Q3: [2,3,3]. I´ve tried my best but i cant :(

pls use the usual tda 4 queues


    public void update_queue() {
        for (int i = 0; i < top; i  ) {
            data[i] = data[i   1];
        }
        data[top] = 0;
    }

    public void print() {
        My_Queue tmp = new My_Queue();
        while (!this.isEmpty()) {
            int t = this.Dequeue();
            tmp.Enqueue(t);
            System.out.print(t   " - ");
        }
        System.out.println();
        while (!tmp.isEmpty()) {
            this.Enqueue(tmp.Dequeue());
        }
    }

    public void reemplace(int X, int Y){
        My_Queue tmp = new My_Queue();
        while(!this.isEmpty()){
            int t=this.Dequeue();
            if(t==X)
                t=Y;
            tmp.Enqueue(t);
           }
        while(!tmp.isEmpty())
            this.Enqueue(tmp.Dequeue());
    }
    public boolean search(int N){
        My_Queue tmp = new My_Queue();
        boolean flag = false;
        while (!this.isEmpty()) {
            int t = this.Dequeue();
            tmp.Enqueue(t);
            if (t == N) {
                flag = true;
            }
        }
        while (!tmp.isEmpty()) {
            this.Enqueue(tmp.Dequeue());
        }
        return flag;
    }

CodePudding user response：

You say they are ordered, so you can just go over them skipping over the lower element and adding to the result when elements match:

const q1 = [2,2,3,3]
const q2 = [1,2,3,3,3,4]

const getIntersection = (a1, i1, a2, i2) => 
  i1 >= a1.length || i2 >= a2.length ? [] : 
  a1[i1] !== a2[i2] ? getIntersection(a1, a1[i1] < a2[i2] ? i1   1 : i1, a2, a1[i1] > a2[i2] ? i2   1 : i2) : 
  [a1[i1], ...getIntersection(a1,i1 1,a2,i2 1)]

console.log(getIntersection(q1, 0, q2, 0))

CodePudding user response：

This is javascript code and I used arrays, but treated them as queues. Note that I did not test this.

function intersection(q1, q2){
    var result = [];
    while(q1.length > 0 && q2.length > 0){
        if(q1[q1.length-1] > q2[q2.length-1]){
            q1.pop();
        } else if(q1[q1.length-1] < q2[q2.length-1]){
            q2.pop();
        } else {
            result.push(q1.pop());
            q2.pop();
        }
    }

    return reverse(result);    
}

function reverse(q: number[]){
    var temp = [];
    while(q.length > 0)
        temp.push(q.pop());
    return temp;
}