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:
Array Based
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
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
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.
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.
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.
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.
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.
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()
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.
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.
Queue Test Cases
All the elements being enqueued and dequeued from your queues must
be instances of the java.lang.String class.
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.
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.
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.
Stack Test Cases
All the elements being pushed and popped from your stacks must be
instances of the java.lang.String class.
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.
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.
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.
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
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:
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.
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.
In which test cases is the array based queue faster than the linked queue? Please explain the reason. Be as specific as possible.
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.
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.
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.
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;
}
}
}
In this assignment you will be implementing two Abstract Data Types (ADT) the Queue ADT and...
1. Use diagrams to explain the logic to return a reversed Queue. Provide solutions for both array Queue and linked list stack. Explain the steps then use pseudocode to explain the implementation. Then use C++, C# or Java to implement the method and test it. Use diagrams to explain the logic to return a reversed Queue. Provide solutions for both array Queue and linked list stack. Explain the steps then use pseudocode to explain the implementation. Then use C++ to...
Goals This assignment is an individual assignment and you will work on it on your own. The goal of this assignment is to be able to use stacks and queues, and to master and have an in-depth understanding of such primitive ADTs. In this assignment you will build a more complex ADT using the primitive stack and queue ADTs. Moreover, an important goal of this assignment is to be able to analyze an ADT that you will build yourself using...
Please help with this Java Program. Thank you! we will be implementing an Ordered List ADT. Our goal is to implement the interface that is provided for this ADT. Notice that there are two interfaces: OrderedListADT builds on ListADT. In this homework, you'll only be responsible for the OrderedListADT. Figure 1: UML Overview 1 Requirements Create a doubly linked implementation of the OrderedListADT interface. Note that the book includes most of the source code for a singly linked implementation of...
Create a flowchart to represent the Push and Pop operations for a Stack based on a linked list data structure. Create a flowchart to represent the Enqueue and Dequeue operations for a Queue based on a linked list data structure. Write the required Java code to implement either a Stack or a Queue data structure based on a linked list. The code should include the class constructors, the necessary properties, and methods to add and remove elements from the data...
1. Create a class MLL, a singly linked, non-circular list where each node only has one link next and the list has a head and a tail link (think about implementation of node). The MLL class also implements the Iterable interface. The following should be implemented as well: 2. Add the methods to the MLL class: a. iterator() to implement the Iterable interface. This method returns an instance of MLLI initialized appropriately. b. addFirst( value) that adds a value to...
In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to...
Lab 3 – Array-Based Stack and Queue Overview In this assignment, you will be implementing your own Array-Based Stack (ABS) and Array-Based Queue (ABQ). A stack is a linear data structure which follows the Last-In, First-Out (LIFO) property. LIFO means that the data most recently added is the first data to be removed. (Imagine a stack of books, or a stack of papers on a desk—the first one to be removed is the last one placed on top.) A queue...
To solve real world problem, the programer uses ADT like list, stack, queue, set, map, ... etc. to build our data model. In AS8, we pick and choose STL queue and stack to build a postfix calculator. In this assignment you are to Design your own linked-list, a series of integer nodes. The private attributes of this IntLinked Queue including a integer node struct and private control variables and methods: private: struct Node { int data; Node *next; }; Node...
Implement the stack queue data structure with a linked list implementation to get the given test code in driver.cpp to work properly: driver.cpp code: #include <iostream> #include "stackLL.h" using namespace std; int main() { /////////////Test code for stack /////////////// stackLL stk; stk.push(5); stk.push(13); stk.push(7); stk.push(3); stk.push(2); stk.push(11); cout << "Popping: " << stk.pop() << endl; cout << "Popping: " << stk.pop() << endl; stk.push(17); stk.push(19); stk.push(23); while( ! stk.empty() ) { cout << "Popping: " << stk.pop() << endl; }...
(The interface class-like) Assume you have the Edible interface with its abstract method. Design a class named Animal and its two subclasses named Mammal and Dairy. Make Sheep and Bear as subclasses of Mammal and make implement the Edible interface. howToEat() and sound() are the main two methods for all edible classes while sound() is the main method for the non-edible classes. 1. Draw the UML diagram for the classes and the interface 2. Use Arraylist class to create an...