kö-implentation

Hur gör jag när sista noden från en kö plockas ut..jag vill att kön ska bli tom. head och tail ska sättas till null. När kön skapas sätter jag ju head och tail till null och kön är tom. Men när den sista noden plockas ut måste jag göra något...men vet inte exakt vad och hur?

//Här plockas noder ur kön
 public WordNode dequeue() {
   //Ordet i noden
   WordNode ord = head;
   if(head.next!=null){
   head = head.next;
   }
   else{
   //??
   }
   return ord;
   
   }    
   
   public boolean isEmpty() {
   if (head==null && tail==null)
       return true;
   else
       return false;
   }

}

Om du plockar ut det sista elementet ur en kö är den per definition tom. Om du anser den vara tom om huvud och tail är null, borde du alltså sätta head och tail till null när du plockar ut sista elementet.

Ok. men om jag skriver så här:

public WordNode dequeue() {
//Ordet i noden
WordNode ord = head;
if(head.next!=null){
head = head.next;
}
else{
head=null;
tail=null;
}
return ord;

Då kommer inte den första noden som jag stoppade in ut överhuvudtaget..tänker jag fel här?

ett alternativ är att du använder en List istället:
http://java.sun.com/j2se/1.3/docs/api/java/util/List.html

luna skrev:

ett alternativ är att du använder en List istället:
http://java.sun.com/j2se/1.3/docs/api/java/util/List.html

Tanken är nog att han ska göra en egen implementation av en kö och inte använda några färdiga listklasser.

Prime_66 skrev:

Då kommer inte den första noden som jag stoppade in ut överhuvudtaget..tänker jag fel här?

Jag skulle gissa att felet ligger i instoppningsfunktionen, i sådana fall. Posta den så kanske vi kan hjälpa. Och förresten, använd [kod]sådana här taggar runt din kod för att få den mer lättläst[/kod] :)

Så att det blir såhär, alltså.

ja..vad det är är ju en länkad lista som ligger i en kö. Kolla koden:

class Queue {
  
    private WordNode head;
    private WordNode tail;
    public Queue() {
        head = null;
        tail = null;

    }
    
    public void writeChain(){
    writeChain(tail);    
    }
    
  private void writeChain(WordNode wordnode){
    if (wordnode!=null){
       writeChain(wordnode.previous); 
       System.out.println(wordnode.info);
   }
}

    
       public void enqueue(WordNode pappa, WordNode nynod) {
       if(isEmpty()){ 
       head = nynod;
       pappa=null;
       //När kön skapas är previous null
       head.previous=pappa;
       }
       else{ 
       tail.next=nynod;
       //Den kommer från head
       nynod.previous=pappa;
       }
       tail = nynod;
       
       }
       public WordNode dequeue() {
       //Ordet i noden
       WordNode ord = head;
       if(head.next!=null){
       head = head.next;
       }
       else{
       head=null;
       tail=null;
       }
       return ord;
       
       }    
       
       public boolean isEmpty() {
       if (head==null && tail==null)
           return true;
       else
           return false;
       }
}{

Problemet löst. Som någon sa..problemet låg i insättnigen! varje gång kön blev helt tom sattes faderspekaren till null vilket ledde till att vägen bröts där typ.. :birp

Ange gärna lämligt svar som lösning då. Blir lättare för andra som söker att hitta en lösning ;)