Queue Algorithm Doubt

[deeps sinha]

hi,
I have doubt in understanding the Queue program in "Data Structure and Algorithms Made Easy in Java " by Narasimha Karumanchi on page 135. I have run the program and enqueued 3 numbers and I called deque more than 5 times and every time its dequeing and giving me the numbers already dequeued. Also it does not delete the numbers after dequeing.I have made few changes in the deQueue method by using class Integer instead if int. Please help. Please find the program below

Thanks.

         
class ArrayQueue {
	private int front;
	private int rear;
	private int capacity;
	private int [] array;
	
	private ArrayQueue(int size) {
		capacity = size;
		front= -1;
		rear = -1;
		array = new int[size];
			
	}
	
	public static ArrayQueue createQueue(int size) {
		return new ArrayQueue(size);
	}
	
	
	public boolean isEmpty() {
		
		return (front == -1);
	}
	
	public boolean isFull() {
		return ((rear +1)%capacity) == front;
	}
	
	public int getQueueSize(){
		return ((capacity-front+rear+1)% capacity);
		
	}
	
	public void enQueue(int data) {
		if (this.isFull()) {
			System.out.println("Queue OverFlow");
			
		}
		else {
			rear = (rear+1)%capacity;
			array[rear]= data;
			if(front == -1){
				front=rear;
			}
		}
	}
	
	
	public int deQueue() {
		Integer data = null;
		if(this.isEmpty()) {
			System.out.println("Queue Empty");
		}else{
			data = new Integer(array[front]);
			if(front==rear){
				front = rear -1;
			}else {
				front = (front+1)%capacity;
				
			}
			
		}
		return data.intValue();
		
		
		
	}
	
	
}

[Praveen Kumar M K]

Can you provide more specifics on what you gave as input. What was the queue capacity, the input values and the removal sequence.

Thanks,
Praveen.

[deeps sinha]

Hi Parveen,
Here is my main method.....

public class Queue {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		ArrayQueue aq = ArrayQueue.createQueue(5);
		aq.enQueue(1);
		aq.enQueue(2);
		aq.enQueue(3);
		
		System.out.println("calling deQueue");
		
		int a = aq.deQueue();
		System.out.println(a);
		System.out.println("calling deQueue");
		int b = aq.deQueue();
		System.out.println(b);
		System.out.println("calling deQueue");
		int c= aq.deQueue();
		System.out.println(c);
		System.out.println("calling deQueue");
		System.out.println(aq.deQueue());
		System.out.println("calling deQueue");
		System.out.println(aq.deQueue());
		System.out.println("calling deQueue");
		System.out.println(aq.deQueue());
		System.out.println("calling deQueue");
		System.out.println(aq.deQueue());
	}

}

[Praveen Kumar M K]

In the deque method why are you setting front = rear - 1 when there is only an element in the queue?

[Praveen Kumar M K]

And you seem to be missing an extra check in your isEmpty method too.

Edit : Perhaps it would be easier for you to see where you are going wrong(or not) by doing some simple scratch work using pen and paper. I suggest you write down the current values of front, rear and array elements after each queue operation. This would help a lot!

[deeps sinha]

Thanks for your advice Parveen,I too have the same doubt(front = rear - 1), actually this code is from a book "Data Structure and Algorithms Made Easy in Java " by Narasimha Karumanchi. Because I donot have much time. Can you tell me where can I find similar code. I have googled but all the links show the builtin Queue Interface. Please also advice a good book for datastructure and algorithms in java.

[Praveen Kumar M K]

You can look into Data Structures and Algorithms in Java by Robert Lafore. Good book to get the basic hang of things.

[deeps sinha]

Thanks Parveen.