Question

(a) Write a stack class that is based on a linked list. It can be just pop(), push(), and anything you need for those methods or testing.

(b) Write a queue class that is based on a linked list. As above, it can be just enqueue() and dequeue(), as well as anything you need for those methods or testing.

(c) Write some test cases, trying to include edge cases. Why did you choose those tests? Did you get the results you expected?

Answer 1

save the file name as LinkedList.java before compiling for both the parts

(A) Stack class based on a linkedlist with functions to pop() and push() with cornor case testing

public class LinkedList {

// defining the linkedlist with node and value
   public Node head;
   public class Node {
       int value;
       Node next;
       public Node(int value) {
           this.value = value;
           this.next = null;
       }
   }
// function to push elements to stack
   public void push(int data) {
       Node temp = new Node(data);
       temp.next = this.head;
       this.head = temp;
   }
  

//function to pop elements from stack
   public int pop() {

//if the stack is empty and you use pop funtion the function will return -1

if(this.head==null){
return -1;
   }
       int popValue = this.head.value;
       this.head = this.head.next;
       return popValue;
   }
  
   public static void main(String[] args) {
       LinkedList linkedList = new LinkedList();
       linkedList.head = null;
      
       linkedList.push(1);
       linkedList.push(2);
      
       System.out.println(linkedList.pop());
       System.out.println(linkedList.pop());
       System.out.println(linkedList.pop()); // edge case when there is nothing in the stack
   }
  
}

(B) Queue class based on linked list with queue() and deque() funtions with cornor case testing

public class LinkedList {
   public Node head;
   // defining the linkedlist with node and value
   public class Node {
       int value;
       Node next;
       public Node(int value) {
           this.value = value;
           this.next = null;
       }
   }
  

// function to enqueus elements to queue
   public void queue(int data) {
       if(this.head==null){
   this.head = new Node(data);
   return;
   }
       Node temp = this.head;
       while(temp.next!=null) {
           temp = temp.next;
       }
       Node newNode = new Node(data);
       temp.next = newNode;
   }

// function to dequeue elements from queue
  
   public int deque() {

// is head is already empty and then you deque element it will return -1
       if(this.head==null){
   return -1;
   }
       int dequeValue = this.head.value;
       this.head = this.head.next;
       return dequeValue;
   }
  
   public static void main(String[] args) {
       LinkedList linkedList = new LinkedList();
       linkedList.head = null;
      
       linkedList.queue(1);
       linkedList.queue(2);
System.out.println(linkedList.deque());
       System.out.println(linkedList.deque());

System.out.println(linkedList.deque()); // dequeeing with no elements in the queue will return -1 i.e. cornor case
          }
   }

(C)

Test cases

Stack

linkedList.push(1);

linkedList.push(2);

linkedList.pop();

linkedList.pop();

linkedList.pop(); // cornor case will return -1 since no elements in stack

Queue

linkedList.queue(1);

linkedList.queue(2);

linkedList.deque()

linkedList.deque()

linkedList.deque() // cornor case will return -1 since no elements in queue