th CSC205-Program #4-Phase I Duc Monday, February 25 Deque Implementation with Circular Array 2019 ata Structure eque" (pronounced 'deck) is a double-ended queue. It supports entry and exit on cither end of the r insertions or deletions. It is similar to a line at a bank teller window. Regular customers enter at the end of the line, but special customers get escorted to the front of the line. Normally, customers exit irom tront of the line when they are served by the teller, but customers may choose to leave from the end ol the imie without being served if the trom the middle of the line, or jump ahead to join their spouse or friend.) y are in a hurry. (It is like a line at a very fussy bank, because customers cannot leave For this exercise, implement a deque of Strings. Formally, support the following operations: constructor- initialize an empty deque. insertOnFront- insert a given String on the front of the deque deletelFromFront- return (and deletc) the String extracted from the front of the deque. insertOnBack-insert a given String on the back of the deque. delete FromBack-return (and delete) the String extracted from the back of the deque. mpty-return true if the deque is empty, and false otherwise. toString - return a String summarizing the entire contents of the deque (from front to back) toStore - return a String summarizing the entire contents of deque storage (from array index 0 to length-1) Application: rite a simple test program to exercise all these operations on two instances of Deques, Construct an empty nstance of each of these, then allow the user to repeatedly perform selected operations on either of the two, in any order, until they choose to quit. For each action, let the user select which Deque to manipulate, then allow them to choose from a menu of the available operations. Prompt for any necessary input, and display results of each operation (or a simple message acknowledging completion if there is no result) Implementation: Use a single array of Strings to store the Deque. Give it an initial size of 5 (admittcdly small, for convenient testing), but allow it to grow, if necessary. If the user asks to insert an element in a Deque that is full, allocate an array twice the current size, copy the contents of the old array to the new one (you will actually be copying references), and carry out the requested insertion. If the user requests a deletion from an empty deque, just ignore the request without comment. (The isEmpty method is available to enable the user to detect that exceptional case.) Use the 'circular' array implementation strategy discussed in class (with queues). All wrap-around figuratively connecting the two ends of the array) to store the deque's contents insertion and deletion operations. Do not attempt to maintain two distinct regions within the arra processing of front and back operations. The implementation must be efficient. ocate a single array (with and respond to all Create one class called "Program4" for the application (the main program), and a separate, inde class (NOT inside the Program4 class) Follow the guidelines listed in your handout on software engineering standards. Start early and get the DoN gram working one piece at a time. 20 CSC205-Program #4-Phase II Due Monday, March4 Deque Implementation with 'Circular' Array and Queue and Stack Implementation with Deque Data Structure A "deque" (pronounced 'deck) is a double-ended queue. It supports entry and exit on either end of line, but no other insertions or deletions. It is similar to a line at a bank teller window. enter at the end of the line, but special customers get escorted to the front of the line. customers exit from the front of the line when they are served by the teller, but customers may leave from the end of the line without being served if they are in a hurry Regular customers Normally choose to For this exercise, implement a deque of Objects. Formally, support the following operations: constructor - initialize an empty deque. insertOnFront - insert a given Object on the front of the deque. deleteFromFront - return the Object extracted from the front of the deque. insertOnBack - insert a given Object on the back of the deque deleteFromBack - return the Object extracted from the back of the deque toString return a String summarizing the entire contents of the deque (from front to back) toStore - return a String summarizing the entire contents of deque storage (from array index 0 to length-1). We have already described Stacks and Queues in class. Implement these two classes also, with the following operations Implement a Stack of Objects supporting the following operations constructor - initialize an empty stack. push - insert a given Object on the top of the stack. pop - return the Object extracted from the top of the stack. isEmpty - return true if the stack is empty, and false otherwise. toString - return a String summarizing the entire contents of the stack (from top to bottom) Implement a Queue of Objects supporting the following operations: constructor - initialize an empty queue. insert - insert a given Object on the rear of the queue delete - return the Object extracted from the front of the queue. isEmpty - return true if the deque is empty, and false otherwise. toString - return a String summarizing the entire contents of the queue (from front to rear). lication Write a simple test program to exercise all these operations on the following: a Deque of Customers, a Queue of Strings, and a Stack of integers. Represent each customer by name and integer identification allow the user to repeatedly perform number. selected operations on any of them, in any order, until they choose to quit select which object to manipulate, then allow them to choose from a menu of the available operations Construct an empty instance of each of these three, then . For each action, let the user CSC205-Program #4-Phase III( Final) Due Monday, March 4 Deque/Queue Application Interfac Prepare a new menu that includes the following oplions (1) Test the Tools (2) Play "Top Trump (3) Quit Repeat this menu until the user decides to quit. tio he Tools Give the user the menu from Phase II of the assignment and allow them to do the same operations. For Option 2: Play "Top Trump" It is a game like War. Here are the rules, adapted from Wikipedia.. "All the cards are dealt among the players. There must be at least two players, and at least one card for each player. The starting player (normally the player sitting on the ealer's left) selects a category from his or her topmost card and reads out its value. Each other player then reads out the value of the same category from their cards. The best value wins the "trick", and the winner takes all the cards of the trick and places them at the bottom of his or her pile. That player then looks at their new topmost card, and chooses the category for the next round. In the event of a draw, the cards are placed in the center and a new category is chosen from the next card by the same person as in the previous round. The winner of that round obtains all of the cards in the center as well as the top card from each player Players are eliminated when they lose their last card, and the winner is the player who obtains the whole pack." The difference between War and Top Trump is that each card has multiple properties, and a value for each property. (All cards in one deck have the same set of properties.) In Top Trump, when the current player turns over a card for combat, that player gets to choose which property is the basis for combat, after seeing the card. Then the other players turn over their top cards and use the same property for comparison (note: they don't get a choice). The card with the highest value for the chosen property wins that combat. For this exercise, create a two-player game, with one hand for the user and the other operated by the computer. Let the user start, and then follow the rules of the game. If it is the user's turn, allow the user to select which property to ask for. For a computer-driven player's turn, make the choiceat random. (Creating a more sophisticated opponent is an optional extension to the assignment.) Display the result after each play, and then wait for the user to press enter to continue so that the user can follow the game play. Also, to allow the user to keep track of the game status, before each play, display the number of cards held by each player