package csci3230.hw3; import java.io.File; import java.io.IOException; import ja

Question

package csci3230.hw3;

import java.io.File;
import java.io.IOException;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Random;

import csci3230.hw3.OutputWriter;

public class DoublyLinkedList<Item> implements Iterable<Item> {
private int n; // number of elements on list
private Node pre; // sentinel before first item
private Node post; // sentinel after last item

public DoublyLinkedList() {
pre = new Node();
post = new Node();
pre.next = post;
post.prev = pre;
}

// linked list node helper data type
private class Node {
private Item item;
private Node next;
private Node prev;
}

public boolean isEmpty() { return n==0;} // your code}
public int size() { return n;}// your code }

// add the item to the list
public void add(Item item) {
Node last = post.prev;
Node x = new Node();
x.item = item;
x.next = post;
x.prev = last;
post.prev = x;
last.next = x;
n++; // your code
}

public ListIterator<Item> iterator() { return new DoublyLinkedListIterator(); }

// assumes no calls to DoublyLinkedList.add() during iteration
private class DoublyLinkedListIterator implements ListIterator<Item> {
private Node current = pre.next; // the node that is returned by next()
private Node lastAccessed = null; // the last node to be returned by prev() or next()
// reset to null upon intervening remove() or add()
private int index = 0;

public boolean hasNext() { return index<n;}// your code }
public boolean hasPrevious() { return index >0;}// your code }
public int previousIndex() { return index - 1;}// your code }
public int nextIndex() { return index;}// your code }

public Item next() {
   if (!hasNext()) throw new NoSuchElementException();
lastAccessed = current;
Item item = current.item;
current = current.next;
index++;
return item;// your code
}

public Item previous() {
   if (!hasPrevious()) throw new NoSuchElementException();
current = current.prev;
index--;
lastAccessed = current;
return current.item;// your code
}

// replace the item of the element that was last accessed by next() or previous()
// condition: no calls to remove() or add() after last call to next() or previous()
public void set(Item item) {
   if (lastAccessed == null) throw new IllegalStateException();
lastAccessed.item = item;// your code
}

// remove the element that was last accessed by next() or previous()
// condition: no calls to remove() or add() after last call to next() or previous()
public void remove() {
   if (lastAccessed == null) throw new IllegalStateException();
Node x = lastAccessed.prev;
Node y = lastAccessed.next;
x.next = y;
y.prev = x;
n--;
if (current == lastAccessed)
current = y;
else
index--;
lastAccessed = null;// your code
}

// add element to list
public void add(Item item) {
   Node x = current.prev;
Node y = new Node();
Node z = current;
y.item = item;
x.next = y;
y.next = z;
z.prev = y;
y.prev = x;
n++;
index++;
lastAccessed = null;// your code
}

}

public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}

/* a test client
* arg[1]: number of input values
* arg[2]: random seed
* arg[3]: output file path
*/
public static void main(String[] args) throws IOException {
  
   int n, seed;
   File outputFile;
   File dir = new File(".");
  
   if (args.length > 0) {
       n = Integer.parseInt(args[0]);
       seed = Integer.parseInt(args[1]);
   }else {
       n = 10;
       seed = 1;
   }
  
   if (args.length == 3) {
           outputFile = new File(args[2]);
       } else {
           outputFile = new File(dir.getCanonicalPath() + File.separator + "Files/testOut_DLL");  
       }
   OutputWriter out = new OutputWriter(outputFile);
  
Random r = new Random(seed);
  
// add elements 1, ..., n
out.writeOutput("Integer items to insert: "+ n);
DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
for (int i = 0; i < n; i++)
list.add(r.nextInt(100));
out.writeOutput(list.toString());
  

ListIterator<Integer> iterator = list.iterator();

// go forwards with next() and set()
out.writeOutput("add 1 to each element via next() and set()");
while (iterator.hasNext()) {
int x = iterator.next();
iterator.set(x + 1);
}
out.writeOutput(list.toString());
  

// go backwards with previous() and set()
out.writeOutput("multiply each element by 3 via previous() and set()");
while (iterator.hasPrevious()) {
int x = iterator.previous();
iterator.set(x + x + x);
}
out.writeOutput(list.toString());

// remove all elements that are multiples of 4 via next() and remove()
out.writeOutput("remove elements that are a multiple of 4 via next() and remove()");
while (iterator.hasNext()) {
int x = iterator.next();
if (x % 4 == 0) iterator.remove();
}
out.writeOutput(list.toString());

// remove all even elements via previous() and remove()
out.writeOutput("remove elements that are even via previous() and remove()");
while (iterator.hasPrevious()) {
int x = iterator.previous();
if (x % 2 == 0) iterator.remove();
}
out.writeOutput(list.toString());

// add elements via next() and add()
out.writeOutput("add elements via next() and add()");
while (iterator.hasNext()) {
int x = iterator.next();
iterator.add(x + 1);
}
out.writeOutput(list.toString());

// add elements via previous() and add()
out.writeOutput("add elements via previous() and add()");
while (iterator.hasPrevious()) {
int x = iterator.previous();
iterator.add(x * 10);
iterator.previous();
}
out.writeOutput(list.toString());
}
}

