I did an implementation of a double ended queue using arrays. I thought everything works but it stops working correctly when I removeRight() and then insertleft() it gives me bad out put.
this is my main :
dqueue mydq = new dqueue(); mydq.insertRight(1); mydq.insertRight(2); mydq.insertRight(3); mydq.insertRight(4); mydq.insertRight(5); mydq.display(); mydq.insertLeft(0); mydq.insertLeft(-1); mydq.display(); mydq.removeLeft(); mydq.display(); mydq.insertLeft(-1); mydq.display();
this is the output:
1 2 3 4 5
-1 0 1 2 3 4 5
0 1 2 3 4 5
-1 0 1 2 3 4 -1
if I only insert from left it works fine but when I remove from left and insert from left again thats when it stops working right.
my code is:
private int theSize; //Number of elements in the array. private int front; //Index of the front element. private int rear; //Index of the rear element. private AnyType [] items; //Array dequeue public dqueue() //Constructor { items = (AnyType[]) new Object[5]; front = 0; rear = -1; theSize = 0; } //Insert an item from the rear of the dequeque. public void insertRight(AnyType x) { if(theSize == items.length) { grow(); } rear = increment(rear); items[ rear ] = x; theSize++; } //Insert an item from the front of the dequeque. public void insertLeft(AnyType x) { if(theSize == items.length) { grow(); } rear = increment(rear); theSize++; AnyType[] temp =(AnyType[]) new Object[theSize]; for(int i = 0; i < theSize - 1; i++) { temp[i + 1] = items[i]; for(int j = i + 1; j < theSize; j++) { temp[j] = items[j - 1]; } items = temp; break; } items[0]=x; } public void grow() //Method to double the array. { AnyType[] temp = (AnyType[]) new Object[items.length * 2]; //Copy elements that are in the dequeue for(int i = 0; i < theSize; i++, front = increment( front )) { temp[i] = items[front]; } items = temp; front = 0; rear = theSize - 1; } public AnyType removeLeft() //Take item from front of queue { AnyType temp = items[front++]; // get value and incr front if(front == items.length) front = 0; theSize --; // one less item return temp; } public AnyType removeRight() //Take item from rear of queue { AnyType temp = items[rear--]; // get value and decr rear if(rear == -1) rear = theSize -1; theSize --; // one less item return temp; } public void display() //Display the elements in the dequeue. { int j = front; for (int count = 0; count < theSize; count++) { System.out.print(items[j] + " "); j = increment(j); } System.out.println(); } private int increment(int i) //Internal method to increment. { if (i == items.length - 1) return 0; return ++i; } public AnyType first() //The first item in the front of the dequeue. { if(isEmpty()) { System.err.println("Dequeue empty"); } return items[front]; } public AnyType last() //The last item inserted from rear of dequeue. { if(isEmpty()) { System.err.println("Dequeue empty"); } return items[rear]; } public int size() //Number of items in dequeue. { return theSize; } public boolean isEmpty() // True if dequeue is empty. { return (theSize ==0); }
please I really need help... working a long time on this and cant figure it