Question

After having downloaded net.datastructures and set you classpath appropriately, create a Java program named “TestDS.java” that does the following:

- Imports SinglyLinkedList, LinkedQueue, and LinkedStack from net.datastructures (NOT from java.util)

- Creates an object of each type that can hold only the Double data type. (The data structures are generic, make them of type Double)

- Using a loop or series of commands, perform the following:

1) To the Linked List, add the numbers from 1.0 to 100.0 (both of these will be included) incrementing between each number by 0.5. That is, 1.0, 1.5, 2.0, 2.5, etc. will be stored in the list. When finished, print the list.

2) To the Stack, add the values 1.0, 0.5, 0.25, 0.125, … etc. down to 1/ 2^20. That is, each time, divide by two, and do this 20 times. When finished, print the number from the top of the stack without removing it.

3) To the Queue, add the values from the stack so that the stack is emptied when you are done. Then, add the values from the list so that the list is emptied when you are done.

- Print the queue and the values stored in the queue when this process is done.

Answer 1

1.

import java.io.*;

  
// Java program to implement
// a Singly Linked List

public class LinkedList {

  

Node head; // head of list

  

// Linked list Node.

// This inner class is made static

// so that main() can access it

static class Node {

  

int data;

Node next;

  

// Constructor

Node(int d)

{

data = d;

next = null;

}

}

  

// Method to insert a new node

public static LinkedList insert(LinkedList list, int data)

{

// Create a new node with given data

Node new_node = new Node(data);

new_node.next = null;

  

// If the Linked List is empty,

// then make the new node as head

if (list.head == null) {

list.head = new_node;

}

else {

// Else traverse till the last node

// and insert the new_node there

Node last = list.head;

while (last.next != null) {

last = last.next;

}

  

// Insert the new_node at last node

last.next = new_node;

}

  

// Return the list by head

return list;

}

  

// Method to print the LinkedList.

public static void printList(LinkedList list)

{

Node currNode = list.head;

System.out.print("LinkedList: ");

// Traverse through the LinkedList

while (currNode != null) {

// Print the data at current node

System.out.print(currNode.data + " ");

// Go to next node

currNode = currNode.next;

}

}

// Driver code

public static void main(String[] args)

{

/* Start with the empty list. */

LinkedList list = new LinkedList();

  

//

// ******INSERTION******

//

  

// Insert the values

list = insert(list, 1.0);

list = insert(list, 1.5);

list = insert(list, 2.0);

list = insert(list, 2.5);

  

  

// Print the LinkedList

printList(list);

}
}

OUTPUT: 1.0 1.5 2.0 2.5

2.

import static java.lang.System.exit;

// Create Stack Using Linked list

class StackUsingLinkedlist {

// A linked list node

private class Node {

int data;

Node link;

}

// Reference variable

Node top;

// Constructor

StackUsingLinkedlist()

{

this.top = null;

}

// Function to add an element x

// in the stack by inserting

// at the beginning of LL

public void push(int x)

{

// Create new node temp

Node temp = new Node();

// If stack is full

if (temp == null) {

System.out.print("\nHeap Overflow");

return;

}

// Initialize data into temp

temp.data = x;

// Reference into temp link

temp.link = top;

// Update top reference

top = temp;

}

// Function to check if the stack

// is empty or not

public boolean isEmpty()

{

return top == null;

}

// Function to return top element

// in a stack

public int peek()

{

// Check for empty stack

if (!isEmpty()) {

// Return the top data

return top.data;

}

// Otherwise stack is empty

else {

System.out.println("Stack is empty");

return -1;

}

}

// Function to pop top element from

// the stack by removing element

// at the beginning

public void pop()

{

// Check for stack underflow

if (top == null) {

System.out.print("\nStack Underflow");

return;

}

// Update the top pointer to

// point to the next node

top = (top).link;

}

// Function to print the elements and

// restore the stack

public static void

DisplayStack(StackUsingLinkedlist s)

{

// Create another stack

StackUsingLinkedlist s1

= new StackUsingLinkedlist();

// Until stack is empty

while (!s.isEmpty()) {

s1.push(s.peek());

// Print the element

System.out.print(s1.peek()

+ " ");

s.pop();

}

}
}

// Driver Code

public class GFG {

// Driver Code

public static void main(String[] args)

{

// Create Object of class

StackUsingLinkedlist obj

= new StackUsingLinkedlist();

// Insert Stack value

obj.push(1.0);

obj.push(0.5);

obj.push(0.25);

obj.push(0.125);

// Function Call

obj.DisplayStack(obj);

}
}

OUTPUT:
1.0 0.5 0.25 0.125

3.

import java.util.*;

  

public class GFG {

public static void main(String[] args)

throws IllegalStateException

{

  

// create object of Queue

Queue<Integer> Q

= new LinkedList<Integer>();

  

// Add numbers to end of Queue

Q.add(7855642);

Q.add(35658786);

Q.add(5278367);

Q.add(74381793);

  

// before removing print queue

System.out.println("Queue: " + Q);

}
}

Output:
Queue: [7855642, 35658786, 5278367, 74381793]