Java 队列页面替换

Question

我有一个循环队列，它应该实现第二次机会页面替换算法。所以，假设我有一个 2D 字符数组，如下所示:

QUEUE: [a, 0] [c, 0] [b, 0] [k, 0] 

每个元素都包含一个字符和一个额外的位。当我们想要将元素添加到存在的队列时，引用位应该从0更改为1。如下所示:

// Adding char 'a' to queue below
QUEUE: [a, 1] [c, 0] [b, 0] [k, 0] 

这提供了第二次机会，以便在应添加新元素时不删除该字符。程序应绕过位为 1 的元素，将其位更改为 0(第二次机会)并将其添加到所需的索引中队列层次结构。添加不存在的新元素时会出现问题。因此，我的代码基本上扫描队列数组并添加到第一个字符值，它看到索引 0，并且在大输入中产生问题，因为我松散层次结构:

public char replace(char c) {
        char tmp = 0; // If nothing is replaced returns 0
        if (isempty()) {
            throw new IllegalStateException("Queue is empty, cant dequeue");
        } else if (this.front == this.rear) {
            front = -1;
            rear = -1;
            numOfelements--;
        } else {
            for(int i = front; i <= rear; i = (i+1)%size ){
                if(queue[i][1] == '0'){
                    tmp = queue[i][0];
                    queue[i][0] = c;
                    break;
                } else {
                    queue[i][1] = '0';
                }
            }
        }
        return tmp;  
    }

例如:假设我们将“b”添加到下面的队列中:

QUEUE: [a, 1] [c, 1] [b, 0] [k, 0] 

当我添加“d”时，它变成这样:

 QUEUE: [a, 0] [c, 0] [d, 0] [k, 0]

之后，当我尝试添加“p”时，它会将其添加到“a”，但它应该将其添加到 k。

Answer 1

您解释的算法完全按照您解释的方式执行。 结果就是您对该算法的期望。

但是你想要一些不同的东西。看来您想要的是每次将 1 更改为 0 时，相应的队列条目都会移至队列末尾。

这可能就是你的意思

and add it into the needed index according to queue hierarchy

但在这种情况下，您忘记了实际执行该部分。

我现在假设 front 和 after 是标记数组的第一个和最后一个索引的变量:

} else {
    char currentChar = queue[i][0];
    for (int j = i; j < rear; j++) {
        queue[j][0] = queue[j+1][0];
        queue[j][1] = queue[j+1][1];
    }
    queue[rear][0] = currentChar;
    queue[rear][1] = '0';
    i--;
}

请记住，这段代码只是为了说明您必须执行的操作，并且不是经过测试的代码。

<小时/>

或者，如果 front 和 back 实际上应该告诉你从哪里开始和结束(我认为由于 % 运算符就是这种情况)，那么你必须设置 front 和将 char 分配到某处后，将后置为新值。但是，如果应该是这样，这将使您的 for 循环无效，因为您实际上可能会比后部更高的位置开始，并且不希望 for 停止。

它应该看起来像这样:

for(int i = front; i != rear; i = (i+1)%size ){
    if(queue[i][1] == '0'){
        tmp = queue[i][0];
        queue[i][0] = c;
        front = (i+1) % size;
        rear = i;
        break;
    } else {
        queue[i][1] = '0';
    }
}

再次强调:请记住这段代码只是为了说明您必须做什么，并且不是经过测试的代码。 这假设前部和后部都在数组边界内!