Please Create the program based on the description below as well as run the prog
ID: 3749375 • Letter: P
Question
Please Create the program based on the description below as well as run the program and answer the questions bellow.
In this assignment you'll get more practice with stacks and queues. You will also practice testing your code for edge cases.
MyStack.java
Implement a stack using linked lists data structure. Implement your own linked list. You cannot use Java's java.util.LinkedList.
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 push 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?
Explanation / Answer
I have answered this question before. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// MyStack.java
public class MyStack {
// pointer to the head node
private Node top;
// number of items on stack
private int size;
/**
* default constructor
*/
public MyStack() {
// initializing values
top = null;
size = 0;
}
/**
* constructor with argument to initialize the stack with some values
*
* @param list
* array containing values to be added
*/
public MyStack(String[] list) {
this(); // invoking default constructor
// pushing each item on the array to the stack
if (list != null) {
for (String item : list) {
push(item);
}
}
}
/**
* removes and return the top element from the stack (in O(1) time)
*/
public String pop() {
if (!isEmpty()) {
String data = top.getData();
top = top.next;
size--;
return data;
}
return null;
}
/**
* add a new item to the top of the stack (in O(1) time)
*/
public void push(String item) {
Node node = new Node(item);
if (top == null) {
top = node;
} else {
node.setNext(top);
top = node;
}
size++;
}
/**
* return true if the stack is empty
*/
public boolean isEmpty() {
return size == 0;
}
/**
* method to print the stack contents
*/
public void printStack() {
Node node = top;
System.out.print("[");
while (node != null) {
System.out.print(node.getData());
node = node.next;
if (node != null) {
System.out.print(", ");
}
}
System.out.println("]");
}
/**
* a private class inside MyStack.java to represent one node in the linked
* list representation of the stack
*/
private class Node {
String data;
Node next;
public Node(String data) {
this.data = data;
}
public void setData(String data) {
this.data = data;
}
public String getData() {
return data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return next;
}
}
}
// MyQueue.java
public class MyQueue {
// using a MyStack as the data container
private MyStack stackQueue;
/**
* default constructor
*/
public MyQueue() {
stackQueue = new MyStack();
}
/**
* constructor with argument to initialize the queue with some values
*
* @param list
* array containing values to be added
*/
public MyQueue(String list[]) {
this();
if (list != null) {
for (String item : list) {
enqueue(item);
}
}
}
/**
* method to add a new item to the back of the queue
*
* @param item
* item to be added.
* @Note that inorder to use a Stack as the queue, we need to compromise the
* cost of either enqueue or dequeue operation, here, I make enqueue
* operation more costly because it involves removing all the elements
* from current stack to a temporary stack, add the new item, and then
* move all elements from temp stack to old stack. The primary goal is
* to reverse the stack inorder to add a new item (it may take O(2n)
* time )
*/
public void enqueue(String item) {
// defining a temporary stack
MyStack tempStack = new MyStack();
// removing and adding all elements of queue stack to temp stack
while (!isEmpty()) {
tempStack.push(stackQueue.pop());
}
// adding new element to the temp stack
tempStack.push(item);
// removing and adding all elements of temp stack to queue stack
while (!tempStack.isEmpty()) {
stackQueue.push(tempStack.pop());
}
}
/**
* removes an item from the front of the queue and returns it As we made
* enqueue operation costly, we can make dequeue operation quick (O(1) time
* complexity)
*/
public String dequeue() {
return stackQueue.pop();
}
/**
* method to print the queue
*/
public void printQueue() {
/**
* as we created printStack() method in MyStack to print contents of the
* stack without any extra labels or headers, we can use it to print the
* queue contents
*/
stackQueue.printStack();
}
public boolean isEmpty() {
return stackQueue.isEmpty();
}
}
// MyTest.java
public class MyTest {
public static void main(String[] args) {
/**
* testing all methods of MyStack and MyQueue classes.
*/
MyStack stack = new MyStack(new String[] { "a", "b", "c" });
System.out.println("Testing MyStack with initial values:");
stack.printStack();
System.out.println(stack.pop() + " is popped from stack");
stack.printStack();
stack.push("x");
System.out.println("x is pushed to stack");
stack.printStack();
System.out.println("Is empty? " + stack.isEmpty());
System.out.println("Popping until stack is empty");
while (!stack.isEmpty()) {
System.out.println(stack.pop() + " is removed");
}
System.out.println("Is empty? " + stack.isEmpty());
MyQueue queue = new MyQueue(new String[] { "x", "y", "z" });
System.out.println(" Testing MyQueue with initial values:");
queue.printQueue();
System.out.println(queue.dequeue() + " is dequeued from queue");
queue.printQueue();
queue.enqueue("s");
System.out.println("s is enqeued to the queue");
queue.printQueue();
System.out.println("Is empty? " + queue.isEmpty());
System.out.println("Dequeuing until queue is empty");
while (!queue.isEmpty()) {
System.out.println(queue.dequeue() + " is removed");
}
System.out.println("Is empty? " + queue.isEmpty());
}
}
/*OUTPUT*/
Testing MyStack with initial values:
[c, b, a]
c is popped from stack
[b, a]
x is pushed to stack
[x, b, a]
Is empty? false
Popping until stack is empty
x is removed
b is removed
a is removed
Is empty? true
Testing MyQueue with initial values:
[x, y, z]
x is dequeued from queue
[y, z]
s is enqeued to the queue
[y, z, s]
Is empty? false
Dequeuing until queue is empty
y is removed
z is removed
s is removed
Is empty? true