Section IB 4. Write Java code to define an interface for a Queue ADT (Abstract D
ID: 3716218 • Letter: S
Question
Section IB 4. Write Java code to define an interface for a Queue ADT (Abstract Data Type). For each queue operation in your interface, add a comment to your code explaining what it does. Write a Java implementation of your Queue from Part (a), using an array for its storage. The run-time performance of an algorithm may be found experimentally or theoretically (i) (a) (b) (c) Demonstrate how theoretical algorithm analysis is performed, using your code to add items to and remove items from a queue from Part (b) as an example Describe in detail how you would perform an experimental comparison of two algorithms, using the example of comparing the performance of queue removal operations when the queue is implemented as a linked list and as an array (ii) (d) Describe the Huffman Encoding algorithm, including details of any data structures it uses. Demonstrate its operation on the following text string (including spaces) cats can catch cat scansExplanation / Answer
Abstract Data Types (ADTs): Stacks and Queues Brief Discussion of Interfaces and Abstract Classes Because abstract date types tend to employ the use of interfaces, it seems beneficial to discuss them before continuing on with abstract data types. Let us consider how many ways there are to solve a particular problem with computer science. Even just consider the different method headers that are available. No normal person has the patience to sift all the different types of methods to figure out how to use them all. Maybe if there were a way to force everyone to use the exact same method headers so that if you know what one method is supposed to do, you know what all of them are supposed to do. You can think of interfaces as a way to do that. Interfaces usually just serve as code templates and are only composed of method headers and empty method bodies (abstract methods). Any class that implements an interface will be forced to override the empty methods. The typical driver is not so interested in how the car works under the hood, but just that it will act like a car. The same can be said of a general user of some class. Some of the skeleton code provided for some of the homework assignments can be considered examples of this if they were declared to be interfaces. A concept similar to an interface is an abstract class. An abstract class can be thought of a cross between an interface and a normal class, because it contains regular methods and can contain, though not necessarily, abstract methods. It is important to note that it is possible for a class to implement more than one interface, but it can only extend one class, abstract, regular or something else. Abstract classes and interfaces also cannot be instantiated
Operations on queues are analogous to operations on stacks. There is a one-to-one correspondence between them. The only dierence is that the push operation of the stack appends an item to the front of the stack (which we call the top), whereas the enqueue operation appends to the rear. Popping a queue is called dequeuing the queue. Other than its having a dierent name, dequeuing a queue is the same as popping a stack. The single dierence between stacks and queues, namely which end of the list new items are inserted, has a major consequence in terms of how the queue abstract data type behaves. See Figure 1. The queue methods are: create() - Create an empty queue. destroy() - Destroy a queue. bool empty() - Return true if the queue is empty and false if not. bool enqueue([in] item) - Append an item to the rear of the queue, returning true if successful, false if not. bool dequeue([out] item) - Remove the item from the front of the queue, and provide it to the caller, returning true if successful and false otherwise
ublic interface QueueADT
{
//---------------------------------------------
// Puts item on end of queue.
//---------------------------------------------
public void enqueue(Object item);
//---------------------------------------------
// Removes and returns object from front of queue.
//---------------------------------------------
public Object dequeue();
//---------------------------------------------
// Returns true if queue is empty.
//---------------------------------------------
public boolean isEmpty();
//---------------------------------------------
// Returns true if queue is full.
//---------------------------------------------
public boolean isFull();
//---------------------------------------------
// Returns the number of elements in the queue.
//---------------------------------------------
public int size();
}
//***********************************************************
// ArrayQueue.java
// An array-based implementation of the classic FIFO queue interface.
//***********************************************************
public class ArrayQueue implements QueueADT
{
private int DEFAULT_SIZE = 5;
private Object[] elements;
private int numElements;
private int front, back;
//---------------------------------------------
// Constructor; creates array of default size.
//---------------------------------------------
public ArrayQueue()
{
}
//---------------------------------------------
// Puts item on end of queue.
//---------------------------------------------
public void enqueue(Object item)
{
}
//---------------------------------------------
// Removes and returns object from front of queue.
//---------------------------------------------
public Object dequeue()
{
}
//---------------------------------------------
// Returns true if queue is empty.
//---------------------------------------------
public boolean isEmpty()
{
}
//---------------------------------------------
// Returns true if queue is full, but it never is.
//---------------------------------------------
public boolean isFull()
{
}
//---------------------------------------------
// Returns the number of elements in the queue.
//---------------------------------------------
public int size()
{
}
//---------------------------------------------
// Returns a string containing the elements of the queue
// from first to last
//---------------------------------------------
public String toString()
{
String result = " ";
for (int i = front, count=0; count < numElements;
i=(i+1)%elements.length,count++)
result = result + elements[i]+ " ";
return result;
}
}
//***********************************************************
// TestQueue
// A driver to test the methods of the QueueADT implementations.
//**********************************************************
public class TestQueue
{
public static void main(String[] args)
{
QueueADT q = new ArrayQueue();
System.out.println(" Enqueuing 10, 20, 30, 40, 50:");
q.enqueue("10");
q.enqueue("20");
q.enqueue("30");
q.enqueue("40");
q.enqueue("50");
System.out.println(" Dequeuing four...");
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(" Enqueuing 60, 70, 80, 90, 100:");
q.enqueue("60");
q.enqueue("70");
q.enqueue("80");
q.enqueue("90");
q.enqueue("100");
System.out.println(" Enqueuing chocolate, cake, pie, truffles:");
q.enqueue("chocolate");
q.enqueue("cake");
q.enqueue("pie");
q.enqueue("truffles");
System.out.println(" Here's the queue: " + q);
System.out.println("It contains " + q.size() + " items.");
System.out.println(" Dequeuing two...");
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(" Enqueuing cookies, profiteroles, mousse, cheesecake, ice cream:");
q.enqueue("cookies");
q.enqueue("profiteroles");
q.enqueue("mousse");
q.enqueue("cheesecake");
q.enqueue("ice cream");
System.out.println(" Here's the queue again: " + q);
System.out.println("Now it contains " + q.size() + " items.");
System.out.println(" Dequeuing everything in queue");
while (!q.isEmpty())
System.out.println(q.dequeue());
System.out.println(" Now it contains " + q.size() + " items.");
if (q.isEmpty())
System.out.println("Queue is empty!");
else
System.out.println("Queue is not empty -- why not??!!");
}
}
4(B)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.