큐만 사용하여 큐를 반전합니다. 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; 
} 

내가 s.getSize()+2에 Tmp의 크기를 증가,이 경우는 0을 출력하지 않는 코드가 작동하지 않습니다.

누군가가 진행 상황을 설명해 주시겠습니까?

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 = [] 

이 후 :

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

당신은 1 단계를 반복하지만, 아무것도하지 그런

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

:

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

그런 다음 2 단계없는 :

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

3 후 :

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

사 후

이제 끝났지 만, 여기서 끝내기 전에 여전히 3과 4를 수행해야합니다. 3 단계는 아무 작업도 수행하지 않지만 빈 큐 tmp에서 항목을 제거하려고하므로 4 단계에서 오류가 발생합니다. 나는 그것이 도움이되기를 바랍니다

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 큐에 저장합니다. 모든 요소에 대해이 작업을 수행합니다.