実装キュー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; 
    } 
} 

私は、3つの基本的な機能をサポート配列を使用して動的にサイズ変更可能なキューを実装しようとしています：

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

を

制約は、キューのshou ldは常に25-100％の範囲内で塗りつぶされます。したがって、キューがいっぱいになると配列のサイズを2倍に変更し、キューの要素数が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ではなく、また

頭がテールより大きくなく、また

は、配列の長さがゼロである

• ：ので、あなたは「アンダーフロー」を上げていません。

キュー内のアイテムの数は、ゼロであるtail - headです。しかし、あなたはそれを確認しません。代わりにhead > tailにチェックします。キュー内の項目の数が負の場合にのみ失敗します。

代わりにhead >= tailをテストして修正できます。