Please make and run the program as well. MyStack.java Implement a stack using li
ID: 3748975 • Letter: P
Question
Please make and run the program as well.
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
// Solution
//MyStack.java:
public class MyStack {
private Node head; // the first node
private class Node {
String data;
Node next;
}
public MyStack() {
head = null;
}
public MyStack(String[] list) {
for(String s : list) {
push(s);
}
}
public String pop() throws Exception {
if(!isEmpty()) {
String value = head.data;
head = head.next;
return value;
} else {
throw new Exception("Stack is empty");
}
}
public boolean isEmpty() {
if (head == null) {
return true;
}
return false;
}
public void push(String value) {
Node oldHead = head;
head = new Node();
head.data = value;
head.next = oldHead;
}
public static void main(String args[]) throws Exception
{
MyStack myStack=new MyStack();
myStack.push("20");
myStack.push("50");
myStack.push("80");
myStack.push("40");
myStack.push("60");
myStack.push("75");
System.out.println("Element removed from LinkedList: "+myStack.pop());
System.out.println("Element removed from LinkedList: "+myStack.pop());
myStack.push("10");
System.out.println("Element removed from LinkedList: "+myStack.pop());
myStack.printStack();
}
public void printStack() {
Node temp = head;
while (temp != null) {
System.out.format("%s ", temp.data);
temp = temp.next;
}
System.out.println();
}
public int size() {
Node temp = head;
int c = 0;
while (temp != null) {
c++;
temp = temp.next;
}
return c;
}
}
//Output:
Element removed from LinkedList: 75
Element removed from LinkedList: 60
Element removed from LinkedList: 10
40 80 50 20
What is the runtime MyStack's push method
It is O(1). It means constant time. Because we are inserting at the beginning which modifies head to new node. So only constant operations.
//MyQueue.java:
public class MyQueue
{
MyStack myStack = new MyStack();
void enqueue(String val) throws Exception
{
int size = myStack.size();
myStack.push(val);
for (int i = 0; i < size; i++)
{
String x = myStack.pop();
myStack.push(x);
}
}
String dequeue() throws Exception
{
if (myStack.isEmpty())
{
System.out.println("No elements");
return "";
}
String x = myStack.pop();
return x;
}
boolean isEmpty() {
return myStack.isEmpty();
}
public static void main(String[] args) throws Exception
{
MyQueue s = new MyQueue();
System.out.println("Inserting 10");
s.enqueue("10");
System.out.println("Inserting 20");
s.enqueue("20");
System.out.println("Displaying Queue");
s.printQueue();
System.out.println("Dequeuing");
s.dequeue();
s.printQueue();
System.out.println("Inserting 30");
s.enqueue("30");
System.out.println("Dequeuing");
s.dequeue();
System.out.println("Displaying Queue");
s.printQueue();
}
private void printQueue() {
myStack.printStack();
}
}
// Output:
Inserting 10
Inserting 20
Displaying Queue
20 10
Dequeuing
10
Inserting 30
Dequeuing
Displaying Queue
10
What is the runtime MyQueue's dequeue method, in Big O
O(1) as we pop the top element. Constant operation.
What is the space complexity of MyQueue,:
O(n) as we need to store queue elements.