Question

In this assignment you will be implementing two Abstract Data Types (ADT) the Queue ADT and the Stack ADT. In addition, you will be using two different implementations for each ADT:

1. Array Based

2. Linked

You will also be writing a driver to test your Queue and Stack implementations and you will be measuring the run times and memory use of each test case.

You will also be adding some functionality to the TestTimes class that you created for Homework 1.

Finally, you will be analysing and comparing the performance of the test cases on both the Array Based and the Linked implementations of both the Queue ADT and the Stack ADT.

Details

1. TestTimes Class
   You will be expanding the functionality of the TestTimes class to implement the expanded TestTimes Interface, The interface may be downloaded fromTestTimesInterface.java

2. Array Based Queue Class
   You will write the ArrayBasedQueue.java class which will implement the Queue Interface. The interface may be downloaded from QueueInterface.java.
   Please note that Queue Interface extends the Iterable Interface. See the Information On The Iterable Interface below.

3. Linked Queue Class
   You will write the LinkedQueue.java class which will implement the Queue Interface. The interface may be downloaded from QueueInterface.java.
   Please note that Queue Interface extends the Iterable Interface. See the Information On The Iterable Interface below.
   Also note that the Linked Queue Class should be a Doubly Linked Queue.

4. Array Based Stack Class
   You will write the ArrayBasedStack.java class which will implement the Stack Interface. The interface may be downloaded from StackInterface.java.
   Please note that Stack Interface extends the Iterable Interface. See the Information On The Iterable Interface below.

5. Linked Stack Class
   You will write the LinkedStack.java class which will implement the Stack Interface. The interface may be downloaded from StackInterface.java.
   Please note that Stack Interface extends the Iterable Interface. See the Information On The Iterable Interface below.
   Also note that the Linked Stack Class should be a Doubly Linked Stack.

6. Information On The Iterable Interface
   The Iterable Interface requires you to implement one method Iterator iterator(). So, all your Queue and Stack classes must implement this interface.

7. Element Iterator Class
   You will write the ElementIterator.java class which will implement the Iterator Interface.
   Please note, you only need to implement two methods from the Iterator interface: boolean hasNext() and E next()

8. Node Class
   You will write the Node.java Please see the Node Class Documentation for all the methods you will need.
   Please note that the Node Class is a node for a Doubly Linked Queue or Doubly Linked Stack.

9. Driver Class
   You will write the Driver.java class which will implement the Driver Interface. The interface may be downloaded from DriverInterface.java.
   Please note that you do not inherit from the TestTimes class. However, you do have to use the TestTimes class to measure test times and memory usages.

10. Queue Test Cases
    All the elements being enqueued and dequeued from your queues must be instances of the java.lang.String class.

    1. Create an instance of your queue that accepts java.lang.String Objects. Starting with an empty queue, use the enqueue(E e) method to add 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") to the Queue.

    2. Starting with an instance of your queue that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the Queue. Use the dequeue() method to remove all the objects from the queue, one at a time.

    3. Starting with an instance of your queue that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the Queue. Use the Iterator() method to obtain an ElementIteratorobject. Use the ElementIterator object to display the strings from the queue one String per line.

11. Stack Test Cases
    All the elements being pushed and popped from your stacks must be instances of the java.lang.String class.

    1. Create an instance of your stack that accepts java.lang.String Objects. Starting with an empty stack, use the push(E e) method to add 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") to the stack.

    2. Starting with an instance of your stack that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the stack. Use the pop() method to remove all the objects from the stack, one at a time.

    3. Starting with an instance of your stack that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the stack. Use the Iterator() method to obtain an ElementIterator object. Use the ElementIterator object to display the strings from the stack, one String per line.

12. Output From Driver Main Method
    Please note that, in addition to implementing the DriverInterface, you are also required to write your own public static main(String[] args)method in Driver.java.
    Your main() method will have to call the runTestCase() method for each of test cases listed above a total of ten times for each test case:
    For each call to the runQueueTestCase() method your main() method will a table with the following output for the Array Based Queue and the Linked Queue implementations

    
    Running test = Test Case Name

Run 1	Run 2	Run 3	Run 4	Run 5	Run 6	Run 7	Run 8	Run 9	Run 10	AverageMicro Seconds
-------	-------	-------	-------	-------	-------	-------	-------	-------	-------	-------

ArrayBasedQueue

LinkedQueue

Running test = Test Case Name

Run 1	Run 2	Run 3	Run 4	Run 5	Run 6	Run 7	Run 8	Run 9	Run 10	Average Kilo Bytes
-------	-------	-------	-------	-------	-------	-------	-------	-------	-------	-------

ArrayBasedQueue

LinkedQueue

For each call to the runStackTestCase() method your main() method will a table with the following output for the Array Based Stack and the Linked Stack implementations:

Running test = Test Case Name

Run 1	Run 2	Run 3	Run 4	Run 5	Run 6	Run 7	Run 8	Run 9	Run 10	AverageMicro Seconds
-------	-------	-------	-------	-------	-------	-------	-------	-------	-------	-------

ArrayBasedStack

LinkedStack

Running test = Test Case Name

Run 1	Run 2	Run 3	Run 4	Run 5	Run 6	Run 7	Run 8	Run 9	Run 10	Average Kilo Bytes
-------	-------	-------	-------	-------	-------	-------	-------	-------	-------	-------

ArrayBasedStack

LinkedStack

13. Analysis:
Using the tables you created by running Driver.main(), copy your results into a text document and answer the following questions using 1-3 complete sentences for each question:

1. Discuss the difference in run times and memory usage between the array based queue and the linked queue for all the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.

2. Are the run times ever similar for both the array based queue and the linked queue? Why or why not? Be as specific as possible.

