Assignment: Data Structures and Algorithms

1. Create a class, MyDeque, to implement a circular deque. The class is based on the discussion of the deques. It should include the following methods:

insertFront()
insertRear()
removeFront()
removeRear()
peekFront()
peekRear()
isEmpty()
isFull()
toString()

• You may create the class by updating the existing class Queue.java in page 138 of the textbook.

• For practicing purpose, assume that the elements in the deque are stock items. Each item consists of two data:

- Item# (String)
- Item price (double)

Create a class called Item. Each element in the deque is an object of the Item class. The class should include set/get methods and toString() method.

• The deque is a circular queue which needs to handle wrap-around.

• Refer the given methods in the example class (Queue.java in page 138) to define the API of the class. It means that you should define the signature (method header) of the constructor(s) and each method before coding. Any ‘remove' method should return the removed item. You may safely assume that the application program tests the deque for full and empty before insert and remove (It is you to write the application class.)

2. The toString() in MyDeque should always display the data stored in the deque in the sequence from ‘front' to ‘rear'.

3. Since the deque is a circular queue, You may have to handle wrap-around not only in insert and remove, but also in ‘peek',

4. Write an application class to test all methods defined in MyDeque class. The application should allow the user to provide the length of the deque and operate on the queue as many times as he/she wants till ‘Quit'.

The selections in the menu for users are:

1) Insert to front
2) Insert to rear
3) Remove from front
4) Remove from rear
5) Peek front
6) Peek rear
7) Display queue (front -> rear)
8) Quit

[Note: 1. For an insertion operation, you have to prompt the user to type in the item# and the price. Create an object of the Item and then pass the object as the argument to the insertion method. Don't pass the item# and the price to insert() and create the Item object inside of insert().

2. Each insert or remove is for a single item. ]

You should test the functions as thoroughly as you can. For the example of a deque with size 5, one of the tests could be:

a) Insert 4 elements to rear (one by one)

a) Remove 2 elements from front (...)
b) Insert 3 elements to rear
c) Remove 3 elements from rear
d) Insert 3 elements to front

Display the contents in the deque frequently during the test to check the correctness of the functions.

5. Write a program to implement a stack class by using the Deque class you implemented. This implementation uses a technique called Delegation. See Note below. It should include the following methods:

push(), pop(), peek(), isEmpty(), isFull() and toString()

The element type is Item.

To avoid the name conflict with the Stack class defined in Java library, please pick any name other than Stack for your class.

[Note: Implementing the delegation relationship: Define a deque object in the stack class, and then use any existing methods of the deque to implement the functions of the stack. Don't use the ‘inheritance' relationship.]

6. No need to write the app class for the stack. You may put a main() inside of the stack class to do simple tests.

7. For all methods and applications you write, give comments (top doc before each method, not only // comments by the side of the sentences) to explain your strategy.

8. Make all screen-output meaningful to the user.

9. Submission:

• Item class
• MyDeque class
• MyDequeApp class
• The stack class.