[Solved]Java Queue First First Fifo Data Structure Assignment Implementing Queue Determine String Q37149511

Java: A queue is a First-In First-Out (FIFO) data structure. Inthis assignment, you will be implementing a
queue to determine if a string belongs to a language. Here is theproblem you are to solve using a
queue: L = {w$w | w is a an empty string or a string of charactersother than $ }
That is, the language L is the set of all strings which follow thepattern of w$w, where w is an empty
string (ex: “”) OR a string of characters other than $ (ex: ba). A$ symbol lies in-between w and w.
The table below shows examples of accepted and rejected strings forlanguage L.

AcceptReject$abc$cbaabc$abcgfffa$afffg3333$3333a$a$$$

Explore the code files provided. You will only be coding insidetwo files: BasicQueue and
StringRecognizer.
Update all necessary methods inBasicQueue by following the provided comments. Remember, the
BasicQueue is reference-based! (think linked lists!)
Once you have updated BasicQueue, complete StringRecognizer byfollowing the provided
comments. (Hint: You MUST make an instance of BasicQueue to use thequeue
operations/methods you created in step 5.)
—————————————————————

package Interfaces;

public interface BasicQueueInterface {
   public boolean isEmpty();
   public int getSize();
   public void enqueue(char newItem);
   public char dequeue();
}

—————————————————————

package Interfaces;

public interface StringRecognizerInterface {
   boolean recognizeString(String s);
}

—————————————————————

package Queue;
import Interfaces.BasicQueueInterface;

// an implementation of a reference-based char queue

public class BasicQueue implements BasicQueueInterface
{

   private static final char NULL_CHAR =’u0000′;
   private Node head = null;   // reference tothe first node in the queue
   private Node tail = null;   // an optional(but recommended) reference to the last node in the queue
   private int count = 0;      // keeps track of the number of chars in the queue (initialized to0 because queue starts empty)

   // if the queue has no chars in it, returntrue
   public boolean isEmpty()
   {
       return false;
   }

   // return the number of chars in the
   public int getSize()
   {
       return 0;
   }

   // adds a node to the end of the queue
   public void enqueue(char c)
   {
       // new node to be added to thequeue
       Node n = new Node(c);
      
       /*
       * TODO:
       *    1.) (special case)Check if the queue is empty using isEmpty(), if it is both the headand tail should reference Node n.
       * 2.) Otherwise, tail’s next shouldreference Node n.
       * 3.) Tail should now referenceNode n.
       */
   }

   // returns the head of the queue (if its notempty), and moves the head to the next node in the queue
   public char dequeue()
   {
       // if the queue is empty, tell theuser and return the null character
       if(isEmpty())
       {
          System.out.println(“Error: Cannot dequeue because the queue isempty!”);
           returnNULL_CHAR;
       }
       /*
       * TODO:
       *    1.)  Store the char of the head node in a new temporary variable.
       * 2.) Move the head reference tothe next node in the queue.
       * 3.) Decrease the count.
       * 4.) If you are using the tailreference: If the queue is now empty (use isEmpty()) the head andtail should be null.
       * 5.) Return the temporaryvariable.
       *
       */
       return ‘A’;
   }

}

—————————————————————

package Queue;

public class Node
{
  
   private Node next;
   private char letter;
  
   // a new node must be assigned a char value
   public Node(char letter)
   {
       this.letter = letter;
   }
  
   // sets the node’s next reference
   public void setNext(Node n)
   {
       next = n;
   }
  
   // gets the node’s next reference
   public Node getNext()
   {
       return next;
   }
  
   // returns the char value of the node
   public char getChar()
   {
       return letter;
   }
}

—————————————————————

//////I have implemented using queue.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

import Interfaces.BasicQueueInterface;
import Interfaces.StringRecognizerInterface;

public class StringRecognizer implementsStringRecognizerInterface,BasicQueueInterface {
   Queue q = new LinkedList(); //defining Queue ofLinkedList Class
public boolean recognizeString(String s) {
/*
* s = input string for testing
* This method should return true if s is in the language L = {w$w |w is a an empty string or a string of characters other than$}
* otherwise return false.
*/
   if (s.indexOf(‘$’)<0){ //Checking the $ is there ornot if not acceptable
       return false;
   }
   else{
       StringBuilder input1 = newStringBuilder();
   // append a string into StringBuilder input1
   input1.append(s);
  
   // reverse StringBuilder input1
   input1 = input1.reverse();
   // print reversed String
   for(int i=0;i       if(q.poll()!=input1.toString().charAt(i)){ //poll it returns headelement and if it matches reverse of string char by // //char thenit is true.
           returnfalse;
       }
   }return true;

   }
}

—————————————————————

import java.io.BufferedReader;
import java.io.InputStreamReader;

import Interfaces.*;
import Queue.BasicQueue;

public class StringTest {
   // you need change this value if you want to test morevalues
   private static final int TEST_ITEMS = 5;
   public static void main(String[] args) {
       BasicQueueInterface bqi = newBasicQueue();
       StringRecognizerInterfacerecognizer = new StringRecognizer();
       StringTest.testQueue(bqi);
      StringTest.testString(recognizer);
   }

   private static voidtestString(StringRecognizerInterface recognizer) {
       // test if queue works. Comment outif working properly.
       String input = getInput();
       boolean solution =recognizer.recognizeString(input);
       if (solution)
       {
          System.out.print(“input is in language w$w”);
       }
       else
       {
          System.out.print(“input is not in language w$w”);
       }
   }

   // asks and gets input from user, then shows theuser what they entered
   private static String getInput() {
       InputStreamReader isr = newInputStreamReader(System.in);
       BufferedReader br = newBufferedReader(isr);
       String lines = null;
       System.out.print(“Please type astring for testing in language w$w:”);
       try {
           lines =br.readLine();
       } catch (Exception e) {
          System.out.print(“Not a valid inputn”);
       }
       System.out.println(“input is:” +lines);
       return lines;
   }

   // tests if queue works properly…
   private static void testQueue(BasicQueueInterface bqi){
       System.out.println(“QueueTest:n”);
       Character items[] = newCharacter[TEST_ITEMS];
       for (int i = 0; i < TEST_ITEMS;i++)
       {
           items[i] = newCharacter((char) (i + 65));
          bqi.enqueue(items[i]);
          System.out.println(“Enqueue: ” + items[i] + “nSize: ” +bqi.getSize() + “n”);
       }
       System.out.println();
       while (!bqi.isEmpty())
       {
          System.out.println(“Dequeue: ” + bqi.dequeue() + “nSize: ” +bqi.getSize() + “n”);
       }
   }

}

ˇ HomeworkBoost JRE System Library [JavaSE-1.8] ˇ罗src (default package) ˇ StringRecognizer.java StringTest.java ˇ串Interfaces >团BasicQueueInterface.java >团StringRecognizerInterface.java ˇ Queue >」BasicQueue,java Node.java Show transcribed image text ˇ HomeworkBoost JRE System Library [JavaSE-1.8] ˇ罗src (default package) ˇ StringRecognizer.java StringTest.java ˇ串Interfaces >团BasicQueueInterface.java >团StringRecognizerInterface.java ˇ Queue >」BasicQueue,java Node.java

Expert Answer

---

Answer to Java: A queue is a First-In First-Out (FIFO) data structure. In this assignment, you will be implementing a queue to det… . . .