1

So I was required to do an implementation of queue in arrays, and I wasn't having any trouble till I saw I was getting a funny output after I dequeue and try to enqueue another value...
For example (output):

Queue: [1]     //Enqueue 1  
Queue: [1, 2]  //Enqueue 2
Queue: [2]      //Dequeue
Queue: [2, 2]   //Enqueue 3
Queue: [2, 2, 3] //Enqueue 4
Queue: [5, 2, 3, 4]  //Now is a total mess...

My code contains queue, dequeque and resize methods everything was working fine and I really don't have any idea at all of how to fix it anymore... Here's my code with the main if you want to try it. Thanks.

public class MainQueue {
    public static void main(String[] args) {

        int capacity=5;
        Queue<Integer> queue = new Queue<Integer>(capacity);

        queue.enqueue(1);
        System.out.println("Queue: "+ queue);
        queue.enqueue(2);
        System.out.println("Queue: "+ queue);
        queue.dequeue();
        queue.enqueue(3);
        System.out.println("Queue: "+ queue);
        queue.enqueue(4);
        System.out.println("Queue: "+ queue);
        queue.enqueue(5);
        System.out.println("Queue: "+ queue);

    }
}

Class

import java.util.NoSuchElementException;


public class Queue<E> {
    private E[] elements;//array in generic
    private int front;//first element or front of the queue
    private int back;//last element or back of the queue
    private int capacity; //capacity of the queue
    private int count; //indicates number of elements currently stored in the queue

    public Queue(int size)
    {
        capacity = size;
        count = 0;
        back = size-1;
        front = 0;
        elements =(E []) new Object[size];  //queue array empty
    }

    //Returns true if the queue is empty or false
    public boolean isEmpty()
    {
        return count==0;//means its true
    }

    //Add elements to the queue
    public void enqueue(E item)
    {
        if(count == capacity)
        {
            resize(capacity*2);
            // System.out.println("Queue is full");

        }

        back =(back+1) % capacity;    //example back=(0+1)%10=1
        elements[back]=item;
        //elements[0]=0
        //item=elements[count];
        count++;
    }


    //Public resize
    public void resize(int reSize){
        E[] tmp = (E[]) new Object[reSize];

        int current = front;
        for (int i = 0; i &lt; count; i++)
        {
            tmp[i] = elements[current];
            current = (current + 1) % count;
        }

        elements = tmp;
        front = 0;
        back = count-1;
        capacity=reSize;

    }


    //Dequeue method to remove head
    public E dequeue()
    {
        if(isEmpty())
        throw new NoSuchElementException("Dequeue: Queue is empty");
        else
        {
            count--;
            for(int x = 1; x <= count; x++)
            {
                elements[x-1] = elements[x];
            }
            capacity--;
            return (E) elements;
        }
    }

    //peek the first element
    public E peek()
    {
        if(isEmpty())
        throw new NoSuchElementException("Peek: Queue is empty");

        else
        return elements[front];
    }


    //Print queue as string
    public String toString()
    {

        if(isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }

        String s = "[";
        for(int i = 0; i < count; i++)
        {
            if(i != 0)
            s += ", ";
            s = s + elements[i];// [value1,value2,....]
        }

        s +="]";
        return s;
    }

    public void delete() {   //Delete everything
        count = 0;
    }
}
5
  • 1
    Why do you reduce the capacity when you dequeue? Commented Nov 22, 2013 at 18:45
  • This works as expected on my machine... I get [1], [1,2], [2], [2,3], [2,3,4], and [2,3,4,5]. Commented Nov 22, 2013 at 18:48
  • Thats weird because I keep on getting repeated numbers and numbers placed in a random index...where did you tried it? Commented Nov 22, 2013 at 18:54
  • @HunterMcMillen I actually thought about that, but still even if I take it off doesnt make any difference, because when I resize the capacity gets modified, anyways yes, i should take it off... Commented Nov 22, 2013 at 18:57
  • @LilithDeficiency, never mind. It doesn't work if your initial capacity is big enough for initial dequeue. If you set capacity to 2, it seems to work. Commented Nov 22, 2013 at 19:07

2 Answers 2

2

You are updating the back in the enqueue() method using the current value of back, but you aren't updating it in the dequeu() method at all. That is not going to work correctly. In fact, you should rather calculate back based on count.

Just change:

back = (back + 1) % capacity;

to:

back = count % capacity;
Sign up to request clarification or add additional context in comments.

1 Comment

Thankkkkk youuuu sir, you made my day! this works! :)
1

In dequeue you are not updating the back variable that determines the position on which you add new value with enqueue. Furthermore in dequque you could copy nonexistent value on index 0 from index 1 when you have count just of 1. This is a special case that will make out of bounds error if you made a queue with capacity(size) of 1, enqueued something and then dequeued it.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.