CODEWITHSUNDEEP
javaqueue
Tersely
Tersely

Reputation: 1

How can I obtain the number of times a number appears in a queue (Java)?

So let's say we have a queue that can store any integer inside it.

What I needed to do (for a test), was write a function that would create (and return) a new queue without leaving the original one changed.

You could change it, but at the end of the function it would have to be as it was in the beginning

Let's assume that the only methods in class Queue are:

In the new queue we would have each integer and after it the number of times it appeared in the first queue.

Aside from the initial queue I could use: Stack(s), Array(s), new Queue(s) and possibly LinkedList(s).

Writing new functions can be done as well.

The straight up solution (I guess) would be to copy the first queue in any method, and then use while(!isEmpty) and a counter for the number which would then be added to the desired queue and removed from the copied one.

I don't have this written down at the moment but I can't really think of a cleaner and more efficient method of doing this, so any help would be appreciated. Thanks.

Upvotes: 0

Views: 2013

Answers (2)

Vinicius Victor
Vinicius Victor

Reputation: 358

You're probably able to come up with a better solution with some time, but this is what I did:

public static Queue<Integer> countQueue(Queue<Integer> q) {
    LinkedList<Integer> valuesList = new LinkedList<>();
    // since we can't iterate on the Queue
    // we remove the head element
    while(!q.isEmpty()) {
        int x = q.remove();
        valuesList.add(x);
    }

    LinkedList<Integer> nonRepeated = new LinkedList<>();
    LinkedList<Integer> timesCount = new LinkedList<>();

    while(!valuesList.isEmpty()) {
        int value = valuesList.remove();
        q.add(value); // get the original queue back
        int index = nonRepeated.indexOf(value);
        if (index == -1) {
            nonRepeated.add(value);
            timesCount.add(1);
        } else {
            timesCount.set(index, timesCount.get(index)+1);
        }
    }
    Queue<Integer> output = new ArrayDeque<>();
    while(!nonRepeated.isEmpty()) {
        output.add(nonRepeated.remove());
        output.add(timesCount.remove());
    }

    return output;
}

If you're interested on creating a method to get the Queue's size, this might be one of the simplest solutions:

public static int getQueueSize(Queue<Integer> q) {
    int i=0;
    Queue<Integer> backupQueue = new ArrayDeque<>(); 
    while(!q.isEmpty()) {
        i++;
        backupQueue.add(q.remove());
    }
    while(!backupQueue.isEmpty())
        q.add(backupQueue.remove());
    return i;
}

Whenever using Queues, Stacks and etc., you'll need to pay attention to the data structure's paradigm, such as FIFO(First in First out) and LIFO(Last in First out), which will dictate how you should iterate on the structure.

Upvotes: 1

Rodrigo
Rodrigo

Reputation: 517

Idea: iterate through queue and re-add the elements to it as you do. Keep a map to store the counts of each element. Then convert the map into a queue.

Something like this (untested):

public Queue<Integer> count(Queue<Integer> input) {
  int size = input.size();
  Map<Integer, Integer> counts = new HashMap<>();
  for (int i = 0; i < size; i++) {
      Integer element = input.remove(); // take from front of queue.
      if (!counts.contain(element)) {
          counts.put(element, 1);
      } else {
          counts.put(element, counts.get(element) + 1);
      }
      input.add(element); // now it's in the back of the queue.
  }

  // convert map to queue.
  Queue<Integer> output = new Queue<>();
  for (Integer key : counts.keySet()) {
      output.add(key);
      output.add(counts.get(key));
  }
  return output;

Note that the output won't contain the integers in the same order... But maintaining order was not part of the problem statement. If it is, you can think of other data structures to keep your counts in.

Upvotes: 0

Related Questions