Queue.java

Go to the documentation of this file.

package aud;
 
import aud.adt.AbstractQueue;
import java.util.NoSuchElementException;
 
//@<queue:class
public class Queue<T> extends AbstractQueue<T> {
 
  T[] data_;
  int head_ = 0;
  int tail_ = 0;
  //@>queue:class
 
  static final int DEFAULT_SIZE = 16;
 
  public Queue() {
    this(DEFAULT_SIZE);
  }
  @SuppressWarnings("unchecked")
  //@<queue:ctor
  public Queue(int capacity) {
    data_=(T[]) new Object[capacity];
    head_=tail_=0;
  }
  //@>queue:ctor
 
  @Override
  //@<queue:empty
  public boolean is_empty() {
    return head_==tail_;
  }
  //@>queue:empty
 
  @Override
  //@<queue:front
  public T front() {
    if (is_empty())
      throw new NoSuchElementException();
    return data_[head_];
  }
  //@>queue:front
 
  //@<queue:dequeue
  @Override public T dequeue() {
    if (is_empty())
      throw new NoSuchElementException();
    T obj=data_[head_];
    data_[head_]=null; // "free" entry (for GC)
    head_=(head_+1)%data_.length;
    return obj;
  }
  //@>queue:dequeue
 
  @Override
  //@<queue:enqueue1
  public void enqueue(T x) {
    int newtail=(tail_+1)%data_.length;
 
    if (newtail!=head_) {
      // no "overrun" we just advance an index.
      data_[tail_]=x;
      tail_=newtail;
    }
    else {
      //@>queue:enqueue1
      //System.err.println("enlarge buffer of size "+data_.length);
 
      // detected "overrun": the new head "hits" tail --
      // This means the alloacted buffer data is too small!
 
      // get larger buffer q
      Queue<T> q=new Queue<T>(data_.length*2);
 
      // copy data into q
      while (!is_empty())
        q.enqueue(dequeue());
      q.enqueue(x);
 
      // "steal" state of temporary object q
      data_=q.data_;
      head_=q.head_;
      tail_=q.tail_;
      assert(head_==0 && tail_<data_.length);
    }
  }
 
  @Override
  public String toString() {
    if (is_empty())
      return "<";
 
    String s="";
 
    int t=(tail_+data_.length-1)%data_.length;
    for (;;) {
      s=data_[t]+"<"+s;
      if (t==head_)
        break;
      t=(t+data_.length-1)%data_.length;
    }
    return s;
  }
}