// Arup Guha
// June 19, 2002
// Queue class: This class implements a queue using an array. An approach
//              slightly different than the text is taken here. So please
//              read both.

import java.util.Random;

public class Queue {

  private int[] items; // Stores the elements of the queue
  private int front; // Stores the array index that front is stored in.
  private int size; // Stores number of elements in the queue.

  // Default constructor initializes an empty queue.
  public Queue() {
    items = new int[10];
    front = 0;
    size = 0;
  }

  // Method for testing only. Prints the entire contents of items.
  public void printA() {
    System.out.println();
    for (int i=0; i<items.length; i++)
      System.out.print(items[i]+" ");
    System.out.println();
  }

  // Enqueues the integer n into the queue.
  public void Enqueue(int n) {
    
    // Takes care of the case where the array is full.
    if (size == items.length) {

      printA(); // Checking contents of items for debugging.

      int i,j;
      int[] temp; // Expanded temporary array to store queue elements.
      temp = new int[2*items.length];

      // Copy all the elements from the queue into the temporary array,
      // resetting the front of the queue to be 0.
      for (i=front,j=0; j < size; j++,i=(i+1)%size)
        temp[j] = items[i];

      // Add in the new element.
      temp[size] = n;

      // Make other necessary adjustments.
      front = 0;
      items = temp;

      printA(); // Checking new contents for debugging.
    }
    // Take care of the normal case.
    else 
      items[(front+size)%items.length] = n;
    
    // Increment size since an element was added.
    size++;
  }

  // Dequeues the front integer from the queue.
  public int Dequeue() {
    
    // Take care of the normal non-empty queue case.
    if (size > 0) {

      int val = items[front]; // Store item to return.

      // Make necessary adjustments to instance variables.
      front=(front+1)%items.length;
      size--;

      return val; // Return front element.
    }
    return -1; // Signals an empty queue.
  }

  // Returns true if the queue is empty, false otherwise.
  public boolean Empty() {
    return (size == 0);
  }

  // Returns the front element w/o dequeuing it.
  public int Front() {
 
    // Return the appropriate value.
    if (size > 0) 
      return items[front];
    return -1; // Signals empty queue.
  }

  public static void main(String[] args) {

    Queue q = new Queue(); // Create Queue object.
    Random r = new Random(); // Used for testing.

    // Do 20 random insert and delete operations.
    for (int i=1; i<21; i++) {

      int ran = Math.abs(r.nextInt()%4);
      // An enqueue will be performed approx. 6/7 of the time.
      if (ran > 0) {
        q.Enqueue(i);
        System.out.print("add "+i+" ");
      }
      // A dequeue will be performed approx. 1/7 of the time.
      else {
        if (!q.Empty())
          System.out.print("del "+q.Dequeue()+" ");
      }

      if (i%10 == 0)
        System.out.println();
     }

  }
}