MyStack.java Implement a stack using linked lists data structure pop(): returns
ID: 3743955 • Letter: M
Question
MyStack.java
Implement a stack using linked lists data structure
pop(): returns and removes the last value on the stack
push(String item): Push a given value onto the stack
isEmpty(): returns true or false depending on if the stack is empty
printStack(): prints the items on the stack to console
Handles errors for all possible edge cases (i.e. doesn’t throw an unhandled exception to the user)
MyStack(String[] list): constructor which creates the stack with the items in list on the stack. So if list had {“a”, “b”, “c”} the stack would look like: “c” on top of “b” on top of “a.”
MyQueue.java
Implement a queue using the MyStack.java implementation as your data structure. In other words, your instance variable to hold the queue items will be a MyStack class.
enqueue(String item): inserts item into the queue
dequeue(): returns and deletes the first element in the queue
isEmpty(): returns true or false depending on if the queue is empty
printQueue(): prints the items in the queue to console
MyQueue(String[] list): constructor which creates the queue with the items in list in the queue: So if list had {“a”, “b”, “c”} the queue would look like: “a” first, then “b”, then “c.”
MyTest.java
You can have other methods in this class but will be graded to have a:
Main method which tests every method you implemented above in MyStack and MyQueue.
As you test the methods, print to console (1) what you are testing, (2) what value you are expecting, (3) whether your test passed or failed.
Test for edge cases and clearly state in your comment/print out which edge case you’re testing.
Console.pdf
This file has the print out from the main method in MyTest.java
Also include an answer to the following questions:
1) Show an example screenshot of how you used the debugger in fixing your code with a short description on explaining the bug and how you fixed it.
2) What is the runtime MyStack's dequeue method, in Big O?
3) What is the runtime MyQueue's dequeue method, in Big O?
4) What is the space complexity of MyQueue, in Big O?
Rubric
Explanation / Answer
package DS;
//Class MyStack definition
public class MyStack
{
// Instance variables to store data
private String [] stackArray;
private int top;
// Parameterized constructor to initialize data
public MyStack(String[] list)
{
stackArray = new String[list.length];
top = -1;
for(int x = 0; x < list.length; x++)
push(list[x]);
}// End of parameterized constructor
// Method to insert data
public void push(String item)
{
// Increase the top position by one.
// Stores the data in top index position
stackArray[++top] = item;
}// End of method
// Method to delete data
public String pop()
{
// Returns the top index position data and then decrease the top by one
return stackArray[top--];
}// End of method
// Method to check stack is empty or not
public boolean isEmpty()
{
// Returns true if top is -1 otherwise return false
return (top == -1);
}// End of method
// Method to display stack contents
public void printStack()
{
// Loops till stack is not empty by calling isEmpty() method
while(!isEmpty())
// Displays the top item from the stack by calling pop() method
System.out.print(pop() + ", ");
}// End of method
}// End of class
-------------------------------------------------------------
package DS;
// Class MyQueue definition
public class MyQueue
{
// Instance variables to store data
private String [] queArray;
private int front;
private int rear;
// Parameterized constructor to initialize data members
public MyQueue(String list[])
{
// Sets the array size to length of the list
queArray = new String [list.length];
// Sets the front and rear to -1
front = -1;
rear = -1;
// Loops till length of the list
for(int x = 0; x < list.length; x++)
// Calls the method enqueue() with list x index position item
enqueue(list[x]);
}// End of parameterized constructor
// Insert the items at the rear end of the queue
public void enqueue(String item)
{
// Increase the rear by one
// Add the data at rear index position of the queue
queArray[++rear] = item;
}// End of method
// Deletes an data from the front of the queue and return the deleted item
public String dequeue()
{
// Stores the front index position data of queue in temp and increase the front by one
String temp = queArray[++front];
// Returns the deleted data
return temp;
}// End of method
// Returns true if the queue is empty otherwise false
public boolean isEmpty()
{
return (front == rear);
}// End of method
// Displays the contents of queue
public void printQueue()
{
// Loops till queue is not empty by calling isEmpty() method
while(!isEmpty())
// Displays the front item from the queue
System.out.print(dequeue() + ", ");
}// End of method
}// End of class
----------------------------------------------------------------
package DS;
// Defines driver class MyTest
public class MyTest
{
// main method definition
public static void main(String ss[])
{
// Creates a string list
String list[] = {"a", "b", "c"};
// Creates an object of the class MyStack using parameterized constructor
// Passing list array
MyStack stack = new MyStack(list);
System.out.println(" ***************** STACK ***************** ");
// Calls the method to display the stack
stack.printStack();
// Creates an object of the class MyQueue using parameterized constructor
// Passing list array
MyQueue queue = new MyQueue(list);
System.out.println(" ***************** QUEUE ***************** ");
// Calls the method to display the queue
queue.printQueue();
}// End of main method
}// End of driver class
Sample Output:
***************** STACK *****************
c, b, a,
***************** QUEUE *****************
a, b, c,
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.