COMPUTER SCIENCE

PROJECT4CSC330.doc

Home >Computer Science homework help >COMPUTER SCIENCE

(PLEASE FOLLOW THE INSTRUCTION OF THE PROFFESSOR AND USE THE MAIN METHOD GIVEN BY PROFFESOR AND TRY TO GIVE THE SAME OUTPUT AS PROFFESSSOR)

Writing programs that solve the Programming Projects helps to solidify your understanding

of the material and demonstrates how the chapter’s concepts are applied.

(As noted in the Introduction, qualified instructors may obtain completed solutions

to the Programming Projects on the publisher’s Web site.)

1) 4.1 Write a method for the Queue class in the queue.java program (Listing 4.4) that

displays the contents of the queue. Note that this does not mean simply

displaying the contents of the underlying array. You should show the queue

contents from the first item inserted to the last, without indicating to the

viewer whether the sequence is broken by wrapping around the end of the

array. Be careful that one item and no items display properly, no matter where

front and rear are.

2) 4.2 Create a Deque class based on the discussion of deques (double-ended queues) in

this chapter. It should include insertLeft(), insertRight(), removeLeft(),

removeRight(), isEmpty(), and isFull() methods. It will need to support wraparound

at the end of the array, as queues do.

3) 4.3 Write a program that implements a stack class that is based on the Deque class

in Programming Project 4.2. This stack class should have the same methods

and capabilities as the StackX class in the stack.java program (Listing 4.1).

4) 4.4 The priority queue shown in Listing 4.6 features fast removal of the high-priority

item but slow insertion of new items. Write a program with a revised

PriorityQ class that has fast O(1) insertion time but slower removal of the highpriority

item. Include a method that displays the contents of the priority

queue, as suggested in Programming Project

5) 4.5 Queues are often used to simulate the flow of people, cars, airplanes, transactions,

and so on. Write a program that models checkout lines at a supermarket,

using the Queue class from the queue.java program (Listing 4.4). Several lines of

customers should be displayed; you can use the display() method of

Programming Project 4.1. You can add a new customer by pressing a key. You’ll

need to determine how the customer will decide which line to join. The checkers

will take random amounts of time to process each customer (presumably

depending on how many groceries the customer has). Once checked out, the

customer is removed from the line. For simplicity, you can simulate the passing

of time by pressing a key. Perhaps every keypress indicates the passage of one

minute. (Java, of course, has more sophisticated ways to handle time4_1

The main may look like:

public static void main(String[] args) throws IOException

{

Queue theQueue = new Queue(5); // queue holds 5 items

long value;

while(true)

{

System.out.print("Enter first letter of ");

System.out.print("show, insert, remove: ");

int choice = getChar();

switch(choice)

{

case 's':

theQueue.display();

break;

case 'i':

if( !theQueue.isFull() )

{

System.out.print("Enter value to insert: ");

value = getLong();

theQueue.insert(value);

theQueue.display();

}

else

System.out.print("*** Queue is full ***\n");

break;

case 'r':

if( !theQueue.isEmpty() )

{

value = theQueue.remove();

System.out.println("Removed " + value);

theQueue.display();

}

else

System.out.print("*** Queue is empty ***\n");

break;

default:

System.out.print("Invalid entry\n");

} // end switch

} // end while

} // end main()

The output may look like:

Enter first letter of show, insert, remove: s

Array: 0 0 0 0 0

Queue:

Enter first letter of show, insert, remove: i

Enter value to insert: 25

Array: 25 0 0 0 0

Queue: 25

Enter first letter of show, insert, remove: i

Enter value to insert: 33

Array: 25 33 0 0 0

Queue: 25 33

Enter first letter of show, insert, remove: i

Enter value to insert: 77

Array: 25 33 77 0 0

Queue: 25 33 77

Enter first letter of show, insert, remove: i

Enter value to insert: 21

Array: 25 33 77 21 0

Queue: 25 33 77 21

Enter first letter of show, insert, remove: r

Removed 25

Array: 25 33 77 21 0

Queue: 33 77 21

Enter first letter of show, insert, remove: r

Removed 33

Array: 25 33 77 21 0

Queue: 77 21

Enter first letter of show, insert, remove: i

Enter value to insert: 15

Array: 25 33 77 21 15

Queue: 77 21 15

Enter first letter of show, insert, remove: i

Enter value to insert: 88

Array: 88 33 77 21 15

Queue: 77 21 15 88

Enter first letter of show, insert, remove: i

Enter value to insert: 99

Array: 88 99 77 21 15

Queue: 77 21 15 88 99

Enter first letter of show, insert, remove: r

Removed 77

Array: 88 99 77 21 15

Queue: 21 15 88 99

4_2

The main( ) may look like:

public static void main(String[] args) throws IOException

{

Deque theDeque = new Deque(10);

while(true)

{

long value;

System.out.println("");

if( theDeque.isFull() )

System.out.println(

"*** Deque is full. No insertions. ***");

if( theDeque.isEmpty() )

System.out.println(

"*** Deque is empty. No deletions. ***");

System.out.print("Enter first letter of ");

System.out.println("insertLeft, InsertRight, ");

System.out.print("removeLeft, RemoveRight, or display: ");

int choice = getChar();

switch(choice)

{

case 'd':

theDeque.display();

break;

case 'i':

System.out.print("Enter value to insert left: ");

value = getLong();

theDeque.insertLeft(value);

break;

case 'I':

System.out.print("Enter value to insert right: ");

value = getLong();

theDeque.insertRight(value);

break;

case 'r':

value = theDeque.removeLeft();

System.out.println("Removed left: " + value);

break;

case 'R':

value = theDeque.removeRight();

System.out.println("Removed right: " + value);

break;

default:

System.out.print("Invalid entry\n");

} // end switch

} // end while

} // end main()

The output may look like:

*** Deque is empty. No deletions. ***