Question

The language is Java.

Using a singly-linked list, implement the four queue methods enqueue(), dequeue(), peek(), and isEmpty(). For this assignment, enqueue() will be implemented in an unusual manner. That is, in the version of enqueue() we will use, if the element being processed is already in the queue then the element will not be enqueued and the equivalent element already in the queue will be placed at the end of the queue. Additionally, you must implement a circular queue. The program's input will be a single string that consists of single-character elements. You program will process each character in the string according the descriptions below. "->" signifies the front of the queue.

1) 'A' - 'Z': Puts the character on the queue.

Input: ABCD Output: nothing will be outputted

Input: ABCDA* Output: B C D A

2) '*': displays the elements of the queue separated by a space

Input: ABCD* Output: -> A B C D

3) '$': prints the element at the front of the queue

Input: ABCD$ Output: peek: A

4) '#': empties out the queue

Input: ABCD#* Output: ->

5) '!': deletes an element from the queue

Input: ABCD!* Output: -> B C D

6) all other characters: prints an error message for each element, does not put the element in the queue and clears the queue.

Input: a Output: The illegal character 'a' was encountered in the input stream.

Rules:

1. You can not delete any code in the Queue class.
2. If you need additional methods you must add them to the MyQueue class.
3. If you do not need any additional methods then you can delete the myQueue class.
4. You must use a singly-linked list with only a rear pointer.
5. Do not assume any maximum length for any input string.
6. You need not test for the null or empty string ("") cases.
7. You are not allowed to add any arrays or ArrayLists or any Java built-in (ADTs), such as Lists, Sets, Maps, Stacks, Queues, Deques, Trees, Graphs, Heaps, etc. Or add any class that inherits any of those ADTs.
8. You are not allowed to use Java Generics.

Starter code which must be used, can only be changed if rules stated above allow it:

import java.util.Scanner; // Import the Scanner class

public class Homework1 {
  
public static void main(String[] args) {
// place your solution here
}

}

class SLLNode {
  
public char data;
public SLLNode next;

public SLLNode(char c) {
data = c;
next = null;
}

}

class Queue {
  
public SLLNode rear;
  
public Queue() {
// place your solution here
}
  
public void enqueue(char c) {
// place your solution here
}
  
public SLLNode dequeue() {
// place your solution here
}
  
public char peek() {
// place your solution here
}
  
public boolean isEmpty() {
// place your solution here
}

}
  
class MyQueue extends Queue {
// place any additional code you need in this class   
}

Answer 1

Complete code in java:-

import java.util.Scanner; // Import the Scanner class

public class Homework1 {
  
   public static void main(String[] args) {
       // place your solution here
       // Create Scanner object to take user input.
       Scanner sc = new Scanner(System.in);
       System.out.print("Input: ");
       String input = sc.nextLine();
       // Create empty queue.
       Queue queue = new Queue();
       System.out.print("Output: ");
       // This for loop will parse the input string
       // And will take appropriate action for each character
       for(int i = 0; i < input.length(); i++) {
           char c = input.charAt(i);
           // If Upper case character, push into the queue.
           if(c >= 'A' && c <= 'Z') {
               queue.enqueue(c);
           }
           // Print all elements of the queue.
           else if(c == '*') {
               SLLNode temp = queue.rear;
               do {
                   if(temp == null) {
                       break;
                   }
                   System.out.print(temp.data+" ");
                   temp = temp.next;
               }while(temp != queue.rear);
           }
           // Printing peek element of queue.
           else if(c == '$') {
               System.out.print(queue.peek());
           }
           // Delete queue.
           else if(c == '#') {
               queue.rear = null;
           }
           // Pop out an element from queue.
           else if(c == '!') {
               queue.dequeue();
           }
           else {
               System.out.println("\nThe illegal character "+c+" was encountered in the input stream.");
               break;
           }
       }
       System.out.println();
   }
}

class SLLNode {
  
   public char data;
   public SLLNode next;

   public SLLNode(char c) {
       data = c;
       next = null;
   }

}

class Queue {
  
   public SLLNode rear;
  
   public Queue() {
       // place your solution here
       // Initializing rear as 'null', Empty queue.
       this.rear = null;
   }
  
   public void enqueue(char c) {
       // place your solution here
       // If currently queue is empty.
       if(this.rear == null) {
           this.rear = new SLLNode(c);
           this.rear.next = this.rear;
       }
       // If queue is not empty.
       else {
           SLLNode temp = this.rear;
           SLLNode prev = null;
           // If character is already present in queue, remove it.
           do{
               if(temp.data == c) {
                   // If character is same present on top of the queue,
                   // Just put it back into the queue.
                   if(prev == null) {
                       this.rear = this.rear.next;
                       return;
                   }
                   // Delete it, from the queue.
                   else {
                       prev.next = temp.next;
                   }
                   break;
               }
               prev = temp;
               temp = temp.next;
           }while(temp != this.rear);

           // Add this character again in queue, at back.
           temp = new SLLNode(c);
           temp.next = this.rear;
           prev = this.rear;
           while(prev.next != this.rear) {
               prev = prev.next;
           }
           prev.next = temp;
       }
   }
  
   public SLLNode dequeue() {
       // place your solution here
       // If queue size is 1
       // Make rear point to 'null'.
       if(this.isEmpty()) {
           return null;
       }
       SLLNode temp = this.rear;
       if(this.rear.next == this.rear) {
           this.rear = null;
       }
       // Else remove element from the top of the queue.
       else {
           this.rear = this.rear.next;
           SLLNode temp1 = this.rear;
           while(temp1.next != temp){
               temp1 = temp1.next;
           }
           temp1.next = this.rear;
       }
       return temp;
   }
  
   public char peek() {
       // place your solution here
       return this.rear.data;
   }
  
   public boolean isEmpty() {
       // place your solution here
       return (this.rear == null);
   }
}

Screenshot of output:-