Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Oct 9th, 2013  |  syntax: None  |  size: 6.46 KB  |  views: 42  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package prog06;
  2.  
  3. import java.util.*;
  4.  
  5. /**
  6.  * Implements the Queue interface using a circular array.
  7.  **/
  8. public class ArrayQueue<E> extends AbstractQueue<E>
  9.         implements Queue<E> {
  10.  
  11.     // Data Fields
  12.     /** Index of the front of the queue. */
  13.     private int front;
  14.     /** Index of the rear of the queue. */
  15.     private int rear;
  16.     /** Current size of the queue. */
  17.     private int size;
  18.     /** Default capacity of the queue. */
  19.     private static final int DEFAULT_CAPACITY = 10;
  20.     /** Array to hold the items. */
  21.     private E[] theItems;
  22.  
  23.     // Constructors
  24.     /**
  25.      * Construct a queue with the default initial capacity.
  26.      */
  27.     public ArrayQueue () {
  28.         this(DEFAULT_CAPACITY);
  29.     }
  30.  
  31.     /**
  32.      * Construct a queue with the specified initial capacity.
  33.      * @param initCapacity The initial capacity
  34.      */
  35.     @SuppressWarnings("unchecked")
  36.     public ArrayQueue (int initCapacity) {
  37.         theItems = (E[]) new Object[initCapacity];
  38.         front = 0;
  39.         rear = theItems.length - 1;
  40.         size = 0;
  41.     }
  42.  
  43.     // Public Methods
  44.     /**
  45.      * Inserts an item at the rear of the queue.
  46.      * @post item is added to the rear of the queue.
  47.      * @param item The element to add
  48.      * @return true (always successful)
  49.      */
  50.     @Override
  51.     public boolean offer (E item) {
  52.         if (size == theItems.length)
  53.             reallocate();
  54.         size++;
  55.         rear = (rear + 1) % theItems.length;
  56.         theItems[rear] = item;
  57.         return true;
  58.     }
  59.  
  60.     /**
  61.      * Returns the item at the front of the queue without removing it.
  62.      * @return The item at the front of the queue if successful;
  63.      * return null if the queue is empty
  64.      */
  65.     @Override
  66.     public E peek () {
  67.         if (size == 0)
  68.             return null;
  69.         return theItems[front];
  70.     }
  71.  
  72.     /**
  73.      * Removes the entry at the front of the queue and returns it
  74.      * if the queue is not empty.
  75.      * @post front references item that was second in the queue.
  76.      * @return The item removed if successful or null if not
  77.      */
  78.     @Override
  79.     public E poll() {
  80.       // EXERCISE 3
  81.         if(size == 0)
  82.                 return null;
  83.         else
  84.         {
  85.                 size--;
  86.                 E frontEntry = theItems[front];
  87.                 front = (front+1)%theItems.length;
  88.                 return frontEntry;
  89.         }      
  90.     }
  91.    
  92.    
  93. /**
  94.  * Return the size of the queue
  95.  * @return The number of items in the queue
  96.  */
  97.     @Override
  98.     public int size () {
  99.       return size;
  100.     }
  101.     /**
  102.      * Returns an iterator to the elements in the queue
  103.      * @return an iterator to the elements in the queue
  104.      */
  105.     @Override
  106.     public Iterator<E> iterator () {
  107.       return new Iter();
  108.     }
  109.    
  110.     // Private Methods
  111.     /**
  112.      * Double the capacity and reallocate the items.
  113.      * @pre The array is filled to capacity.
  114.      * @post The capacity is doubled and the first half of the
  115.      *       expanded array is filled with items.
  116.      */
  117.     @SuppressWarnings("unchecked")
  118.     private void reallocate () {
  119.         int newCapacity = 2 * theItems.length;
  120.         E[] newItems = (E[]) new Object[newCapacity];
  121.         if(front > rear)
  122.         {
  123.                 System.arraycopy(theItems, front, newItems, 0, theItems.length-front);
  124.                 System.arraycopy(theItems, 0, newItems, theItems.length-front, size-theItems.length+front);
  125.         }
  126.         else
  127.         {
  128.                 System.arraycopy(theItems, front, newItems, 0, size);
  129.         }
  130.         front = 0;
  131.         rear = size - 1;
  132.         theItems = newItems;
  133.     }
  134.  
  135.     private boolean labSolution = false;
  136.  
  137.  
  138.     /** Inner class to implement the Iterator<E> interface. */
  139.     private class Iter implements Iterator<E> {
  140.         // Data Fields
  141.  
  142.         // Index of next element */
  143.         private int index;
  144.        
  145.         // Count of elements accessed so far */
  146.         private int count = 0;
  147.  
  148.  
  149.         // Methods
  150.         // Constructor
  151.         /**
  152.          * Initializes the Iter object to reference the
  153.          * first queue element.
  154.          */
  155.         public Iter ()
  156.         {
  157.                 if (labSolution) {
  158.                 index = front;
  159.               }
  160.               else
  161.               {
  162.                   if(size == 0)
  163.                           index = -1;
  164.                   else
  165.                           index = front;
  166.               }
  167.         }
  168.  
  169.         /**
  170.          * Returns true if there are more elements in the queue to access.
  171.          * @return true if there are more elements in the queue to access.
  172.          */
  173.         @Override
  174.         public boolean hasNext () {
  175.             if (labSolution)
  176.               return count < size;
  177.             else {
  178.               // EXERCISE
  179.               return !(index == -1);
  180.             }
  181.           }
  182.         /**
  183.          * Returns the next element in the queue.
  184.          * @pre index references the next element to access.
  185.          * @post index and count are incremented.
  186.          * @return The element with subscript index
  187.          */
  188.         @Override
  189.         public E next () {
  190.             if (!hasNext()) {
  191.                 throw new NoSuchElementException();
  192.             }
  193.             E returnValue = theItems[index];
  194.             if (labSolution) {
  195.               index = (index + 1) % theItems.length;
  196.               count++;
  197.             }
  198.             else {
  199.               // EXERCISE
  200.                 if(index == rear)
  201.                         index = -1;
  202.                 else
  203.                 index++;
  204.             }
  205.             return returnValue;
  206.         }
  207.  
  208.         /**
  209.          * Remove the item accessed by the Iter object -- not implemented.
  210.          * @throws UnsupportedOperationException when called
  211.          */
  212.         @Override
  213.         public void remove () {
  214.             throw new UnsupportedOperationException();
  215.         }
  216.     }
  217. }
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225. package prog06;
  226. import java.util.*;
  227.  
  228. public class Main {
  229.   public static void main (String[] args) {
  230.     System.out.println("ArrayQueue");
  231.     test(new ArrayQueue<Integer>());
  232.    // System.out.println("LinkedQueue");
  233.    // test(new LinkedQueue<Integer>());
  234.  
  235.    // WordGame game = new WordGame();
  236.   }
  237.  
  238.   static void test (Queue<Integer> queue) {
  239.     for (int i = 0; i < 5; i++)
  240.       queue.offer(i);
  241.     System.out.println(queue);
  242.     for (int i = 5; i < 15; i++) {
  243.       System.out.println(queue.poll());
  244.       queue.offer(i);
  245.       System.out.println(queue);
  246.     }
  247.     for (int i = 15; i < 25; i++)
  248.       queue.offer(i);
  249.     System.out.println(queue);
  250.   }
  251. }
clone this paste RAW Paste Data