3. In which test cases is the array based queue faster than the linked queue? Please explain the reason. Be as specific as possible.

4. Discuss the difference in run times and memory usage between the array based stack and the linked stack for all the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.

5. Are the run times ever similar for both the array based stack and the linked stack? Why or why not? Be as specific as possible.

6. In which test cases is the array based stack faster than the linked stack? Please explain the reason. Be as specific as possible.

Bring your analysis to class for discussion.

Answer 1

Node.java:

public class Node

{

String data;

Node next;

Node prev;

public Node(String data,Node next, Node prev){

this.next=next;

this.data=data;

this.prev=prev;

}

public Node(){

}

public String getData(){

return data;

}

public void setData(String data){

this.data=data;

}

public Node getNext(){

return next;

}

public void setNext(Node next){

this.next=next;

}

public Node getPrev(){

return prev;

}

public void setPrev(Node prev){

this.prev=prev;

}

}

Linked Queue.java:

public class LinkedQueues {

Node head ;

Node tail;

int size=0;

public Oueues(){

this.head=null;

this.tail=null;

}

public boolean isEmpty()

{

return head == tail;

}   

public int getSize()

{

return size;

}   

public void insert(String data){

Node tmp = new Node(data,null,null);

tmp.data=data;

tmp.next=null;

if(head==null){

head=tail=tmp;

head.prev=null;

}

else{

tail.next=tmp;

tmp.prev=tail;

tail=tmp;

}

}

public String remove(){

if(head.next==tail)

return null;// list empty

Node tmp=head.next;

head.next=tmp.next;

tmp.next.prev=head;

list();

return tmp.data;

}

public void list(){

System.out.println("Queues");

if(size==0){

System.out.println("İs Empty");

}

Node tmp=head;

while(tmp !=tail.getNext()){

System.out.println(tmp.getVeri()+" ");

tmp= tmp.getNext();

}

System.out.println();

}

Linkedstack.java:

public class LinkedStack {

Node head = null;

Node tail = null;

int size=0;

public int getSize() {

return size;

}

public boolean isEmpty()

{

return head == null;

}   

public void Push(String data) {

tail = head;

head = new Node(data,null,null);

head.data=data;

head.next= tail;

head.prev = null;

if(tail != null) {

tail.prev=head;

}

size++;

}

public void Pop() {

if (!isEmpty()) {

head = head.next; // delete first node

size--;

} else {

System.out.println("İs Empty");

}

}

public void Top() {

Node tmp = head;

while (tmp != null) {

System.out.println(tmp.getData());

tmp = tmp.getNext();

}

}

}

ArrayBasedQueue.java

import java.util.LinkedList;

import java.util.Queue;

  

public class ArrayBasedQueue

{

public static void main(String[] args)

{

Queue<Integer> q = new LinkedList<>();

  

// Adds elements {0, 1, 2, 3, 4} to queue

for (int i=0; i<5; i++)

q.add(i);

  

// Display contents of the queue.

System.out.println("Elements of queue-"+q);

int removedele = q.remove();

System.out.println("removed element-" + removedele);

  

System.out.println(q);

int head = q.peek();

System.out.println("head of queue-" + head);

  

int size = q.size();

System.out.println("Size of queue-" + size);

}

}

ArrayBasedStack.java:

import java.io.*;

import java.util.*;

  

public class ArrayBasedStack

{

static void stack_push(Stack<Integer> stack)

{

for(int i = 0; i < 5; i++)

{

stack.push(i);

}

}

  

// Popping element from the top of the stack

static void stack_pop(Stack<Integer> stack)

{

System.out.println("Pop :");

  

for(int i = 0; i < 5; i++)

{

Integer y = (Integer) stack.pop();

System.out.println(y);

}

}

}

TestTimes.java:

public class TestTimes implements TestTimesInterface

{

public static enum TimeUnits {};

public static enum MemoryUnits{};

}

Driver.java:

public class driver

{

public static void main(String args[])

{

Scanner s = new Scanner(System.in);

LinkedStack y = new LinkedStack();

LinkedQueues k = new LinkedQueues();

ArrayBasedStack as=new ArrayBasedStack();

ArrayBasedQueue as=new ArrayBasedQueue();

FileWriter fwy;

FileWriter fwk;

File stack = new File("stack.txt");

if (!stack.exists()) {

stack.createNewFile();

} else {

System.out.println("already exists ");

}

BufferedReader reader = null;

reader = new BufferedReader(new FileReader(stack));

String line = reader.readLine();

while (line != null) {

y.Push(line = reader.readLine());

System.out.println(line);

}

File queue = new File("queue.txt");

if (!queue.exists()) {

queue.createNewFile();

} else {

System.out.println("already exists ");

}

BufferedReader read = null;

read = new BufferedReader(new FileReader(queue));

String lines = read.readLine();

while (lines != null) {

lines = read.readLine();

k.insert(lines);

System.out.println(lines);

}

int choice;

System.out.println("1. Stack out- queue add");

System.out.println("2. Stack add- queue out");

System.out.println("3. Stack and queue ");

System.out.println("4. File writer");

choice = s.nextInt();

switch (choice) {

case 1:

k.insert(s.next());

k.list();

y.pop();

break;

case 2:

y.Push(s.next());

y.Top();

k.remove();

break;

case 3:

y.Top();

k.list();

break;

case 4:

fwy = new FileWriter(stack);

Node no = y.head;

while (no.next != null) {

fwy.write("\n" + no.data);

no = no.next;

}

fwy.flush();

fwy.close();

fwk = new FileWriter(queue);

Node noo = k.head;

while (noo.next != null) {

fwk.write("\n" + noo.data);

noo = noo.next;

}

fwk.flush();

fwk.close();

break;

}

}

}