Your objective for this assignment is to implement both the

Your objective for this assignment is to implement both the stack and queue data structures in java. You will start by downloading the template files from Blackboard. You are required to fill in the missing method bodies for the List, Stack, and Queue classes. You should NOT modify the ListNode class. You may add more helper methods or attributes to the other classes. When you submit your project you may include your main class but it will only be used if the support classes do not compile. Please refer to the sample code starting on the next page to test the functionality of your three data structures.

Sample List Test

Standard Output

List<Character> list = new List<>(); list.insert(0, \'A\');

list.insert(1, \'B\');

list.insert(2, \'C\'); list.print(); list.insert(1, \'X\'); list.print(); list.delete(0); list.print();

[A, B, C]

[A, X, B, C]

[X, B, C]

Method Return

list.find(\'C\');

2

list.find(\'D\');

-1

list.get(0);

\'X\'

Solution

import java.util.*;

/**
*Exception to indicate that LinkedList is empty.
*/
class LinkedListEmptyException extends RuntimeException{
public LinkedListEmptyException(){
super();
}
  
public LinkedListEmptyException(String message){
super(message);
}
}

/**
*Exception to indicate that Queue is empty.
*/
class QueueEmptyException extends RuntimeException {

public QueueEmptyException(){
super();
}
  
public QueueEmptyException(String message){
super(message);
}
  
}

/**
*Exception to indicate that Stack is empty.
*/
class StackEmptyException extends RuntimeException {

public StackEmptyException(){
super();
}
  
public StackEmptyException(String message){
super(message);
}
  
}

/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.

/**
* Constructor
*/
public Node(int data){
this.data = data;
}

/**
* Display Node\'s data
*/
public void displayNode() {
System.out.print( data + \" \");
}
}


/**
* LinkedList class
*/
class LinkedList {
private Node first; // ref to first link on list

/**
* LinkedList constructor
*/
public LinkedList(){
first = null;
}

  
/**
* Insert New Node at first position
*/
public void insertFirst(int data) {
Node newNode = new Node(data); //Creation of New Node.
newNode.next = first; //newLink ---> old first
first = newNode; //first ---> newNode
}
  
  
/**
* Inserts new Node at last of LinkedList.
*/
public void insertLast(int data){
Node newNode = new Node(data); //Creation of New Node.

if(first==null){ //means LinkedList is empty, make first point to new Node.
first=newNode; //first ---> newNode
return;
}

Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
while(tempNode.next!=null){ //Executes until we don\'t find last Node of LinkedList.
//If next of some Node is pointing to null, that means it\'s a last Node.
tempNode=tempNode.next; //move to next Node.
}
tempNode.next=newNode; //make last\'s Node next point to new Node
}
  
  


/**
* Deletes first Node
*/
public Node deleteFirst()
{
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException(\"LinkedList doesn\'t contain any Nodes.\");
}
Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
first = first.next; // delete first Node (make first point to second node)
return tempNode; // return tempNode (i.e. deleted Node)
}
  

  
/**
* Display LinkedList
*/
public void displayLinkedList() {
Node tempDisplay = first; // start at the beginning of linkedList
while (tempDisplay != null){ // Executes until we don\'t find end of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println();

}

}


/**
* For implementing queue using using LinkedList- This QueueLinkedList
* class internally maintains LinkedList reference in java.
*/

class QueueLinkedList{
  
LinkedList linkedList = new LinkedList(); // creation of Linked List
  
/**
* Insert element at rear in Queue
*/
public void insert(int value){
linkedList.insertLast(value);
}

/**
* Removes elements from front of Queue
*/
public void remove() throws QueueEmptyException {
try{
linkedList.deleteFirst();
}catch(LinkedListEmptyException llee){
throw new QueueEmptyException();
}
}

/**
* Display queue.
*/
public void displayStack() {
System.out.print(\"Displaying Queue> Front to Rear: \");
linkedList.displayLinkedList();
}

  
}
//Stack

class StackLinkedList{
  
LinkedList linkedList = new LinkedList(); // creation of Linked List
  
/**
* Push items in stack, it will put items on top of Stack.
*/
public void push(int value){
linkedList.insertFirst(value);
}

/**
* Pop items in stack, it will remove items from top of Stack.
*/
public void pop() throws StackEmptyException {
try{
linkedList.deleteFirst();
}catch(LinkedListEmptyException llee){
throw new StackEmptyException();
}
}

/**
* Display stack.
*/
public void displayStack() {
System.out.print(\"Displaying Stack > Top to Bottom : \");
linkedList.displayLinkedList();
}

  
}

//End Stack



/**
* Main class - To test Queue Implementation Using LinkedList in java
*/
public class ImplementationUsingLinkedListExample {
public static void main(String[] args) {

QueueLinkedList queueLinkedList=new QueueLinkedList();

System.out.println(\"INSERTING AT LAST (REAR) IN QUEUE IMPLEMENTED USING LINKED LIST \");
queueLinkedList.insert(11); //insert node.
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST
queueLinkedList.insert(71); //insert node.
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST
queueLinkedList.insert(39); //insert node.
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST
queueLinkedList.insert(31); //insert node.
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST

System.out.println(\"\ DELETING FROM FIRST (FRONT) OF QUEUE IMPLEMENTED USING LINKED LIST \");

queueLinkedList.remove(); //remove Node
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST
queueLinkedList.remove(); //remove Node
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST
queueLinkedList.remove(); //remove Node
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST
queueLinkedList.remove(); //remove Node
queueLinkedList.displayStack(); // display QUEUE IMPLEMENTED USING LINKED LIST

   //Test Stack

StackLinkedList stackLinkedList=new StackLinkedList();
System.out.println(\"INSERTING AT FIRST (TOP) IN STACK IMPLEMENTED USING LINKED LIST \");
stackLinkedList.push(39); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.push(71); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.push(11); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.push(76); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java

System.out.println(\"\ DELETING FROM FIRST (TOP) FROM STACK IMPLEMENTED USING LINKED LIST \");

stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
}
}