The class below(LinkedListStack) is where I need help. Im suppose to complete the rest of the methods (pop,push, size, isEmpty, top). I also need help with the method that finds the maximum value.

package csci3230.hw3;

import java.io.File;
import java.io.IOException;
import java.util.ListIterator;
import java.util.Random;

public class LinkedListStack {

   DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();

   public int size() {
       // your code
   }

   public void push(Integer s){
   // your code
   }

   public Integer pop() {
       // your code
   }
  
   public Integer top() {
       // your code
   }
  
   public boolean isEmpty() {
       // your code
   }

   public String displayStack() {
       return (list.toString());
   }

    public static void main(String[] args) throws IOException {
       LinkedListStack stack = new LinkedListStack();

       int n, seed;
   File outputFile;
   File dir = new File(".");
  
   if (args.length > 0) {
       n = Integer.parseInt(args[0]);
       seed = Integer.parseInt(args[1]);
   }else {
       n = 10;
       seed = 1;
   }
  
   if (args.length == 3) {
           outputFile = new File(args[2]);
       } else {
           outputFile = new File(dir.getCanonicalPath() + File.separator + "Files/testOut_Stack");  
       }
   OutputWriter out = new OutputWriter(outputFile);
  
Random r = new Random(seed);
  
Integer nextval;
for (int i = 0; i < n; i++) {
nextval = r.nextInt(10000);
// your code
/* retain the max value that you see among the integers generated in the stack.
* In the end there should be only one integer in stack, which is the max value
*/
}
  
// write the content of stack -- which is the max value -- to file
       out.writeOutput(stack.displayStack());
   }
}

Explanation / Answer

Here is the stack implementation using the doublylinked list code above. Please don't forget to rate the answer if it helped. Thank you very much.

package csci3230.hw3;
import java.io.File;
import java.io.IOException;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Random;
public class LinkedListStack {
  
DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
  
public int size() {
return list.size();
}
  
public void push(Integer s){
   list.iterator().add(s);      
}
  
public Integer pop() {
  
   ListIterator<Integer> iterator = list.iterator();
   if(!iterator.hasNext())
       throw new NoSuchElementException();
  
   Integer value = iterator.next();
   iterator.remove();
   return value;
      
}
  
public Integer top() {
   ListIterator<Integer> iterator = list.iterator();
   if(!iterator.hasNext())
       throw new NoSuchElementException();
  
   Integer value = iterator.next();
   return value;
}
  
public boolean isEmpty() {
return list.isEmpty();
}
public String displayStack() {
return (list.toString());
}
public static void main(String[] args) throws IOException {
LinkedListStack stack = new LinkedListStack();
int n, seed;
File outputFile;
File dir = new File(".");
  
if (args.length > 0) {
n = Integer.parseInt(args[0]);
seed = Integer.parseInt(args[1]);
}else {
n = 10;
seed = 1;
}
  
if (args.length == 3) {
outputFile = new File(args[2]);
} else {
outputFile = new File(dir.getCanonicalPath() + File.separator + "Files/testOut_Stack");
}
OutputWriter out = new OutputWriter(outputFile);
  
Random r = new Random(seed);
  
Integer nextval;
for (int i = 0; i < n; i++) {
nextval = r.nextInt(10000);
/* retain the max value that you see among the integers generated in the stack.
* In the end there should be only one integer in stack, which is the max value
*/
if(stack.isEmpty())
   stack.push(nextval);
else if(stack.top() < nextval)
{
   stack.pop();
   stack.push(nextval);
}
}


// write the content of stack -- which is the max value -- to file
out.writeOutput(stack.displayStack());
out.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.