Reputation: 833
Dequeues in Java
I'm having trouble with fully implementing the enqueue and dequeue portion. Here's the result I'm trying to get:
DEQUE TESTING
The size of the deque is: 3
The deque contains:
4 9 8
4
8
9
1
11
The size of the deque is: 2
The deque contains:
11 1
But this is what I'm getting:
DEQUE TESTING
The size of the deque is: 3
The deque contains:
4 9 8
4
null
null
null
null
The size of the deque is: 0
The deque contains:
So, it's only printing up to a certain point. I've went through my code several times (actually a lot) in an attempt to correct this issue, but I can't determine where the problem lies. I have a feeling its something minor that needs to be changed.
Here is my code:
public class Murray_A06Q3 {
public static void main(String[] args) {
LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
System.out.println("DEQUE TESTING");
deque.enqueueBack(3);
deque.enqueueBack(7);
deque.enqueueBack(4);
deque.dequeueFront();
deque.enqueueBack(9);
deque.enqueueBack(8);
deque.dequeueFront();
System.out.println("The size of the deque is: " + deque.size());
System.out.println("The deque contains:\n" + deque.toString());
System.out.println(deque.dequeueFront());
deque.enqueueFront(1);
deque.enqueueFront(11);
deque.enqueueFront(3);
deque.enqueueFront(5);
System.out.println(deque.dequeueBack());
System.out.println(deque.dequeueBack());
System.out.println(deque.last());
deque.dequeueFront();
deque.dequeueFront();
System.out.println(deque.first());
System.out.println("The size of the deque is: " + deque.size());
System.out.println("The deque contains:\n" + deque.toString());
} // End of main method
public static class LinkedDeque<T> implements DequeADT<T> {
private int count;
private LinearDoubleNode<T> firstNode, lastNode;
// constructor
public LinkedDeque(){
count = 0;
firstNode = null;
lastNode = null;
} // end of constructor
// Beginning of enqueueFront
public void enqueueFront(T element) {
LinearDoubleNode newNode = new LinearDoubleNode();
if(isEmpty()){
lastNode = newNode;
count++;
}
else
firstNode.setPrev(newNode);
firstNode = newNode;
count--;
} // end of enqueFront
// Beginning of enqueueBack
public void enqueueBack(T element) {
LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);
if (isEmpty())
firstNode = node;
else
lastNode.setNext(node);
lastNode = node;
count++;
} // end of enqueueBack
// Beginning of dequeueFront
public T dequeueFront() {
T front = null;
if (!isEmpty()) {
front = firstNode.getElement();
firstNode = firstNode.getNext();
count--;
if (firstNode == null) {
lastNode = null;
}
else
firstNode.setPrev(firstNode);
}
return front;
} // end of dequeueFront
// Beginning of dequeueBack
public T dequeueBack() {
T back = null;
if (!isEmpty()) {
back = lastNode.getElement();
lastNode = lastNode.getPrev();
if (lastNode == null) {
firstNode = null;
}
else
lastNode.setNext(null);
}
return back;
} // end of dequeueBack()
public T first() {
return firstNode.getElement();
}
public T last() {
return lastNode.getElement();
}
// Beginning of isEmpty()
public boolean isEmpty() {
if (count == 0) {
return true;
}
else
return false;
} // End of isEmpty()
// Beginning of size()
public int size() {
return count;
}
// Begin of toString() method
public String toString() {
if (isEmpty()) {
return " ";
}
StringBuilder sb = new StringBuilder();
LinearDoubleNode<T> next = firstNode;
while(next != null){
sb.append(" ").append(next.getElement());
next = next.getNext();
}
return sb.toString();
} // End of toString()
} // End of LinkedDeque
} // End of class header
Upvotes: 0
Views: 1474
Answers (2)
Reputation: 34628
The first rule of a doubly-linked list is that you have to maintain two links when you add an element. This is your code:
public void enqueueFront(T element) {
LinearDoubleNode newNode = new LinearDoubleNode();
if(isEmpty()){
lastNode = newNode;
count++;
}
else
firstNode.setPrev(newNode);
firstNode = newNode;
count--;
} // end of enqueFront
First, you never put the value of your element into the new Node.
Second, the queue should look like
A ⇆ B ⇆ C
But let's see how you add an "A" when you have only a "B" in the queue. Your firstNode is the "B", and you set its prev with setPrev to point to your "A".
A ← B
But you do not link back from the new "A" to "B". This means that when you need to look at the queue from the front side, it seems to have only one element - A doesn't have a "next"!
Your else clause should be:
else {
firstNode.setPrev(newNode);
newNode.setNext(firstNode);
}
And then you'll be able to traverse the list from both sides. The same logic should be applied to your enqueueBack as well.
Now, your dequeue logic:
public T dequeueFront() {
T front = null;
if (!isEmpty()) {
front = firstNode.getElement();
firstNode = firstNode.getNext();
count--;
if (firstNode == null) {
lastNode = null;
}
else
firstNode.setPrev(firstNode);
}
return front;
}
Now, after you dequeue, you set the of the new firstNode to itself. This means you might have an infinite loop. After you do this once, if you try to walk the "prev" link by dequeuing from the back, you'll just get the same node again and again. The backlink should be set to null (which you do properly in dequeueBack, by the way).
Upvotes: 0
Reputation: 1193
You forgot to set the previous and the elements. Also you had some errors when incrementing the count. And be caucios about some exceptions which are not thrown. Nevertheless, it should be straightforward now. You have below working code with the required output:
public static class LinkedDeque<T> {
private int count;
private LinearDoubleNode<T> firstNode, lastNode;
// constructor
public LinkedDeque(){
count = 0;
firstNode = null;
lastNode = null;
} // end of constructor
// Beginning of enqueueFront
public void enqueueFront(T element) {
LinearDoubleNode newNode = new LinearDoubleNode();
newNode.setElement(element);
if(isEmpty()){
lastNode = newNode;
firstNode = newNode;
}
else {
LinearDoubleNode second=firstNode;
firstNode=newNode;
firstNode.setNext(second);
second.setPrev(firstNode);
// firstNode.setPrev(newNode);
}
count++;
} // end of enqueFront
// Beginning of enqueueBack
public void enqueueBack(T element) {
if (element==null) throw new NullPointerException("cannot add null to the list");
LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);
node.setElement(element);
if (isEmpty()){
firstNode = node;
lastNode=node;}
else{
LinearDoubleNode<T> before=lastNode;
lastNode=node;
before.setNext(lastNode);
lastNode.setPrev(before);
}
count++;
} // end of enqueueBack
// Beginning of dequeueFront
public T dequeueFront() {
T front = null;
if (count==1){
front=firstNode.getElement();
firstNode=null;
lastNode=null;
count--;
}
else if (!isEmpty()) {
count--;
front = firstNode.getElement();
firstNode = firstNode.getNext();
}
return front;
} // end of dequeueFront
// Beginning of dequeueBack
public T dequeueBack() {
T back = null;
if (count==1){
back = lastNode.getElement();
lastNode = null;
firstNode = null;
count--;
}
else if (!isEmpty()) {
count--;
back = lastNode.getElement();
lastNode = lastNode.getPrev();
lastNode.setNext(null);
}
return back;
} // end of dequeueBack()
public T first() {
return firstNode.getElement();
}
public T last() {
return lastNode.getElement();
}
// Beginning of isEmpty()
public boolean isEmpty() {
return count==0;
} // End of isEmpty()
// Beginning of size()
public int size() {
return count;
}
// Begin of toString() method
public String toString() {
if (isEmpty()) {
return " ";
}
StringBuilder sb = new StringBuilder();
LinearDoubleNode<T> next = firstNode;
while(next != null){
sb.append(" ").append(next.getElement());
next = next.getNext();
}
return sb.toString();
} // End of toString()
} // End of LinkedDeque
} // End of class header
DEQUE TESTING
The size of the deque is: 3
The deque contains:
4 9 8
4
8
9
1
11
The size of the deque is: 2
The deque contains:
11 1
Upvotes: 1
Related Questions
- Java Deque Implementation
- Implementing Dequeue in Java
- JAVA how to implement wraparound on a deque
- removeLast / addFirst methods in Deque JAVA
- what is wrong with this deque implementation
- What is the Java equivalent of C++ deque?
- Java Deque without using any of the existing classes like LinkedList?
- Java equivalent of std::deque
- Problems with implementing a deque in java
- What to choose to implement deque?