SHARE
TWEET

Untitled

a guest Mar 11th, 2011 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. The given program, shown below, implements a circular-array queue. A queue is a British term for a line of people waiting to be served. A queue can also refer to any line of items where the item at the front of the queue is served next, and new items are added at the rear of the queue. Information-transmission systems, like the Internet, have lots of queues, where messages in transit are temporarily stalled at some intermediate system node, waiting to get into the next available time slot on the next leg of their journey. A queue’s length is the total number of people or items currently waiting. When the next item is served, that shortens the queue by one. When another person arrives, that lengthens the queue by one. A queue’s capacity is the maximum number of items that can fit in the line at one time. If a queue is full, its length equals its capacity, and all new arrivals are rejected.
  3.  
  4. The simplest way to implement a queue is with an array and two pointers, a front pointer, which contains the index of the element at the front of the queue, and a rear pointer, which contains the index of the element that is one position past the rear of the queue. When the server calls “next,” the front person gets service, and then the front pointer increments. Each new arrival increments the rear pointer. As time passes, both pointers move to higher values. Does this mean that the array’s length must keep increasing forever? No. Whenever either pointer increments to a value equal to the array’s length (thereby making it one greater than the array’s maximum index), you reassign the pointer to index 0. This effectively connects the end of the array to its beginning and makes it circular.
  5.  
  6. The following CircularQueue class is functionally correct, but inelegant in the three places marked “inelegant.” In this project, you are to (a) improve the inelegant code, and (b) implement a driver class that fully tests your CircularQueue class.
  7.  
  8. In part a, you should provide a new CircularQueue class where the original CircularQueue class’s conditional operators, embedded assignments, and embedded increment operators are replaced within the isFull, remove, and showQueue methods. Hints: You should replace isFull’s code with more compact code. You should replace remove’s code and showQueue’s code with lengthier, but more understandable code.
  9.  
  10. In part b, you should provide a complete CircularQueueDriver class that fully tests the functionality of your CircularQueue class. Your CircularQueueDriver class should:
  11. •     Instantiate a 3-element CircularQueue.
  12. •     Use a loop to add strings to the queue until the add method returns false (which indicates a full queue).
  13. •     Call showQueue.
  14. •     Use a loop to remove strings from the queue until the remove method returns null (which indicates an empty queue). As you remove each string from the queue, print the removed string.
  15.  
  16.  
  17.  
  18. /*************************************************************
  19. * CircularQueue.java
  20. * John Dean
  21. *
  22. * This class implements a queue with a circular array.
  23. *************************************************************/
  24.  
  25. public class CircularQueue
  26. {
  27.   private String[] queue; // array that implements a circular queue
  28.   private int length = 0; // number of filled elements
  29.   private int capacity;   // size of array
  30.   private int front = 0;  // index of first item in queue
  31.   private int rear = 0;   // one past the index of the last item
  32.  
  33.   //**********************************************************
  34.  
  35.   // Instantiate the queue's array with the given capacity.
  36.  
  37.   public CircularQueue(int capacity)
  38.   {
  39.     queue = new String[capacity];
  40.     this.capacity = capacity;
  41.   } // end constructor
  42.  
  43.   //**********************************************************
  44.  
  45.   public boolean isEmpty()
  46.   {
  47.     return length == 0;
  48.   } // end isEmpty
  49.  
  50.   //**********************************************************
  51.  
  52.   public boolean isFull()
  53.   {
  54.     return length==capacity ? true : false;
  55.   } // end isFull
  56.  
  57.   //**********************************************************
  58.  
  59.   public int length()
  60.   {
  61.     return length;
  62.   } // end length
  63.  
  64.   //**********************************************************
  65.  
  66.   // Add a value to the rear of the queue by using the rear's
  67.   // current position and then incrementing rear.
  68.  
  69.   public boolean add(String name)
  70.   {
  71.     if (isFull())
  72.     {
  73.       return false;
  74.     }
  75.     else
  76.     {
  77.       queue[rear++] = name;
  78.       rear %= capacity;     // if rear gets too big, assign it to 0
  79.       length++;
  80.       return true;
  81.     }
  82.   } // end add
  83.  
  84.   //**********************************************************
  85.  
  86.   // Remove the value at the front of the queue and then increment
  87.   // front.
  88.  
  89.   public String remove()
  90.   {
  91.     if (isEmpty())
  92.     {
  93.       return null;
  94.     }
  95.     else
  96.     {
  97.       length--;
  98.       return queue[(front = ++front % capacity) == 0 ?
  99.         capacity-1 : front-1];
  100.     }
  101.   } // end remove
  102.  
  103.   //**********************************************************
  104.  
  105.   // Display the queue's contents in front-to-rear order.
  106.  
  107.   public void showQueue()
  108.   {
  109.     int current; // used for walking through the queue
  110.    
  111.     current = front;
  112.     if (!isEmpty())
  113.     {
  114.       do
  115.       {
  116.         System.out.println(queue[current]);
  117.       } while ((current = ++current % capacity) != rear);
  118.     }
  119.   } // end showQueue
  120. } // end CircularQueue class
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top