Answer To: assign4/~$signment-04.docx assign4/Assignment-04.docx Classes to use that I attached in the zip...
Abhishek answered on Mar 28 2021
52758 - data Structures/Screenshots/O1.png
52758 - data Structures/Problem/assign4-kwtdlxua-3l4nifhn.zip
assign4/~$signment-04.docx
assign4/Assignment-04.docx
Classes to use that I attached in the zip
Ring.java
RingNode.java
Objective
implement a linked-list based Stack and an array-based Queue data structures and some additional methods that use stacks and queues.
IMPORTANT: You may NOT use the Stack and Queue classes from the java library. Instead, you must implement your own Stack and Queue data structures as explained below.
Question 1: Stack
Part 1: Implement RingLinkedStack
In this part, you will use/implement the following classes.
· Ring.java – This is in the zip file that I provided
· RingNode.java - This is in the zip file that I provided
· RingLinkedStack: We implemented IntLinkedStack that stores integers. Start from the implementation of IntLinkStack and change as appropriate to implement the RingLinkedStack which is a stack that can hold elements of type Ring. – Use IntLinkedStack.java that I provided as reference
· RingStackDriver: includes a main method to test the functionality of your stack. This file also includes additional methods that use the stack as described below.
class RingLinkedStack
· RingLinkedStack is a linked-list-based stack that can hold elements of type Thing. Start from the IntLinkedStack implementation and change as appropriate.
· The class has exactly 2 private instance variables such that:
· one instance variable must be RingNode reference variable and this variable will be used to keep track of the top of the stack.
· one instance variable must be a counter that keeps track of the number of items on the stack.
· The class has the following methods:
· a constructor that sets the top of stack to null and initializes the number of items on the stack to 0.
· isEmpty() returns true if there are no elements on the stack and returns false if the stack has one or more data elements.
· peek() returns a copy of the element stored at the top of the stack. peek() does not change the stack in any way. peek() throws an EmptyStackException if the stack is empty.
· pop() removes and returns the element stored at the top of the stack. pop() throws an EmptyStackException if the stack is empty.
· push() is a void method with one parameter which is an element of type Thing to be added to the top of the stack.
· toString() returns a String which lists the elements in the stack from top to bottom.
toString() does not change the stack.
· size() returns the number of items on the stack.
Part 2: Implement RingStackDriver
First, add the main method and write statements to test all the methods that you implemented in RingLinkedStack. Then, implement the methods described below as static methods in RingStackDriver and write code, in the main method, to call and test the methods. Note the following:
· You must use the RingLinkedStack class that you wrote in part 1 above. Do NOT use the Java-provided Stack.
· All the methods are static and are implemented in the RingStackDriver class.
· The input stack should remain unchanged after the method call except only as required by the method.
· Include appropriate comments for each method using Javedoc. For each method briefly explain your algorithm and, explain each parameter and the return value.
Method
Description
Suggested Test Cases
stackToInt()
A static method that takes a stack of Things as a parameter. Assume that the input stack contains 7 or less things and all of them has an integer attribute in the range 0 to 9. The method returns an integer number representation of the values stored on the stack where the most significant digit is at the top of the stack. For example, if the input stack is as shown, the output integer is 5478. When the method has finished, the stack will be empty.
Red,5
Blue,4
Green,7
Red, 8
Top of
Stack
*4 elements in the stack.
*empty stack
*1 element
*1 element with integer attribute 0.
popSome()
A static method that takes two input parameters, a RingLinkedStack and an integer value count. The method then pops count elements from the stack. The method returns the sum of the integer attributes of the popped elements. If the stack has less than count values, the method returns -1.
*Stack has 3 rings and count = 3.
*Stack has more than 3 ring and count = 3. *Stack has less than 3 ring and count = 3. *Stack has no ring and count = 3.
*Stack has several rings and count = 0.
*Stack has several rings and count is negative.
extractFromStack()
A static void method that takes two input parameters, a RingLinkedStack and a Thing target element. The method removes all occurrences of the input target. All other elements in the stack must remain unchanged and in the same order. You must use the Thing class' equals() method.
*Stack has multiple rings, one of which matches the input target.
*Stack has multiple rings, several of which match the input target.
*Stack has multiple rings, none of which match the input target.
*Stack is empty.
equalStacks()
A static method that takes two
RingLinkedStacks as input
parameters, and returns true or false based on whether the two stacks are equal or not. Assume that two stacks are equal if they have the same Things in the same order. The two input stacks must remain unchanged after the call to this method. The method must use the Thing class equals() method.
*Stacks are not empty and are equal.
*Stacks are not empty and are not equal.
*One stack is empty
(returns false).
*Both stacks are empty (returns true).
*Test for case insensitivity.
assign4/IntLinkedStack.java
assign4/IntLinkedStack.java
import java.util.EmptyStackException;
/**
* Invariant of the IntLinkedStack class:
* 1. The items in the stack are stored in a linked list, with the top of
* the stack stored at the head node, down to the bottom of the stack
* at the final node.
* 2. The instance variable top is the head reference of the linked list of items.
*
*
*/
public class IntLinkedStack implements IntStackInterface
{
private IntNode top;
/**
* Initialize an empty stack.
**/
public IntLinkedStack( ){
top = null;
}
/**
* Determine whether this stack is empty.
* @return true if this stack is empty and false otherwise.
**/
public boolean isEmpty( ){
return (top == null);
}
/**
* @return the top item of the stack without removing it
* @exception EmptyStackException Indicates that this stack is empty.
**/
public int peek( ) {
if (top == null)
// EmptyStackException is from java.util and its constructor has no argument.
throw new EmptyStackException( );
return top.getData( );
}
/**
* Get the top item, removing it from this stack.
* @return The return value is the top item of this stack, and the item is removed.
* @exception EmptyStackException Indicates that this stack is empty.
**/
public int pop( ) {
int answer;
if (this.top == null)
// EmptyStackException is from java.util and its constructor has no argument.
throw new EmptyStackException( );
answer = this.top.getData( );
this.top = this.top.getLink( );
return answer;
}
/**
* Push a new item onto this stack.
* @param item - the item to be pushed onto this stack
**/
public void push(int item){
this.top = new IntNode(item, this.top);
}
/**
* Accessor method to determine the number of items in this stack.
* @return the number of items in this stack
**/
public int size( ) {
return IntNode.listLength(this.top);
}
/** convert the stack to a printable string
* @return a string representing the stack
*/
public String toString() {
String output = "[ ";
IntNode cursor = top;
while (cursor != null){
output += cursor.getData()+"\t";
cursor = cursor.getLink();
}
output += " ] \n";
return output;
}
}
assign4/Ring.java
assign4/Ring.java
public class Ring implements Comparable {
/**
* instance variables
*/
private String ring;
private int size;
/**
* Contrustor
* @param ring
* @param size
*/
public Ring(String ring, int size) {
this.ring = ring;
this.size = size;
}
/**
* Getters and Setters
* @return
*/
public String getRing() {
return this.ring;
}
public void setRing(String ring) {
this.ring = ring;
}
public int getSize() {
return this.size;
}
public void setSize(int size) {
this.size = size;
}
/**
* returns a string represent a ring
*/
@Override
public String toString() {
String output = "";
output += "Ring type-" + "["+this.ring +": ";
output += this.size +"]";
return output;
}
/**
* equals method to
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Ring other = (Ring) obj;
if (ring == null) {
if (other.ring != null)
return false;
} else if (!ring.equalsIgnoreCase(other.ring))
return false;
if (size != other.size)
return false;
return true;
}
/**
*
*/
@Override
public int compareTo(Ring otherRing) {
int output = 0;
if (this.ring.equalsIgnoreCase(otherRing.ring)) {
if (this.size > otherRing.size)
output = 1;
else if(this.size < otherRing.size) {
output = -1;
}
else {
output = 0;
}
}
else if(this.ring.toLowerCase().compareTo(otherRing.ring.toLowerCase())<0){
output = -1;
}
else {
output = 1;
}
return output;
}
}
assign4/RingNode.java
assign4/RingNode.java
public class RingNode {
private Ring data;
private RingNode link ;
public RingNode(Ring data, RingNode link) {
super();
this.data = data;
this.link = link;
}
public Ring getData() {
return data;
}
public void setData(Ring data) {
this.data = data;
}
public RingNode getLink() {
return link;
}
public void setLink(RingNode link) {
this.link = link;
}
public void addNodeAfter(Ring element){
this.link = new RingNode(element,this.link);
}
public void removeNodeAfter(){
this.link = this.link.link;
}
public static int listLength(RingNode head){
RingNode cursor = head;
int answer = 0;
while (cursor != null){
answer++;
cursor = cursor.link;
}
return answer;
}
public static RingNode listSearch(RingNode head, Ring target){
RingNode cursor = head;
while (cursor != null){
if (cursor.getData().equals(target))
return cursor;
cursor = cursor.getLink();
}
return null;
}
public static RingNode listPosition(RingNode head, int position){
RingNode cursor = head;
int index = 1;
while (cursor != null && index < position){
index++;
cursor = cursor.getLink();
}
return cursor;
}
public static void display(RingNode list){
RingNode cursor = list;
while (cursor != null){
System.out.println(cursor.getData());
cursor = cursor.getLink();
}
}
}
52758 - data Structures/Solution/Simple Code Files/RingNode.java
52758 - data Structures/Solution/Simple Code Files/RingNode.java
public class RingNode {
private Ring data;
private RingNode link ;
public RingNode(Ring data, RingNode link) {
super();
this.data = data;
this.link = link;
}
public Ring getData() {
return data;
}
public void setData(Ring data) {
this.data = data;
}
public RingNode getLink() {
return link;
}
public void setLink(RingNode link) {
this.link = link;
}
public void addNodeAfter(Ring element){
this.link = new RingNode(element,this.link);
}
public void removeNodeAfter(){
this.link = this.link.link;
}
public static int listLength(RingNode head){
RingNode cursor = head;
int answer = 0;
while (cursor != null){
answer++;
cursor = cursor.link;
}
return answer;
}
public static RingNode listSearch(RingNode head, Ring target){
RingNode cursor = head;
while (cursor != null){
if (cursor.getData().equals(target))
return cursor;
cursor = cursor.getLink();
}
return null;
}
public static RingNode listPosition(RingNode head, int position){
RingNode cursor = head;
int index = 1;
while (cursor != null && index < position){
index++;
cursor = cursor.getLink();
}
return cursor;
}
public static void display(RingNode list){
RingNode cursor = list;
while (cursor != null){
System.out.println(cursor.getData());
cursor = cursor.getLink();
}
}
}
52758 - data Structures/Solution/Simple Code Files/Ring.java
52758 - data Structures/Solution/Simple Code Files/Ring.java
public class Ring implements Comparable {
/**
* instance variables
*/
private String ring;
private int size;
/**
* Contrustor
* @param ring
* @param size
*/
public Ring(String ring, int size) {
this.ring = ring;
this.size = size;
}
/**
* Getters and Setters
* @return
*/
public String getRing() {
return this.ring;
}
public void setRing(String ring) {
this.ring = ring;
}
public int getSize() {
return this.size;
}
public void setSize(int size) {
this.size = size;
}
/**
* returns a string represent a ring
*/
@Override
public String toString() {
String output = "";
output += "Ring type-" + "["+this.ring +": ";
output += this.size +"]";
return output;
}
/**
* equals method to
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Ring other = (Ring) obj;
if (ring == null) {
if (other.ring != null)
return false;
} else if (!ring.equalsIgnoreCase(other.ring))
return false;
if (size != other.size)
return false;
return true;
}
/**
*
*/
@Override
public int compareTo(Ring otherRing) {
int output = 0;
if (this.ring.equalsIgnoreCase(otherRing.ring)) {
if (this.size > otherRing.size)
output = 1;
else if(this.size < otherRing.size) {
output = -1;
}
else {
output = 0;
}
}
else if(this.ring.toLowerCase().compareTo(otherRing.ring.toLowerCase())<0){
output = -1;
}
else {
output = 1;
}
return output;
}
}
52758 - data Structures/Solution/Simple Code Files/RingStackDriver.java
52758 - data Structures/Solution/Simple Code...