仅使用队列来逆转队列。获得indexofbound例外

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队列中。它为所有元素做到了这一点。