Part B Stacks and Queues LinkedList verus Growable Arrays in

Part B: Stacks and Queues, Linked-List verus Growable Arrays

interface Queue{

              void Enqueue(int n);

              int Dequeue();

              int length();

}

interface Stack{

              void Push (int n);

              int Pop();

              int length();

}

Given the following interfaces for Stacks and Queues, implement each interface in two ways: using a Linked-List and a Stack. (That means, a total of FOUR implementations is needed. E.g., Queue using Linked-List & Queue using Growable Array. Provide a short paragraph of your observation once you have completed all the implementation. Use the following class names MyStack1, MyStack2, MyQueue1, MyQueue2 in your code.

Java

Solution

import java.util.ArrayList;
import java.util.List;

public class MyStack1 implements Stack{
  
   List<Integer> a = new ArrayList<Integer>();
  
   public void Push(int n){
       a.add(0,n);
   }
  
   public int Pop(){
       return a.remove(0);
   }
  
   public int length(){
       return a.size();
   }
  

}

//--------------------------------------------------------------------------------------

//Linked List
public class MyStack2 implements Stack{
  
   class Node {
       int value;
       Node next;
       public int getValue() {
           return value;
       }
       public void setValue(int value) {
           this.value = value;
       }
       public Node getNext() {
           return next;
       }
       public void setNext(Node next) {
           this.next = next;
       }  
      
   }
  
   Node s = null; // start node
  
   public void Push(int n){
       Node n1 = new Node();
       n1.setValue(n);
       n1.setNext(null);
      
       if(s == null) s = n1;
       else {
           n1.setNext(s);
           s = n1;
       }          
   }
  
   public int Pop() {
       if(s == null){
           return -1; //error if stack is empty
       }
       else
       {
           int n = s.getValue();
           s = s.getNext();
           return n;
       }
   }
  
   public int length() {
      
       int n = 0;
       Node t = s;
       while(t != null){
           n++;
           t = t.getNext();
          
       }
       return n;
   }

}

//----------------------------------------------------------------------------------------------

import java.util.ArrayList;
import java.util.List;

public class MyQueue1 implements Queue{
  
   List<Integer> a = new ArrayList<Integer>();
  
   public void Enqueue(int n){
       a.add(n);
   }
  
   public int Dequeue(){
       return a.remove(0);
   }
  
   public int length(){
       return a.size();
   }

}

//-------------------------------------------------------------------------------------------

//Linked List
public class MyQueue2 implements Queue{

   class Node {
       int value;
       Node next;
       public int getValue() {
           return value;
       }
       public void setValue(int value) {
           this.value = value;
       }
       public Node getNext() {
           return next;
       }
       public void setNext(Node next) {
           this.next = next;
       }
      
   }
  
   Node s = null; // start node
  
   public void Enqueue(int n){
      
       Node n1 = new Node();
       n1.setValue(n);
       n1.setNext(null);
      
       if(s == null) s = n1;
       else {
           Node t = s;
           while(t.getNext() != null){
               t = t.getNext();
           }
           t.setNext(n1);
       }
      
   }
  
   public int Dequeue(){
      
       if(s == null) return -1; //error empty queue
      
       int n = s.getValue();
       s = s.getNext();
       return n;
   }
  
   public int length() {
      
       int n = 0;
       Node t = s;
       while(t != null){
           n++;
           t = t.getNext();
          
       }
       return n;
   }
}