反转队列，仅使用队列.获取索引绑定异常

Question

public static Queue1 mirror(Queue1 s){
    int len = s.getSize();
    Queue1 ret = new Queue1(s.getSize());
    Queue1 tmp = new Queue1(s.getSize());
    while(ret.getSize()!=len){
        while(s.getSize()>1) tmp.insert(s.remove());
        ret.insert(s.remove());
        while(tmp.getSize()>1) s.insert(tmp.remove());
        ret.insert(tmp.remove());
    }
    return ret;
}

我的插入和删除方法的实现：

public void insert(int x){
    if(rear == maxsize-1) rear = -1;
    arr[++rear] =  x;
    count++;
}
public int remove(){
    int tmp = arr[front++];
    if(front==maxsize) front = 0;
    count--;
    return tmp;
}

除非我将Tmp的大小增加到 s.getSize()+2，否则代码不起作用，在这种情况下，它会打印零。

有人可以解释一下发生了什么吗？

Answer 1

看起来您的循环缺少几个条件。

您的问题在这里：

while(ret.getSize()!=len){
    while(s.getSize()>1) tmp.insert(s.remove()); // 1
    ret.insert(s.remove()); // 2
    while(tmp.getSize()>1) s.insert(tmp.remove()); // 3
    ret.insert(tmp.remove()); // 4
}

假设您的输入是

s = [1 2 3]

在第一次执行 1 之后：

s = [3]
tmp = [1 2]
ret = []

2 后 ：

s = []
tmp = [1 2]
ret = [3]

3 之后 ：

s = [1]
tmp = [2]
ret = [3]

4 后 ：

s = [1]
tmp = []
ret = [3 2]

然后你重复步骤1，但它什么也不做：

s = [1]
tmp []
ret = [3 2]

然后第 2 步：

s = []
tmp = []
ret = [3 2 1]

现在你完成了，但你仍然在这里执行 3 和 4 在终止之前。步骤 3 将不执行任何操作，但步骤 4 将给出错误，因为您正在尝试从空队列中删除项目tmp。

解决方案是添加几个条件：

while(ret.getSize()!=len){
    while(s.getSize()>1) tmp.insert(s.remove());
    if (s.getSize() > 0) ret.insert(s.remove());
    while(tmp.getSize()>1) s.insert(tmp.remove());
    if (tmp.getSize()>0) ret.insert(tmp.remove());
}

Answer 2

我希望它有所帮助。我想自己找到解决问题的方法：仅使用队列来反转队列。这是我想到的：

public class Queue1 {
    private int maxSize, count, front, rear;
    private int[] arr;
    public Queue1(int maxSize) {
        arr = new int[maxSize];
        this.maxSize = maxSize;
        count = 0;
        front = 0;
        rear = 0;
    }
    public boolean insert(int x) {
        if (count == maxSize)
            return false;
        arr[rear] = x;
        rear = (rear + 1) % maxSize;
        count++;
        return true;
    }
    public int remove() throws Exception {
        if (count == 0) {
            throw new Exception("Cannot remove from queue: it's empty!");
        }
        int ret = arr[front];
        front = (front + 1) % maxSize;
        count--;
        return ret;
    }
    public int getSize() {
        return count;
    }
    public static Queue1 mirror(Queue1 q) throws Exception {
        int n = q.getSize();
        Queue1 ret = new Queue1(n);
        Queue1 tmp = new Queue1(n);
        boolean f = true;
        while (ret.getSize() < n) {
            if (f) {
                while (q.getSize() > 1)
                    tmp.insert(q.remove());
                ret.insert(q.remove());
            } else {
                while (tmp.getSize() > 1)
                    q.insert(tmp.remove());
                ret.insert(tmp.remove());
            }
            f = !f;
        }
        return ret;
    }
}

希望对您有所帮助！此解决方案有效。它遍历所有队列并到达最后一个元素并将其保存在ret队列中。它对所有元素执行此操作。