Week-02 | Stacks About Objective: The purpose of this exercise is to create a "Stack" LIFO data structure that mimics the behavior of the Java Standard Library Version (Java API). The outcomes/results...

1 answer below »

Week-02 | Stacks


About



Objective:The purpose of this exercise is to create a "Stack" LIFO data structure that mimics the behavior of the Java Standard Library Version (Java API). The outcomes/results of using the library features should be identical with your own version (My API). However, the underlying implementation should follow with the descriptions listed below.




Testing your skills.


Now that you have tested your data structure making strategies. You have already been introduced to Stacks in Practice It, now you will design and implement your own Stack and Queue data structures.




Instructions: Create a Stack class using "singly linked" data structures. NOTE: This isnotsaying the implementation is using a "singly linked" Linked List!Notice the difference between a "Linked List" and a "Linked Data Structure".




Key Points



  • A generic class allows you to have a place holder Class Type (usually T or E) until one is specified in the client class.

  • There is a difference between making a class using a "Linked List" or a "Linked Data Structure".




Where to find starter code in my-api



package.class :utils.MyStack




Where to find the test starter code in my-api


package.class :tests.console.MyStackTest




Where to find the JUNIT TEST code in my-api


package.class :tests.junit.MyStackJUnitTest




Task Check List



  • ONLY "for" loops should be used within the data structure class. There is anautomatic 30% deduction,if other loops are used.

  • The names of identifiers MUST match the names listed in the description below. Deductions otherwise.

  • The Node class must be generic and a nested class within MyQueue.

  • Complete coding Assignment in your "my-api"GitHub Repository. You will not be graded otherwise and will receive a 0, if not uploaded there.

  • Run JUNIT TEST and take a SNAPSHOT of results. Upload PDF of snapshot of yourJUnitTest results to Canvas.



Design Description:Building A Stack Data Structure


Create a generic class for a "Stack" data structure (LIFO) with the following methods:



































MethodDescriptionExample
push(item)places given element on top of stack.stack.push("Tom");
pop()removes the element at the top of the stack and returns it. Throws anEmptyStackException, if stack is empty.stack.pop();
peek()returns the element at the top of the stack without removing it from the stack. Throws an
EmptyStackException, if stack is empty.		stack.peek();
size()returns number of elements in stack.stack.size();
isEmpty()checks if stack is empty and returns true, if stack has no elements.stack.isEmpty();



string representation: displays the contents of the stack. Create a string representation of the stack from top (last) to bottom (first) reading left to right. Note: Changes will be made to how this content is displayed in a future lab.


public String toString()



MyStack



outer class: Create the generic MyStack class. This is used to control the linked node structures.



data fields:



  • first: stores the memory address of the first Node object of type NodeE>.

  • last: stores the memory address of the last Node object of type NodeE>.

  • size: stores how many elements are linked, i.e., how many Node objects are linked together.



constructor: uses a default constructor to initialize the data fields.



public MyStack()




outer class methods: your methods should follow the input and output requirements in the Java Standard Library.NOTE : All methods must be implemented. Deductions apply otherwise.









































Method



Description



Example



detach



removes the node at the top of the stack. This is a private helper method.



private void detach()



push



places given element on top of stack.



public E push(E item)



pop



removes the element at the top of the stack and returns it. Throws an
EmptyStackException, if stack is empty.



public E pop()



peek



returns the element at the top of the stack without removing it from the stack. Throws an
EmptyStackException, if stack is empty.



public E peek()



size



returns number of elements in stack.



public int size()



isEmpty



checks if stack is empty and returns true, if stack has no elements.



public boolean isEmpty()




NOTE : All methods must be implemented. Deductions apply otherwise.




inner class: class inside the body of another class.


The outer class MyStack class includes a nested static generic Node class, i.e. astatic innerclass within the Linked List class.Note: This private class does not require access to instance members of the outer class, so it is declaredstatic. This means that the node object won’t be coupled to the outer class object, and hence will be more optimal ...since it won’t require additional heap/stack memory.



data fields:



  • data: hold the data stored in each node as is of typeE.

  • next: stores the location of the next node in the list.



constructor:


A constructor that receives parameters for data, next and prev.



public Node(Node next, E data)










Week-02 | Queues


About



Objective:The purpose of this exercise is to create a Queue (FIFO) data structure that mimics the behavior of the Java Standard Library Version (Java API). The outcomes/results of using the library features should be identical with your own version (My API). However, the underlying implementation should follow with the descriptions listed below.




Testing your skills.


