Queue using array in java

Question

I just want to ask in Queue if for example i have already 5 elements in my queue and the limit of it is 5. Then, i remove one element. Then i insert an element. Is it right that the output will be overflow? My problem is even if inserted new elements from the queue. It always say overflow. What i want is to add more elements in my queue.(I'm referring to the situation above)

import java.io.*;  
import java.lang.*;  
class clrqueue  
{  
     DataInputStream get=new DataInputStream(System.in);  
     int a[];  
     int i,front=0,rear=0,n,item,count=0;  
void getdata()  
{  
    try  
    {  
         // to enter the limit

       System.out.println("Enter the limit");  
       n=Integer.parseInt(get.readLine());  
       a=new int[n];  
    }   
   catch(Exception e)  
    {  
       System.out.println(e.getMessage());  
   }  
}  
void enqueue()  
{  
  try  
   {  
     if(count<n)  
      {  
         System.out.println("Enter the element to be added:");  
         item=Integer.parseInt(get.readLine());  
         a[rear]=item;  
         rear++;  
         count++;  
      }  
     else  
         System.out.println("QUEUE IS FULL");  
   }  
   catch(Exception e)  
   {  
         System.out.println(e.getMessage());  
   }  
}  


    void dequeue()  
      {  
        if(count!=0)  
         {  
    System.out.println("The item deleted is:"+a[front]);  
    front++;  
    count--;  
    }  
   else  
    System.out.println("QUEUE IS EMPTY");  
  if(rear==n)  
   rear=0;  
  }  
  void display()  
  {  
   int m=0;  
   if(count==0)  
   System.out.println("QUEUE IS EMPTY");  
   else  
   {  
   for(i=front;m<count;i++,m++)  
   System.out.println(" "+a[i]);  
   }  
  }  
 }  
 class Myqueue  
 {  
  public static void main(String arg[])  
  {  
  DataInputStream get=new DataInputStream(System.in);  
  int ch;  
  clrqueue obj=new clrqueue();  
  obj.getdata();  
  try  
  {  
   do  
   {  
   System.out.println(" 1.Enqueue  2.Dequeue  3.Display  4.Exit");  
   System.out.println("Enter the choice");  
   ch=Integer.parseInt(get.readLine());  
   switch (ch)  
   {  
   case 1:  
       obj.enqueue();  
      break;  
   case 2:  
      obj.dequeue();  
      break;  
   case 3:  
      obj.display();  
      break;  
   }  
   }  
   while(ch!=4);  
  }  
  catch(Exception e)  
  {  
  System.out.println(e.getMessage());  
  }  
  }  
 }

Variable names don't have names just because they have to, but because they should be **meaningful**. `a`, `n`, `m` or `ch` are **not**. Please use some names that will say something to the reader, because it's much harder to understand your code quickly. — Eel Lee, Jan 29 '14 at 16:15

score 2 · Answer 1 · answered Jan 29 '14 at 16:45

You want to implement a circular queue. the point is, please keep the front and rear pointer with care or you get overflow or FULL message. please note that when you do front++, rear++, you may make them = n, doing a mod n every time will help restore it to 0 if necessary.

front++;front%=n;

rear++;rear%=n;

for(i=front;m<count;i++,i%=n,m++)

Your implementation is almost right, keep on.

score 0 · Answer 2 · edited May 23 '17 at 11:45

Since you're using an fixed-sized array, when you remove elements, you will have to shift all remaining elements in the array. As it currently is, you're just continuing to increment rear and front, and causing an overflow because those variables eventually exceed the available indexes in your array. You either need to shift your array as you perform the operations, or wrap your rear and front variables accordingly so that they're always between 0 and the limit.

Try this in your dequeue. Count and rear are decremented, because the array is being shifted 1 to the left.

void dequeue() {
    if (count != 0) {
        System.out.println("The item deleted is:" + a[front]);
        count--;
        rear--;
        System.arraycopy(a, 1, a, 0, count);
    } else
        System.out.println("QUEUE IS EMPTY");
    if (rear == n)
        rear = 0;
}

The arraycopy method copies the contents of one array into another. The first parameter is the source/current array, and the second parameter is the start position. You want to remove the first element in the array, so the start position is 1 (the second element in the array). The third parameter is the destination array where you want the data copied. In this instance, I'm just copying to the same array. The fourth parameter is the starting index of the destination array that the data will be added. This is 0 because we want to put that element at the front of the array. The final parameter is the number of elements to copy. a[1] is copied to a[0], a[2] is copied to a[1] and so on.

So, for instance if the array is [1, 2, 3, 4], then when we copy, the count would be 3 (current count has been decremented and we're only copying the final 3 elements). Since the start parameter was 1, that means the first thing copied is a[1].

We end up with an array like : [2,3,4]

You can read more about it here: oracle docs

This other stackoverflow question also illustrates how to do the same thing with a for loop: Java, Shifting Elements in an Array

What is the use of the System.arraycopy(a, 1, a, 0, count) ? — user3249541, Jan 29 '14 at 16:35
@user3249541 Added additional clarification to the question. — Joel, Jan 29 '14 at 16:45
I have one last question. My printing method doesn't work when i changed the code. Could you help with this? — user3249541, Jan 29 '14 at 21:02
@user3249541 Can you please be more specific about your problem? Most likely you accidentally deleted or changed something when you updated the code. I would suggest comparing what you had before with your new code and see where the differences are. — Joel, Jan 29 '14 at 22:04

score 0 · Answer 3 · answered Nov 06 '14 at 06:59

0

Full full implementation of Circular Queue, hava a look at : https://github.com/ranjeetsinha13/androidcodes/blob/master/DS_Algos/src/com/queues/QueuesImpl.java

answered Nov 06 '14 at 06:59

Ranjeet

393
2
10

Queue using array in java

3 Answers3