Problems with implementing a deque in java

Question

sorry, just following on from the question I had here : here I am trying to run this method to remove a generic value (EltType) from a double sided queue(deque), but I keep getting an error in that, I call insertFirst twice, and insert the value "3" into the array twice, then, when I run removeFirst, it will print out "3" once, and then "Null" thereafter. Would anyone be able to help me out please ?

class ArrayBasedDeque<EltType> { private final int CAPACITY = 10; private int capacity; private int end; private EltType deque[]; public ArrayBasedDeque() { this.capacity = CAPACITY; deque = (EltType[]) (new Object[capacity]); } public EltType removeFirst() { EltType[] tempArray; EltType returned = deque[0]; tempArray = (EltType[]) new Object[capacity]; for (int i=1;i<capacity;i++) { tempArray[i-1] = deque[i]; } deque = tempArray; return returned; } public boolean isEmpty() { return end == 0; } public void insertFirst(EltType first) { if(!isEmpty()) { EltType[] tempArray; tempArray = (EltType[]) new Object[capacity+1]; for (int i=0;i<deque.length;i++) { tempArray[i+1] = deque[i]; } deque = tempArray; } deque[0] = first; } }

Thank you :)

Why are you casting a new array like this? Why not just create that type of array? deque = (EltType[]) (new Object[capacity]) — Joe Phillips
– Joe Phillips, Commented Feb 7, 2011 at 22:39
Any particular reason you are implementing this yourself? Homework, self improvement, otherwise? If not, you may want to consider the java.util.ArrayDeque instead. — rfeak
– rfeak, Commented Feb 7, 2011 at 23:33
@Joe Phillips - this will not work in Java, try it. It returns an error, it's an unfortunate trait of generic types! — user476033
– user476033, Commented Feb 8, 2011 at 17:10

Edawg · Accepted Answer · 2011-02-07 22:40:23Z

The big glaring issue is that end never changes. isEmpty() will always return true. Now let's look at your insertFirst() method.

public void insertFirst(EltType first) { if(!isEmpty()) { EltType[] tempArray; tempArray = (EltType[]) new Object[capacity+1]; for (int i=0;i<deque.length;i++) { tempArray[i+1] = deque[i]; } deque = tempArray; } deque[0] = first; }

Knowing that isEmpty() always returns true no matter what, what is the problem with this piece of code?

Mihai Toader · Accepted Answer · 2011-02-07 22:39:05Z

You need to update your end pointer too when you remove an element.

You should also investigate System.arrayCopy()

Collectives™ on Stack Overflow

Problems with implementing a deque in java

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related