CODEWITHSUNDEEP
javaarraysqueue
Fish
Fish

Reputation: 103

Queue implementation with Array- Java

I am trying to implement a Queue with an array. (Not using the built in Java Queue functions). However, when tested, the array will only print out when size ==maxSize (as in the size of the array reached the maxSize/capacity). Other than not printing when the size is less than maxSize, the test cases pass. (It is a double ended Queue, so elements can be added to the front and back). Any advice?

package vipQueueArray;

import java.util.NoSuchElementException;


 public class vipQueue {

private Object[] array;
private int size = 0;
private int head = 0; // index of the current front item, if one exists
private int tail = 0; // index of next item to be added
private int maxSize;

public vipQueue(int capacity) {
    array = new Object[capacity];
    maxSize = capacity;
    size = 0;
    tail = maxSize - 1;

}

public Object Dequeue() {
    if (size == 0) {
        throw new NoSuchElementException("Cant remove: Empty");
    }
    Object item = array[head];
    array[head] = null;
    head = (head + 1) % array.length;
    size--;

    return item;

}

public void EnqueueVip(Object x) {
    if (size == maxSize) {
        throw new IllegalStateException("Cant add: Full");
    }

    array[tail] = x;
    tail = (tail - 1) % array.length;
    size++;

}

public void Enqueue(Object y) {
    if (size == maxSize) {
        throw new IllegalStateException("Cant add: Full");
    }
    array[head] = y;
    head = (head + 1) % array.length;
    size++;

}

public boolean isFull() {
    return (size == maxSize);
}

public boolean isEmpty() {
    return (size == 0);
}

}

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

             vipQueue Q = new vipQueue(2);
             Q.Enqueue(4);






        System.out.printf("->%d", Q.Dequeue());
         }  }

Upvotes: 1

Views: 9525

Answers (2)

Nir Alfasi
Nir Alfasi

Reputation: 53525

In dequeue you're doing:

head = (head + 1) % array.length;

you should (according to your impl.) change it to:

head = (head - 1) % array.length;

Addition:

This is not an implementation of a Queue: a queue works in FIFO and what you implemented works LIFO which is actually more like a...stack.

In order to implement a Queue you should start with both head & tail pointing to array[0]. Then every insert is addAtTail() which means that the item will be entered at array[tail] :

array[tail] = item;
tail++;
size++;

You stop inserting when tail == array.length (throw exception).

Dequeue means removing the item at array[tail-1] and then doing:

tail--;
size--;

Upvotes: 4

James
James

Reputation: 8586

When you enqueue, you're setting head = head + 1. When you dequeue, you're return array[head]

Ergo, after the Enqueue, head = 1, but the item you added is in slot 0.

Additionally, having tail = capacity-1, when there's nothing in the queue is bound to cause trouble. En

Upvotes: 1

Related Questions