Queue Circular Array loop

Question

Let's say that I have an Array of size [10] and when that array get's filled up I want to implement a FIFO structure instead of it just being full and therefore not able to add new stuff to the array and throw out the old.

For example if I have a String array with car manufacturers and when I have 10 manufacturers in my array I want the oldest entry to be deleted and the newest entry to be added but kepping FIFO in mind. How would I implement that in a method like this:

public void insert(String name)
{
    int a;
    a = (rear + 1) % names.length;

    if(a == front)
    {
        System.out.println("Full Queue!");
    }
    else
    {
        rear = a;
        names[rear] = name;

        if(front == -1)
        {
            front = 0;
        }

    }
}

A queue is **already** FIFO, so you would only have to "take" an element and "insert" an element if the queue is full. There is a queue available in java: http://www.easywayserver.com/blog/java-queue-example/ — Reut Sharabani, Mar 16 '14 at 22:29
possible duplicate of [Size-limited queue that holds last N elements in Java](http://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java) — indivisible, Mar 16 '14 at 22:31
Do you need to implement the logic yourself ,or are you allowed to use Queue structures in Java? — ErstwhileIII, Mar 16 '14 at 22:41
I need to implement the logic myself.. So no pre-defined structures — sparrowJack, Mar 16 '14 at 23:22
@user2298680 Check out the `LinkedList` implemented below. The Java `Queue` is actually based on a `LinkedList` under the hood — Brian, Mar 16 '14 at 23:24
@user2298680 the code provided below is a self implementation of a LinkedList. It does not use the actual LinkedList of Java — Brian, Mar 16 '14 at 23:33
@BrianVanover how would I go around actually adding elements with your implementation? — sparrowJack, Mar 17 '14 at 09:09
@user2298680 `LinkedList mLL = new LinkedList(10); mLL.append("hello");` — Brian, Mar 17 '14 at 12:58

Raul Guiu · Answer 1 · 2014-03-16T23:17:33.340

I tried to build a queue using rear and front as you did. Slighly modified your insert. I wrote a main method with some test.

Also I had to add a "empty" flag to check if rear == front is because is empty or because is full.

public class DummyQueue {
    int rear, front;
    String[] names;
    boolean empty = true;

    public DummyQueue(int size) {
        names = new String[size];
    }

    public void insert(String name)
    {
        if(!empty && rear == front )
        {
            System.out.println("Full Queue!");
        }
        else
        {
            names[rear] = name;
            rear = (rear+1) % names.length;
        }
        empty = false;
    }

    public String deque()
    {
        if (empty) {
            System.out.println("Empty Queue!");
            return null; // demo 
        } else { 
             String response = names[front % names.length];
             front = (front + 1) % names.length;
             if (front == rear) empty = true;
             return response;
        }
    }

    public static void main(String[] args) {
        DummyQueue d = new DummyQueue(10);
        System.out.println(d.deque());
        d.insert("Element");
        System.out.println(d.deque());
        System.out.println(d.deque());
        for (int i = 0; i < 12; i++) {
            System.out.println("Adding: "+i);
            d.insert("Element "+ i);
        }
        for (int i = 0; i < 12; i++) {
            System.out.println(d.deque());
        }
    }
}

score 0 · Accepted Answer · answered Mar 16 '14 at 23:17

I recommend using an implementation of a LinkedList

public class LinkedList {
  Node head;
  Node tail;
  final int MAX_SIZE;
  int currentSize; 

  public LinkedList(int MAX_SIZE) {
    this.head = null;
    this.tail = null;
    this.MAX_SIZE = MAX_SIZE;
    this.currentSize = 0;
  }

  public void append(String val) {
    Node n = new Node(val);

    if (currentSize < MAX_SIZE) {   
      if (head == null) {
        head = n;
        tail = n;
        return;
      }

      Node current = head;
      while (current.next != null) {
        current = current.next;
      }

      current.next = n;
      currentSize++;
    }
    else {
      head = head.next;
      currentSize--;
      append(val);
    }
  }

public class Node {
  String val;
  Node next;

  public Node(String val) {
    this.val = val;
    this.next = null;
  }
}

Basically you hold a MAX_SIZE and currentSize. When your currentSize reaches the maximum, you remove the head of the LinkedList and append the value to the end.

Queue Circular Array loop

2 Answers2