Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Assignment # 5 - Radix Sorting Background: The purpose of this assignment is to get familiar with the deque ( double - ended queue )
Assignment # Radix Sorting
Background:
The purpose of this assignment is to get familiar with the deque doubleended queue nodebased structure along with generic data type. In this assignment, you will involve constructing Java functions that use linked nodes and head and tail references to operate the elements in the list. Moreover, to leverage the usefulness of the structure you designed, we use the deque to apply the radix sort to a list of integer numbers read from a input file.
A realworld application of the deque is to store the history of a web browser. The recently visited URLs are added to the front of the deque, and the URL at the back of the deque is removed after some specified number of insertions at the front. Another common application of the deque is to work like a list of undo operations in a software application.
Objectives:
This assignment will assess your mastery of the following objectives:
To construct doubleend queue.
To understand how node references work in the linked lists.
To perform basic operations in the linked list.
To design interface, abstract class, and concrete classes. optional
To design condition for the comparable class. optional
Rules and Explanations:
Part :
The original queue has a reference to the first element head of the queue. In this assignment, you are ask to construct a deque a doubleended queue that has an additional reference to the last element tail of the queue. Anyway, you are NOT allowed to use the tail reference in the LinkedDeque class. Deque is an ordered collection of items similar to the queue. It has two ends, a front and rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. Deque allows adding new items at either the front or the rear. Furthermore, we can remove existing items from either end. In an insight, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
We will develop a singlylinked implementation of a doubleended queue. There is an interface Deque that extends from the Queue interface with a new interface called Deque. The class LinkedQueue implements all prototypes in the interface Queue. You are not allowed to modify Queue, Deque, and LinkedQueue. You will develop a new class called LinkedDeque, and this class will extend the provided LinkedQueue class and implements all prototypes in the Deque interface. Please do not add any extra fields or methods. Write the code in the body of each required methods as following:
Method Description
public void addRearType data The method adds element to the back
public void addFrontType data The method adds element to the front
public Type removeRear The method removes element from the back and return the removed element.
public Type removeFront The method removes element from the front and return the removed element.
public Type peekRear The method examines element from the back.
public Type peekFront The method examines element from the front.
In this assignment, you have to write JUnit tests for all public LinkedDeque operations including those inherited from LinkedQueue Your tests should provide complete code coverage including the toString method Think carefully about border cases and exceptional cases as you develop your code and your tests. You will need to take a screenshot that shows all test cases of LinkedDeque passed. Your unit tests should NOT produce any console output. Here is a list of examples of test cases you must have.
Method Description
public void testLinkedDeque Do nothing but check the size and if the queue is empty.
public void testAddRear Add one element to the back and check size and queue in string format.
public void testAddRear Add two elements to the back and check size and queue in string format.
public void testAddFront Add one element to the front and check size and queue in string format.
public void testAddFront Add two elements to the front and check size and queue in string format.
public void testAddFrontRear Add three elements to the front andor back then check size and queue in string format.
public void testAddFrontRear Add three elements to the front andor back then check size and queue in string format.
public void testRemoveRear Remove the element from the back once then check size and queue in string format.
public void testRemoveRear Remove the element from the back twice then check size and queue in string format.
public void testRemoveFront Remove the element from the front once then check size and queue in string format.
public void testRemoveFront Remove the element from the front twice then check size and queue in string format.
public void testPeekRear Examine the element from the back then check size and queue in string format.
public void testPeekFront Examine the element from the
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started