使用两个Queue实现Pop和Push方法的Java代码问题求助

需求 #

通过两个队列实现栈的push(x)和pop()方法。

实现代码 #

Queue类 #

public class Queue {
    Node first;
    Node last;
    int N;
    
    public Queue() {
        first = null;
        last = null;
        N = 0;
    }
    
    class Node{
        int data;
        Node next;
        }
    
    public int add(int x) {
        Node u = new Node();
        u.data = x;
        u.next = first;
        first = u;
        if (N==0) {
            last =u;
        }
        N++;
        return x;
    }
    
    public boolean isEmpty() {
        boolean isEmpty = false;
        if(N==0) {
            isEmpty = true;
        }
        return isEmpty;
    }
    
    public int remove(int i) {
        if (N==0) {
            return (Integer) null;
        }
        int x = first.data;
        if (--N == 0) {
            last = null;
        }
        N--;
        return x;
    }
    
    public void display() {
        Node current = first;
        
        if(first == null) {
            System.out.println("List is empty.");
        }
        System.out.print("Nodes: ");
        while(current != null) {
            System.out.print(current.data+", ");
            current = current.next;
        }
        System.out.println();
    }
    
    public int size() {
        return N;
    }
}

DoubleQueue类 #

public class DoubleQueue {
    // Creates 2 queues for the push and pop methods.
    static Queue q1 = new Queue();
    static Queue q2 = new Queue();

    // Push method.
    int push(int x) {
        Node u = q1.new Node(); // Creates new node.
        u.data = x; // Sets node to the value x.
        u.next = q1.first; // Places the new node at the head of the stack.
        q1.first = u; 
        if (q1.N==0) { // Checks if node is empty and adds it as tail if it is.
            q1.last = u;
        }
        q1.N++; // Increments the element counter.
        return x; 
        }
    
    // Pop method.
    static int pop() {
        // Sets variables.
        Node q1curr = q1.first;
        Node q1prev = null;
        Node q2curr = null;
        Node q2prev = null;
        int q1size = q1.size();
        int q2size;
        
        if (q1.N == 0) { // Checks if the queue is empty.
            return (Integer) null;
        }
        int x = q1.first.data; // Sets x to the head value.
        for(int i = 0; i <= q1.size(); i++) { // Loop to check entire queue.
            if (q1curr.data == x) { // If the data does not match x, it is added to the second queue.
                q1.remove(q1curr.data);
                q1curr = q1curr.next;
                System.out.print("q");
            }
            else { // If the data matches x, the counter is moved and the data is deleted.
                q2.add(q1curr.data);
                q1.remove(q1curr.data);
                q1curr = q1curr.next;
                System.out.println("x");
            }
        }
        
        q2curr = q2.first;
        q2size = q2.size();
        q1.display();
        q2.display();

        // Adds all the elements back into the first queue.
        for (int i = 0; i < q2.size(); i++) {
            if (q2curr != null) {
                q1.add(q2curr.data);
                q2curr = q1curr.next;
            }
        }
        
        return x; // Returns the value removed.
    }
}

Main类 #

public class Main {

    public static void main(String[] args) {
        DoubleQueue dq = new DoubleQueue();
        dq.q1.add(1);
        dq.q1.add(2);
        dq.q1.add(3);
        dq.q1.add(4);
        dq.q1.add(5);
        dq.q1.display();
        dq.push(7);
        dq.q1.display();
        dq.pop();
        dq.q1.display();
    }

}

遇到的问题 #

• 最初尝试交换q1和q2时，q2元素顺序反转；
• 改为循环将元素放回q1时，循环仅执行2次就终止；
• q1无法每次正常删除数据，q2仅能添加两个节点，需排查原因。

排查建议 #

1. 修复Queue类的核心实现错误 #

你的Queue类不符合队列**FIFO（先进先出）**的基本特性：

• add方法把新节点插在first前，是栈的逻辑，正确队列应该把新节点追加到last后；
• remove方法完全错误：参数i未被使用，且执行了两次N--导致计数异常，同时没有修改链表指针（仅返回first.data，但first未移动）。

2. 修正DoubleQueue的pop逻辑 #

• 栈的pop需要移除最后加入的元素，若Queue修复为正确FIFO，应将q1中除最后一个元素外的所有元素移到q2，移除q1剩余元素后再将q2元素移回q1；
• 循环条件i <= q1.size()不合理：每次remove会改变q1.size()，导致循环次数异常，应先记录初始q1大小，用固定值作为循环次数；
• q1curr = q1curr.next在remove后执行会触发空指针，因为remove已改变q1结构；
• 元素移回q1时，q2curr = q1curr.next是错误的，应为q2curr = q2curr.next。

3. 调整变量作用域 #

DoubleQueue中的q1和q2为静态变量，会导致多个实例共享同一队列，改为成员变量可避免逻辑混乱。

内容的提问来源于stack exchange，提问作者Dash Harber