CODEWITHSUNDEEP
javadata-structures
Anuj Mehta
Anuj Mehta

Reputation: 1138

Creating a Queue that does not allow duplicate elements and should allow index based retrieval

I want to create a Queue which should not allow duplicate elements and I should be able to access elements of this queue based on index. Please let me know how should I implement this?

Upvotes: 4

Views: 13598

Answers (4)

Anuj Mehta
Anuj Mehta

Reputation: 1138

I am planning to use ConcurrentLinkedQueue for my problem. Here is the sample code

import java.util.concurrent.ConcurrentLinkedQueue;


public class FinalQueue {

    private ConcurrentLinkedQueue<String> queue;

    public FinalQueue()
    {
        queue = new ConcurrentLinkedQueue<String>();
    }

    public synchronized void enqueue(String ipAddress)
    {
        if(!queue.contains(ipAddress))
            queue.add(ipAddress);
    }

    public String dequeue()
    {
        return queue.poll();
    }

    public String toString()
    {
        return "" + queue;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        FinalQueue queue = new FinalQueue();
        queue.enqueue("1.2.3.4");
        queue.enqueue("2.3.4.5");
        queue.enqueue("1.1.1.1");
        queue.enqueue("1.2.3.4");
        System.out.println(queue.toString());
        System.out.println("Dequeue..." + queue.dequeue());
        System.out.println("Dequeue..." + queue.dequeue());
        System.out.println(queue.toString());
    }
}

Upvotes: 1

fkl
fkl

Reputation: 5535

Don't call it a queue because by definition a queue only is a first in first out data structure.

Depending upon your input values, i believe you should use an array and a hash function. The hash determines which index an element is located using its value and vice versa i.e. when given an index it returns the value contained in it.

Since you are using a hash, the repetition is avoided when a collision occurs i.e. you can check if a value previously existed in an index and if it's the same value or not.

C++ stl has a good class for set though java i don't think have one. But the point is set does not offer index based retrieval.

Upvotes: 0

anubhava
anubhava

Reputation: 784878

Well it is clear that Java doesn't have the exact data structure matching your specification and requirement. The closest that can match your requirement is probably a LinkedHashSet. It is basically a Set (matching your unique items requirement) whose elements are kept in insertion-order (like a Queue) and to get an element by index you can use set.toArray() to get an array or create a list out of the set (however it will cost cost some extra memory).

Upvotes: 5

jrad
jrad

Reputation: 3190

You could always just use an ArrayList. It's good for accessing elements based on index and when adding elements you can always just check if the ArrayList contains the element to be added. My initial instinct was to use a Set for the disallowing of duplicates, but the elements are Sets are not indexed. If you can find a way to index the elements in Sets, then that would be my recommendation.

Upvotes: 0

Related Questions