Solution in Java The Problem Integer numbers must be loaded into and stored in a

Question

Solution in Java

The Problem

Integer numbers must be loaded into and stored in a stack such that the largest value is always stored at the top position (that is the numbers are kept sorted in decreasing order).

The numbers are read by the program from a file. The numbers in the file are not necessarily sorted.

The stack must be linked list based.

(10pts)Generic implementation is required, that is, the data in the nodes must be objects. Use the Integer type at instantiation for data rather than int.

(10pts) The implementation must be tested and the result (decreasing storage) verified.

(20pts)Determine the big-Oh for the performance of your algorithm

Analysis and Design

(15pts)Make a careful design before implementation. Decide about the classes and additional methods needed to load up the stack.

(15pts)Write a pseudo-code (attach it as a comment after the Application class).

Implementation and Testing

When a new element is added to the stack, one or more elements may have to be popped, since the new value may not be greater than the current top value. You will need a temporary storage for these popped elements before they can be pushed back. You must use a second stack for temporary storage (10pts).

A file numbers.txt is attached to this assignment, the file contains 500 numbers randomly selected between 1 and 10,000. Use this file to test the correctness of your methods (10pts). Use the toString( ) method (see HW4) to collect the output showing the state of the stack and print the output to the console (10pts).

Document your program.

Explanation / Answer

Solved first 4 parts of the question as per guidelines

Part 1&2 : Code for part 1 and 2 :

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

// class Node ( uses generic type Integer )
class Node
{
protected Integer data;
protected Node link;

public Node()
{
link = null;
data = 0;
}
public Node(Integer d,Node n)
{
data = d;
link = n;
}
  
// set and get methods for protected data
public void setLink(Node n)
{
link = n;
}
public void setData(Integer d)
{
data = d;
}
public Node getLink()
{
return link;
}
public int getData()
{
return data;
}
}

// stack which is implemented as a linked list with nodes of type 'Node' class
class linkedStack
{
protected Node top ;
protected int size ;

public linkedStack()
{
top = null;
size = 0;
}
// if no element in stack
public boolean isEmpty()
{
return top == null;
}
public int getSize()
{
return size;
}
public void push(Integer data)
{
Node nptr = new Node (data, null);
if (top == null) // if no element in stack
top = nptr;
else
{
nptr.setLink(top);
top = nptr;
}
size++ ;
}
public int pop()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ; // cannot pop
Node ptr = top;
top = ptr.getLink();
size-- ;
return ptr.getData();
}
}

// main class which tests the implementation as mentioned in part 2 of question
public class LinkedListStackImplement
{
public static void main(String[] args)
{
Scanner scan;
Integer [] numbers = new Integer [100000]; // an array to store numbers in file
int i = 0;
       try {
           scan = new Scanner(new File("numbers.txt")); // read numbers from file
           System.out.print("Numbers in text file : ");
           while(scan.hasNextInt())
           {
           numbers[i++] = scan.nextInt();
           System.out.print(numbers[i-1]+" ");
           }
           System.out.println();
       } catch (FileNotFoundException e1) {
           System.out.println("File not found");
       }
       Arrays.sort(numbers,0,i);
// Creating object of class linkedStack
linkedStack ls = new linkedStack();
for(int j=0;j<i;j++)
{
   ls.push(numbers[j]);
}
  
// popping all numbers to verify correctness
System.out.println("Popping elements to verify order");
while(!ls.isEmpty())
{
   System.out.println("Popped integer : "+ls.pop());
}
}
}

Part 3 :

Assuming we have n numbers to store:

Complexity of reading numbers from file : O(n)

Complexity of sorting numbers : O(nlogn)

Complexity of pushing numbers on the stack : O(1) for each, O(n) in total

Complexity of popping numbers from stack : O(1) for each, O(n) in total

Overall Complexity = O(nlogn)

Part 4 : Following classes and methods have been created:

Class Node - Methods :

Node(),Node(Integer d,Node n) {constructors}

setLink(Node n),setData(Integer d),getLink(),getData() {set and get members}

Class LinkedStack - Methods:

LinkedStack(), isEmpty(), push(), pop()

Class LinkedStackImplement : implementation class, only main() method

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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