Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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.
- 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.
- 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.
- 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.
- In part b, you should provide a complete CircularQueueDriver class that fully tests the functionality of your CircularQueue class. Your CircularQueueDriver class should:
- • Instantiate a 3-element CircularQueue.
- • Use a loop to add strings to the queue until the add method returns false (which indicates a full queue).
- • Call showQueue.
- • 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.
- /*************************************************************
- * CircularQueue.java
- * John Dean
- *
- * This class implements a queue with a circular array.
- *************************************************************/
- public class CircularQueue
- {
- private String[] queue; // array that implements a circular queue
- private int length = 0; // number of filled elements
- private int capacity; // size of array
- private int front = 0; // index of first item in queue
- private int rear = 0; // one past the index of the last item
- //**********************************************************
- // Instantiate the queue's array with the given capacity.
- public CircularQueue(int capacity)
- {
- queue = new String[capacity];
- this.capacity = capacity;
- } // end constructor
- //**********************************************************
- public boolean isEmpty()
- {
- return length == 0;
- } // end isEmpty
- //**********************************************************
- public boolean isFull()
- {
- return length==capacity ? true : false;
- } // end isFull
- //**********************************************************
- public int length()
- {
- return length;
- } // end length
- //**********************************************************
- // Add a value to the rear of the queue by using the rear's
- // current position and then incrementing rear.
- public boolean add(String name)
- {
- if (isFull())
- {
- return false;
- }
- else
- {
- queue[rear++] = name;
- rear %= capacity; // if rear gets too big, assign it to 0
- length++;
- return true;
- }
- } // end add
- //**********************************************************
- // Remove the value at the front of the queue and then increment
- // front.
- public String remove()
- {
- if (isEmpty())
- {
- return null;
- }
- else
- {
- length--;
- return queue[(front = ++front % capacity) == 0 ?
- capacity-1 : front-1];
- }
- } // end remove
- //**********************************************************
- // Display the queue's contents in front-to-rear order.
- public void showQueue()
- {
- int current; // used for walking through the queue
- current = front;
- if (!isEmpty())
- {
- do
- {
- System.out.println(queue[current]);
- } while ((current = ++current % capacity) != rear);
- }
- } // end showQueue
- } // end CircularQueue class
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement