1. Use a chain of Nodes to design and create a class Queue that implements the i

Question

1. Use a chain of Nodes to design and create a class Queue that implements the interface QueueInterface<String> having the following methods:
• public void insert(E x); // E is interpreted as String in this and the following methods
• public E remove(); // if the Queue is empty, this returns null and doesn’t change anything
• public boolean empty();
• public E peek();// if the Queue is empty, this returns null
• public int size(); // you can just copy these method signatures to create QueueInterface<E>
Remember that a Node is an object that contains data as well as a reference to another Node; a Node class has the following structure:
• Attributes:
– private String data;
– private Node next;
• Constructors:
– public Node() – sets data to its "zero" or "empty" value (ie, the empty String, "") and sets next to null
– public Node(String s) – sets data equal to s and sets next to null
Define the Node class to be an inner class of Queue.
2. You must implement insert() and remove() efficiently so that insertions and deletions always take the same amount of time, regardless of how large the Queue is. To do this, provide two Queue instance variables, front and rear, which hold references to the first and last Nodes in the chain of Nodes:
• private Node front; // front and rear will be set to null if the Queue is empty
• private Node rear; // front and rear will reference the same Node if there is only 1 item
• private int size; // also needed in order to implement the QueueInterface size() method
Queue insertions take place at the rear of the Queue, and Queue removals take place at the front of the Queue. Don't forget to update front and/or rear when you insert or remove items.
3. Define Queue implementations for all of the other QueueInterface<String> methods, and define one or more constructors as appropriate, then define either a Queue main method or a separate TestQueue class that tests the various methods of your Queue – you can either ask the user to enter Strings to put into the Queue or just write them into your test program as literal Strings. Design your test program to test all 5 of the Queue methods listed in item 1.

Explanation / Answer

Hi, haven't done interfaces in a while but I think this follows your requirements. Please double-check that this approach meets your needs. I added accessors and modifiers to the Node inner class. I added some basic case handline (when front node is null i.e. queue is empty) and went with the assumption that when the very first node is inserted, both the front and rear nodes contain that value.

I made sure to add comments to explain what happens in the code when I felt it was important. For the test class, I went with the hard-coded rather than interactive testing, because it's easier.

Hope this helps, please remember to rate.

public class Queue implements QueueInterface<String>{
   
    private Node front;
    private Node rear;
    private int size;
   
    public Queue()
    {
        front = null;
        rear = null;
        size = 0;
    }

    @Override
    public void insert(String x) {
        // if this is the first element to be inserted
        // set both front and rear to this same value
        if(size == 0)
        {
            Node first = new Node(x);
            front = first;
            rear = first;
        }
        // else create a node to hold the String data
        else
        {
            Node latest = new Node(x);
            // link the current rear to this new node
            rear.setNext(latest);
            // make this new node the new rear
            rear = latest;
        }
        // increment the size
        size++;
    }

    @Override
    public String remove() {
        // if Queue not empty - then remove
        if( front != null )
        {
            // removing from the front
            Node removed = front;
            // so we take the next node in line
            // pointed to by the current front
            // and make that one the new front
            front = front.getNext();
            // update the size
            size--;
            // return data in removed node
            return removed.getData();
        }
        else
            return null;
    }

    @Override
    public boolean empty() {
        if(size == 0) // OR if ( (front==null) && (rear==null) )
            return true;
        else
            return false;
    }

    @Override
    public String peek() {
        // "see" data in front node without removing it
        if(front != null)
            return front.getData();
        else
            return null;
    }

    @Override
    public int size() {
        return size;
    }

    // inner class Node
    private class Node {

        private String data;
        private Node next;

        public Node() {
            data = "";
            next = null;
        }

        public Node(String d) {
            data = d;
            next = null;
        }

        // getters and setters (accessors and modifiers)
        public String getData()
        {
            return data;
        }

        public void setNext(Node n)
        {
            next = n;
        }
        public Node getNext()
        {
            return next;
        }
    }
}

public class TestQueue {

    public static void main(String[] args) {
       
        System.out.println("Creating a Queue...");
        Queue queue = new Queue();
        System.out.println("Testing if Queue is Empty:" + queue.empty() );
        System.out.println("Inserting 3 nodes into Queue");
        queue.insert("Node 1");
        queue.insert("Node 2");
        queue.insert("Node 3");
        System.out.println("Current Queue Size: " + queue.size());
        System.out.println("Removing front node: " + queue.remove());
        System.out.println("Current Queue Size: " + queue.size());
        System.out.println("Peeking at next front node: " + queue.peek());
        System.out.println("Current Queue Size: " + queue.size());
        System.out.println("Removing front node: " + queue.remove());
       
        System.out.println("Testing if Queue is Empty:" + queue.empty() );
        System.out.println("Removing front node: " + queue.remove());
        System.out.println("Testing if Queue is Empty:" + queue.empty() );
    }
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.