1

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());
         }  }
5
  • I can't find any problem in the code, other than how I can add an element to the front of the queue. I think the problem is in the test case itself, can you post it as well? Commented Sep 23, 2013 at 4:09
  • posted, so the maxSize is 2, and only one element is added. but dequeue prints out null Commented Sep 23, 2013 at 4:11
  • Enqueue and Dequeue both use head. I would expect that from a stack, not from a queue. Commented Sep 23, 2013 at 4:16
  • @MarkPeters for this implementation it's actually fine, you can't "tell", as the user, if you should dequeue from the head or from the tail, and his implementation of dequeue takes care of it in a very elegant way (modulo). Commented Sep 23, 2013 at 4:18
  • @alfasin: It's not fine if you're expecting FIFO behavior, which is what a queue is. I'm not saying it matters whether you add to the tail or the head, but using one cursor variable for both doesn't seem to make sense. Commented Sep 23, 2013 at 4:24

2 Answers 2

4

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--;
Sign up to request clarification or add additional context in comments.

9 Comments

I'm guessing he's trying to do something where if you have items in slots 1 2 3, and you remove item 1, head should be at 2, not 0. (But he shouldn't be removing from the head anyway, if it's a "queue").
I'm removing the element in a front... in my dequeue function
@James you're right - this implementation of Queue behaves more like a stack :) when you enqueue the head doesn't supposed to "move", only the tail...
@alfasin I guess it's really a Dequeue, with somewhat ambiguous function names.
Nevermind. I fixed it. I switched the Enqueue, EnqueueVip functions. then switched the initial values of head and tail.
|
1

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

1 Comment

so what is your advice exactly?

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.