Now that you have tested your data structure making strategies. You have already been introduced to Queues in Practice It, now you will design and implement your own Queue data structure.




Instructions: Create a generic Queue class using "singly linked" data structure. NOTE: This isNOT THE SAME AS
using a "singly linked" Linked List!Notice the difference between a "Linked List" and a "Linked Data Structure" that uses the underlying linked node objects.




Key Points



  • A generic class allows you to have a place holder Class Type (usually T or E) until one is specified in the client class.

  • There is a difference between making a class using a "Linked List" or a "Linked Data Structure".




Where to find starter code in my-api


package.class :utils.MyQueue




Where to find the test starter code in my-api


package.class :tests.console.MyQueueTest




Where to find the JUNIT TEST code in my-api


package.class :tests.junit.MyQueueJUnitTest




Task Check List



  • ONLY "for" loops should be used within the data structure class. There is anautomatic 30% deduction,if other loops are used.

  • The names of identifiers MUST match the names listed in the description below. Deductions otherwise.

  • The Node class must be generic and a nested class within MyQueue.

  • Complete coding Assignment in your "my-api"GitHub Repository. You will not be graded otherwise and will receive a 0, if not uploaded there.

  • Run JUNIT TEST and take a SNAPSHOT of results. Upload PDF of snapshot of yourJUnitTest results to Canvas.




Building A Queue Data Structure


Create a generic class for a "Queue" data structure (FIFO) with the following methods:




































Method



Description



Example



add(item)



places given element at back of queue.



queue.add("Tom");



remove()



removes element from front of queue and returns it.Throws aNoSuchElementException, if queue is empty.



queue.remove();



peek()



returns front element from queue without removing it from the queue, returnsnull, if queue is empty.



queue.peek();



size()



returns number of elements in queue.



queue.size();



isEmpty()



returns true, if queue has no elements.



queue.isEmpty();





string representation: displays the contents of the queue from left (front) to right (back).


create a string representation of the queue from "front" to "back" reading left to right.


public String toString()



Node Nested Class for MyQueue


The generic MyQueue class includes a static Node class as a nested class, i.e. astatic innerclass within the Linked List class.



inner class: class inside the body of another class.


Note: This private class does not require access to instance members of the outer class, so it is declaredstatic. This means that the node object won’t be coupled to the outer class object, thus will be more optimal since it won’t require additional heap/stack memory.



data fields:



  • data: hold the data stored in each node as is of typeE.

  • next: stores the location of the next node in the list.



constructor:


A constructor that receives parameters for data, and prev and calls the second constructor.



public Node(E data)



Notice the difference in the additional content for Node from MyStack class.


A constructor that receives parameters for data, next and prev.



public Node(Node next, E data)




MyQueue



outer class: This class is used to control the linked node structures.



data fields:



  • first: stores the memory address of the first Node object of type NodeE>.

  • last: stores the memory address of the last Node object of type NodeE>.

  • size: stores how many elements are linked, i.e., how many Node objects are linked together.




constructor: uses a default constructor to initialize the data fields.



public MyQueue()




outer class methods: your methods should follow the input and output requirements in the Java Standard Library.NOTE : All methods must be implemented. Deductions apply otherwise.














































Method



Description



Example



add



places given element at back of queue and updates the number elements in queue.



public boolean add(E item)



append



a helper method to "help" the add method append data at back of queue. DOES NOT update up the number of elements in the queue.



private void append(E item)



detach



removes the node at the front of the queue and returns the deleted element. DOES NOT update up the number of elements in the queue. This is a private helper method.



private E detach()



remove



removes element from front of queue and returns it, and reduces size of queue. ThrowsNoSuchElementException, if queue is empty.



public E remove()



peek



returns front element from queue without removing it from the queue, returnsnull, if queue is empty.



public E peek()



size



returns number of elements in queue.



public int size()



isEmpty



returns true, if queue has no elements.



public boolean isEmpty()




NOTE : All methods must be implemented. Deductions apply otherwise.




Example:



Read from left to right


add order: "Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet"


front[Red, Orange, Yellow, Green, Blue, Indigo, Violet]back




Removal Example:



Read from left to right


front[Red, Orange, Yellow, Green, Blue, Indigo, Violet] back


front[Orange, Yellow, Green, Blue, Indigo, Violet] back


front[Yellow, Green, Blue, Indigo, Violet] back


front[Green, Blue, Indigo, Violet] back


Answered Same DayMay 03, 2022

Answer To: Week-02 | Stacks About Objective: The purpose of this exercise is to create a "Stack" LIFO data...

Kshitij answered on May 04 2022
91 Votes
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?