I have written these codes and in trying out the code in my main method, it looks like I am on the right way, but which disturbs me is the fact, that whenever I say:
while (!empty(){
it give me front of the queue. It seems like the queue never gets empty and the loop is running forever. Is this the logic of circular doubly linked lists, that it never gets empty? I think I might be making mistakes in the dequeue
method.
package übung;
import java.util.NoSuchElementException;
public class QueueCircularDLL<T> implements ADTQueue<T> {
private ListElement<T> head;
private ListElement<T> tail;
public QueueCircularDLL(){
head=null;
tail=null;
}
public void enq (T element){
ListElement<T>newElement=new ListElement<T>(element);
if (empty()){
head= newElement;
tail= head;
}
tail.setNextElement(newElement);
newElement.setPrevElement(tail);
tail=tail.getNextElement();
tail.setNextElement(head);
head.setPrevElement(tail);
}
public void deq(){
if (empty()){
throw new RuntimeException("queue is empty");
}
if (head==tail){
//head=null;
head=null;
tail=null;
}
else{
head=head.getNextElement();
head.setPrevElement(tail);
tail.setNextElement(head);
}
}
public T front(){
if(empty()){
return null;
}
return head.getElement();
}
public boolean empty(){
return (head==null);
}
private static class ListElement<T>{
private T element = null;
private ListElement<T> nextElement = null;
private ListElement<T> prevElement = null;
public ListElement(T element) {
this.element = element;
}
public T getElement() {
return element;
}
public ListElement<T> getNextElement() {
return nextElement;
}
public void setNextElement(ListElement<T> element) {
this.nextElement = element;
}
//für zirkuläre doppelt verkettete liste
public ListElement<T>getPrevElement(){
return prevElement;
}
// für zirkuläre doppelt verkette liste
public void setPrevElement(ListElement<T> element){
this.prevElement=element;
}
}
public static void main(String[] args) {
QueueCircularDLL<Integer> queue = new QueueCircularDLL<Integer>();
for (int i = 0; i < 10; ++i) {
queue.enq(i);
}
//while (!queue.empty()) {
for(int i=0; i<20; i++){
System.out.println(queue.front());
queue.deq();
}
}
}
head
andtail
when you enqueue but only half updatehead
when you dequeue. If you updatetail
properly, then you won't need to check the null case except to gate the update of the previous element for the newhead
. Hint: after you updatehead
, it's the same two commands to updatetail
andhead
as you use inenqueue
. – mdfst13 Jul 16 at 18:21