구현 큐 API 사용하여 크기 조정 배열

Question

package com.queueapi; 

/** 
* Created by Dhaval on 6/15/2016. 
*/ 

public class DynamicArrayQueue { 
    private String[] s; 
    private int head = -1; 
    private int tail = -1; 

    public DynamicArrayQueue() { 
    } 

    public boolean isEmpty() { 
     return head == -1 || head > tail || s.length == 0; 
    } 

    public void enqueue(String item) { 
     if (isEmpty()) { 
      head = 0; 
      tail = 0; 
      s = new String[1]; 
     } 

     if (tail - head == s.length) { 
      resize(s.length * 2); 
     } 

     s[tail++] = item; 
    } 

    public String dequeue() throws QueueUnderFlowException { 
     if (isEmpty()) { 
      throw new QueueUnderFlowException(); 
     } 

     String item = s[head++]; 
     if (tail - head == s.length/4) { 
      resize(s.length/2); 
     } 
     return item; 
    } 

    public void resize(int capacity) { 
     String[] copy = new String[capacity]; 
     for (int i = head; i < tail; i++) { 
      copy[i - head] = s[i]; 
     } 
     s = copy; 
     tail = tail - head; 
     head = 0; 
    } 
} 

나는 세 가지 기본 기능을 지원 배열을 사용하여 동적으로 크기 조정 큐 구현하기 위해 노력하고 있습니다 :

1. isEmpty()
2. Enqueue()
3. Dequeue()

을

제약 조건은 다음과 같습니다. ld는 항상 25-100 % 범위 내에서 채워 지므로 큐가 가득 찼을 때 그 크기를 두 배로 배열의 크기를 조정하고 큐의 요소 수가 size/4와 같은 경우 크기를 size/2로 줄입니다.

이 대기열은 입력을 받아들이는 테스터와 함께 사용됩니다. 1 - 2 - 3 여기서 "-"가 발생하면 dequue() 작업이 수행되고 그렇지 않으면 enqueue()가 수행됩니다.

1 2 3 - - - - 코드 입력에 실패했습니다. 제가 잘못 가고있는 부분에 대해 어느 정도 통찰력을주십시오. 문제의 경우

테스터 클라이언트에게

package com.queueapi; 
import edu.princeton.cs.algs4.StdIn; 
import edu.princeton.cs.algs4.StdOut; 

public class QueueTester { 

    public static void main(String[] args) throws QueueUnderFlowException { 

     DynamicArrayQueue queue = new DynamicArrayQueue(); 
     while(!StdIn.isEmpty()){ 

      String s = StdIn.readString(); 
      if(s.equals("-")){ 
       StdOut.print(queue.dequeue()); 
      } 
      else{ 
       queue.enqueue(s); 
      } 
     } 
    } 
} 

Answer 1

을, 멤버 값은 다음과 같습니다이에서

head tail s 
-1 -1 [] 
    Enque "1" 
0 1 ["1"] 
    Enque "2" 
0 2 ["1" "2"] 
    Enque "3" 
0 3 ["1", "2", "3", null] 
    Deque -> "1" 
1 3 ["1", "2", "3", null] 
    Deque -> "1" 
0 1 ["3", null] 
    Deque -> "1" 
0 0 [null] 
    Deque -> null 

을 꽤 분명해진다. 당신은 "언더 플로"때문에 제기되지 않습니다

• 머리 것은 -1 아니며,
• 머리 꼬리보다 크지 않으며,
• 배열의 길이가 0입니다.

대기열에있는 항목의 수는 tail - head이며 0입니다. 그러나 당신은 그것을 확인하지 않습니다. 대신 head > tail을 확인하십시오. 대기열의 항목 수가 음수이면 실패합니다.

대신 head >= tail을 테스트하여 문제를 해결할 수 있습니다.