Queue

Status
Nicht offen für weitere Antworten.

Sindbad1983

Top Contributor
Hi!!

Hab folgendes Problem:

Möchte in ein Queue beliebige Werte himzufügen und entfernen!
Nur bekomm ich eine IndexOutOfBoundsException....
keine Ahnung, worans liegt!

Kann mir bitte jemand einen Tipp geben?

Code:
import java.io.*;
import java.util.*;


public class Queue {
	
		ArrayList list;
		int top=0;
		
		
		public Queue(){
		list=new ArrayList();
		}
		
		public void add(Object obj, int priority){
			list.add(obj);
			top++;
		}
		
		public void remove(){
			
			if(list.size()>0){
			list.remove(list.size()-top);
			}
		}
	
		public ArrayList getAll(){
			return list;
		}
		
		public int getTop(){
			return top;
		}
		
		public int size(){
			return list.size();
		}
		
		public boolean isEmpty(){
			if(list.size()==0){
				return true;
			}
			return false;
		}
		
		
		public String toString(){
			
			StringBuffer sb=new StringBuffer();
			String s="";
			
			for(int i=0;i<list.size()-1;i++){
				sb.append(list.get(i));
			}
			
			return sb.toString();
		}
		
		
		
		
		
		
	

}


Code:
import java.util.*;


public class QueueTest {
	
	public static void main(String [] args){
		
		
		Queue qu=new Queue();
		qu.add(1,1);
		qu.add(2,1);
		qu.add(3,1);
		qu.add(4,2);
		qu.add(5,2);
		
		
		System.out.println(qu);
		
		
		qu.remove();
		qu.remove();
		//qu.remove();
		//qu.remove();
		
		int size=qu.size();
		System.out.println(size);
		
		int top=qu.getTop();
		System.out.println(top);
		
		
		System.out.println(qu);
		
		qu.getAll();
		
		System.out.println(qu);
		
		boolean empty=qu.isEmpty();
		
		System.out.println(empty); 
		
		
	}

}

Danke!!
 

mic_checker

Top Contributor
Code:
         if(list.size()>0){ 
         list.remove(list.size()-top); 
         }

Edit:
Beim Löschen aus einer Queue wird doch normalerweise das Element gelöscht welches zuerst reingesteckt wurde...
Queue = FIFO (First In First Out)

Btw. das isEmpty() geht noch schöner:
Code:
public boolean isEmpty() {
return list.size()==0;
}
 

Sindbad1983

Top Contributor
mensch..billiger Fehler!

ok..danke!



Jetzt gehts weiter:

Eine solche Warteschlange soll Elemente gleichen Typs, unter Berücksichtigung einer Priorität aufnehmen
können. Es sollen dabei Elemente gleicher Priorität vorkommen können. Die Ordnung der Priorität in der
Warteschlange wird dabei durch ein Objekt vom Typ java.util.Comparator realisiert. Dieses
Objekt muss dem Konstruktor der Implementierungsklasse übergeben werden!


Das mit dem Object der Klasse Comparator ist mir leider nach wie vor überhaupt nicht verständlich!
Wie könnt ich das am besten anstellen?

Bezüglich Priorität soll es 5 Stufen geben, sag ich mal .. 1 - 5 ...die muss ich ja mitübergeben(int priority) !
Aber werden die bloß nur mit der Übergabe von Comarator geordnet? nein..kann auch nicht sein.. :bahnhof:
Brauch ich da eine eigene Klasse Comparator?

Kann mir da bitte jemand ein bisschen unter die Arme greifen?
 

mic_checker

Top Contributor
Jo , lass die Klasse Comparable implementieren und in compareTo(..) guckst du dann u.a. nach Prioritäten.

Aber mein Einwand von oben bleibt weiterhin bestehen:
Normalerweise löscht man nicht das Ende oder mittendrin, sondern das was zuerst reingesteckt wurde, bzw. bei Prioritäten entsprechend das mit der höchsten Priorität wird zuerst abgearbeitet....
 

Zilchinger

Mitglied
Hi,
ich hätte vielleicht auch noch ne gute Idee, wie man eine Queue mit Prioritäten verwalten könnte.
Was ist denn wenn du ein Array of Queue anlegst das hat 5 Elemente, nämlich die Prioritäten.

Sprich du hast 5 verschiedene Queues in einem Array. Jetzt gibt es eine Methode zb
addEllement(myObject, Priorität)

Ist die Priorität zb 5

dann addest du das Object in die Queue an der Stelle 4 im Array.
 

Sky

Top Contributor
Zilchinger hat gesagt.:
ich hätte vielleicht auch noch ne gute Idee, wie man eine Queue mit Prioritäten verwalten könnte.
Was ist denn wenn du ein Array of Queue anlegst das hat 5 Elemente, nämlich die Prioritäten.

Ich find' die Idee gar nicht schlecht. Ich denke es kommt darauf an, wie viele Elemente verarbeitet werden müssen. Bei wenigen ist's wohl gleich; bei vielen ist aber denke ich deine Idee schneller, weil man sich immer das erste Element der ersten Queue nehmen kann; so ist sogar eine Sequenzialisierung pro Priorität implizit eingearbeitet.
 

Sindbad1983

Top Contributor
baaa, ich kanns nicht! :cry:


ich kann compareTo nicht implementieren


ich hab jetzt eine neue Klasse Element hinzugefügt:

Code:
import java.io.*;
import java.util.*;


public class Queue implements Comparable {
	
		ArrayList list;
		int top=0;
		int priority;
		
		
		public Queue(){
		list=new ArrayList();
		}
		
		public int compareTo(Element e) {
			
			
			
			
			
			if(this.e<???){
				return 1;
				
			}
			else{}
			
			
			return -1;
			}
		}
		
		public void add(Element e){
			list.add(e);
			top++;
		}
		
		public void remove(){
			
			if(list.size()>0){
			list.remove(list.size()-top);
			top--;
			}
		}
	
		public ArrayList getAll(){
			return list;
		}
		
		public int getTop(){
			return top;
		}
		
		public int size(){
			return list.size();
		}
		
		public boolean isEmpty(){
			return list.size()==0;	
		}
		
		
		public String toString(){
			
			StringBuffer sb=new StringBuffer();
			String s="";
			
			for(int i=0;i<list.size();i++){
				sb.append(list.get(i).toString());
			}
			
			return sb.toString();
		}
}

Code:
public class Element {
	
	private Object obj;
	private int priority;
	
	
		public Element(Object obj, int priority){
			
			this.obj=obj;
			this.priority=priority;
			
		}
		
		public String toString(){
			StringBuffer sb=new StringBuffer();
			sb.append(obj);
			return sb.toString();
			
		}
		
		public int getPriority(){
			
			return priority;
		}
		
		
		

}

Code:
public static void main(String [] args){
		
		
		Queue qu=new Queue();
		qu.add(new Element(1,1));
		qu.add(new Element(2,2));
		qu.add(new Element(3,1));
		qu.add(new Element(4,3));
		qu.add(new Element(5,2));
		
		
		
		System.out.println(qu);
		
		
		qu.remove();
		qu.remove();
		//qu.remove();
		//qu.remove();
        //qu.remove();
		
		int size=qu.size();
		System.out.println(size);
		
		int top=qu.getTop();
		System.out.println(top);
		
		
		System.out.println(qu);
		
		qu.getAll();
		
		System.out.println(qu);
		
		boolean empty=qu.isEmpty();
		
		System.out.println(empty); 
		
		
	}

}
 

mic_checker

Top Contributor
Hol dir in compareTo(Object o) halt entsprechend das Objekt vom Typ Element:

Code:
public int compareTo(Object o) {
Element e = (Element)o;
..
}

Dann musst du überlegen wann welche Elemente "größer" sind etc. also auch Prioritäten beachten....
 

Sky

Top Contributor
mic_checker hat gesagt.:
Hol dir in compareTo(Object o) halt entsprechend das Objekt vom Typ Element:

Code:
public int compareTo(Object o) {
Element e = (Element)o;
..
}

Dann musst du überlegen wann welche Elemente "größer" sind etc. also auch Prioritäten beachten....
.... und außerdem sollen doch die Elemente vergleichbar sein und nicht die Queues.
 

mic_checker

Top Contributor
darauf hab ich gar nicht mehr geachtet, dachte das wäre ihm klar gewesen. Mensch Sindbad, was ist denn los ? ;)

Kannst ja auch mal im Forum gucken, gibt schon einiges zu Comparable.
 

Sindbad1983

Top Contributor
ja tut mir leid, bin halt grad frustriert!

Da bring ich vorhin grad meinen smtp-Client zum Laufen und dann häng ich wieder stundenlang an einer compareTo-Methode!
Irgendwas stimmt da nicht! :-(
 

Sky

Top Contributor
Der Vergleich läuft ganz Einfach (hier sind nur die Prios verglichen, man kann -wenn man will- auch noch die obj. des Element einbeziehen):
Code:
class Element implements Comparable {
  //...
  public int compareTo( Object o ) {
    Element e = (Element)o;
    return this.getPriority() - e.getPriority();
  }

  //...
}
Wenn man nun einen Element mit Prio1 mit einem Prio3 vergleicht, so wird "1-3" also "-2" zurück gegeben. Somit steht der Prio1 vor dem Prio3.
Nicht vergessen die List bei Bedarf zu sortieren (bspw. beim add)
 

Sindbad1983

Top Contributor
mensch, so blöde Fehler..

ja, ich habs genauso wie du, nur hab ich das Comparable-Interface in Queue implementier..und dann isses klar, dass this.getPriority() nicht funktioniert!

Danke!!!!!
 

Sindbad1983

Top Contributor
Code:
public int compareTo(Object obj) {
			
			Element e;
			e=(Element) obj;
			
			if(e.getPriority()<this.getPriority()){
				return -1;
			}
			else if(e.getPriority()>this.getPriority()){
				return 1;
			}
			else{
				return this.getPriority() - e.getPriority(); 
			}
		}

kann das so stimmen?
 

Sindbad1983

Top Contributor
Code:
		public void add(Element e){
			list.add(e);
			top++;
			Collections.sort(list);
		}

geil...funktioniert!

Danke Mic!!! :applaus:

Mensch, das war ne schwere Geburt! :cry:

Jaja..da hab ich Schmerzen!

Naja..dann werd ich morgen gleich mit Comparator beginnen!
Übung macht den Meister! :bae:

Danke für eure tolle Unterstützung!
Gute Nacht,
Tommy
 

Zilchinger

Mitglied
Hi, habe mal schnell meinen Vorschlag in die Tat umgesetzt:
Also hier meine Klasse der PriorityQueue....

Code:
/*
 * Created on 01.06.2005
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package schlage;

import java.util.LinkedList;

/**
 * @author Zilchinger
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class PriorityQueue {
    
    private LinkedList[] prior = new LinkedList[5];
    
    public PriorityQueue(){
        initQueue();
    }
    
    /**
     * Queues initialisieren
     */
    private void initQueue(){
        for (int i=0;i<5;i++){
            prior[i] = new LinkedList();
        }
    }
    
    /**
     * Ein neues Element wird in die Queue nach der entsprechenden Priorität einsortiert
     * @param obj
     * @param priority
     * @return 
     */
    public boolean pushElement(Object obj, int priority){
        if(prior[priority-1].add(obj))
            return true;
        else
            return false;
    }
    
    /**
     * Das nächste Element mit der höchsten Priorität, welches
     * vorhanden ist, wird zurückgegeben und anschl aus der Liste gelöscht
     * @return
     */
    public Object popElement(){
        Object obj = null;
        for (int x=4;x>-1;x--){
            if (prior[x].size()>0){
                obj = prior[x].get(0);
                prior[x].remove(0);
                return obj;
            }
        }
        return null;
    }
    
    /**
     * Das nächste Element einer bestimmten Priorität wird zurückgegeben
     * und aus der Liste gelöscht.
     * @param priority
     * @return
     */
    public Object popElementByPriority(int priority){
        Object obj = null;
        if (prior[priority-1].size()>0){
            obj = prior[priority-1].get(0);
            prior[priority-1].remove(0);
            return obj; 
        }
        else
            return null;
    }
    
    /**
     * Gibt die Anzahl aller Elemente zurück
     * @return Anzahl aller Elemente
     */
    public int getSize(){
        int size = 0;
        for (int x=4;x>-1;x--){
            size +=prior[x].size();
        }
        return size;
    }
    
    /**
     * Gibt die Anzahl der Elemente für eine bestimmten Priorität zurück
     * @param p
     * @return
     */
    public int getSizeByPriority(int p){
        return prior[p-1].size();
    }
    
    /**
     * Prüft ob Queue leer ist
     * @return
     */
    public boolean isEmpty(){
        if (getSize()==0)
            return true;
        else
            return false;
            
    }
    
    /**
     * Löscht alle Elemente aus der Queue
     */
    public void removeAllElements(){
        initQueue();
    }
    
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.pushElement(new String("P1"),1);
        pq.pushElement(new String("P2"),2);
        pq.pushElement(new String("P3"),3);
        pq.pushElement(new String("P4"),4);
        pq.pushElement(new String("P5"),5);
        pq.pushElement(new String("P5_2"),5);
        pq.pushElement(new String("P3_2"),3);
        pq.pushElement(new String("P1_2"),1);
        System.out.println("Gesamtanzahl in Queue: "+pq.getSize());
        System.out.println("Anzahl der Prioritätsstufe 5: : "+pq.getSizeByPriority(5));
        while(pq.isEmpty()==false)
            System.out.println(pq.popElement());//Alle Elemente rausholen
 
    }
}

Probiers mal aus, die Queue arbeitet wie gewohnt nach dem FIFO-Prinzip

Viel Spass :D :) 8)
 

Sky

Top Contributor
Hey, das sieht ja gut aus... jetzt fehlt nur noch die Funktion zur Änderung der Prio :wink:
 

Sindbad1983

Top Contributor
boa, das hast du echt toll gemacht!

Aber ich denk meine funktioniert auch:

die Aufgabenstellung für das Rausnehmen aus der Queue war nämlich so:

Object getFirst() throws NoMoreElementsException Returns the element in the queue with the highest priority which in turn is removed from the queue. Throws NoMoreElementsException if this PriorityQueue does not contain more elements.


Und bei mir geht das:

Code:
public class QueueTest {
	
	public static void main(String [] args){
		
		
		Queue qu=new Queue();
		qu.add(new Element(1,1));
		qu.add(new Element(2,2));
		qu.add(new Element(3,1));
		qu.add(new Element(2,5));
		qu.add(new Element(4,3));
		qu.add(new Element(5,2));
		qu.add(new Element(6,4));
		qu.add(new Element(7,1));
		
		System.out.println(qu);
		
		
		qu.remove();
		qu.remove();
		qu.remove();
		
		
		qu.getAll();
		
		System.out.println(qu);
		
		boolean empty=qu.isEmpty();
		
		System.out.println(empty); 
	}
}


Ausgabe:

13725462
13725
false


müsste so passen, oder?
 

Sindbad1983

Top Contributor
bin jetzt grad dabei, das ganze mit Comparator zu implementieren...

aber wo muss ich Comparator c übergeben?

in der add-Methode?
Collections.sort(list, Comparator c) ??

und die Implementierung compare(Object o1, Object o2)
dann in der Klasse Element oder?
 

Sindbad1983

Top Contributor
naja..ich glaub ich hab so halbigs verstanden, wie die beiden funktionieren:



Comparator funktioniert jetzt auch:

folgende Änderungen:

man braucht eine eigene Klasse MyComparator in der man die compare-Methode implementiert!
Eine Instanz dieser Klasse benötigt man dann, um Collections.sort() diese übergeben zu können!



schauts so aus:


Code:
		public void add(Element e){
			MyComparator comp=new MyComparator();
			list.add(e);
			top++;
			Collections.sort(list, comp);
			
			
		}


Code:
import java.util.*;
import java.lang.*;

public class MyComparator implements Comparator {

	public int compare(Object obj1, Object obj2) {
		
		Element e=(Element) obj1;
		Element other=(Element) obj2;
		
		if(e.getPriority()<other.getPriority()){
			return -1;
		}
		else if(e.getPriority()>other.getPriority()){
			return 1;
		}
		else{
	
		return 0;
		}
	}

}

sonst bleibt alles gleich!


Gibts da ne andere Möglichkeit der Implementierung auch noch?
Stimmt das jetzt aber schon so oder? :roll:
 

Sky

Top Contributor
Du kannst 'comp' auch als Instanzvariable halten und musst ihn nicht bei jedem Aufruf von 'add' neu erzeugen
 

Sindbad1983

Top Contributor
so..jetzt möcht ich noch in dem Beispiel die Generics einbaun:
es sollen ja nur Elemente gespeichert werden -> <Element>


aber ich weiß nie, wo ich das überall reinschreiben muss...

sicher mal hier, z.b:

Code:
public class Queue {
	
                        //es sollen ja nur Elemente in der Liste gespeichert werden
	    ArrayList <Element>list;
		int top=0;
		MyComparator comp=new MyComparator();
		
		
		
		
		public Queue(){
		list=new ArrayList<Element>();
		
		
		}
		
		
		//bei den nächsten 2 muss ich aber nichts verändern, weil kein Wert zurückgegeben wird, oder?
		public void add(Element e){
			
			list.add(e);
			top++;
			Collections.sort(list, comp);
				
		}

		
		public void remove(){
			
			if(list.size()>0){
			list.remove(list.size()-top);
			top--;
			}
		}

nur wie schauts in der Klasse MyComparator aus?

Code:
public class MyComparator implements Comparator {

	public int compare(Object obj1, Object obj2) {
		
		Element e=(Element) obj1; //da wär ja dann eigentlich kein cast mehr nötig oder?
		Element other=(Element) obj2;
		
		if(e.getPriority()<other.getPriority()){
			return -1;
		}
		else if(e.getPriority()>other.getPriority()){
			return 1;
		}
		else{
	
		return 0;
		}
	}

}


Kann mir da bitte jemand einen Tipp geben? :bae:





ich komm nicht drauf...es geht nicht! :cry:
 

Sky

Top Contributor
Wenn schon Generics: Warum läßt Du deine Klasse nur Elemente aufnehmen... die Queue könnte prinzipiell doch auch andere Elemente aufnehmen!?
 

Sindbad1983

Top Contributor
hm...naja das schon..aber es geht mir einfach um die Sache an sich..möcht nur die Funktionalität generell ausprobieren


so gesehen ist das ja eigentlich sinnlos, denn in Element ist Object eine Instanzvariable, das heißt ich kann ja dann ohnehin Beliebiegs drinnen speichern, oder nicht?

Code:
public class Element {
	
	private Object obj;
	private int priority;
	
	
	
		public Element(Object obj, int priority){
			
			this.obj=obj;
			this.priority=priority;
			
		
			
		}
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Queue-Datenstruktur: nach dem Elementen entfernen, das Ergebnis ist immer noch nicht optimal. Java Basics - Anfänger-Themen 3
I BlueJ Queue Frage für Klausur Java Basics - Anfänger-Themen 2
N Vererbung Queue bestehend aus Superclass- und Subclass-Objekten Java Basics - Anfänger-Themen 7
B Zahlenfolge von Queue in Stack Java Basics - Anfänger-Themen 29
J Java Queue mit default Werten erstellen Java Basics - Anfänger-Themen 4
P Priority Queue Performance Java Basics - Anfänger-Themen 3
Chabub Hilfe bei Stacks und Queue Java Basics - Anfänger-Themen 2
G Stack und Queue Arbeitsblatt Java Basics - Anfänger-Themen 3
F Queue zyklisch Java Basics - Anfänger-Themen 8
D Queue vs. Stack Java Basics - Anfänger-Themen 6
L Queue mithilfe von 2 Stacks erstellen Java Basics - Anfänger-Themen 1
B Automatisierung von Jobs / @EJB Scheduler / Verhinderung, dass Queue überläuft Java Basics - Anfänger-Themen 2
A Priority Queue / Comparator Java Basics - Anfänger-Themen 6
J Queue Warteschlange Java Basics - Anfänger-Themen 3
J Liste,Queue,Stack sortieren Java Basics - Anfänger-Themen 2
Y Unendlicher Ringbuffer (Queue) Java Basics - Anfänger-Themen 49
C Stack und Queue in Aktion (Bitte Hilfe für die Klausur) Java Basics - Anfänger-Themen 7
E Stack vs Queue - Gemeinsamkeiten / Unterschiede Java Basics - Anfänger-Themen 7
H Collections StackOverflowError in einer Queue Java Basics - Anfänger-Themen 3
R Klassen Die lineare Datenstruktur Queue Java Basics - Anfänger-Themen 3
JokerBlacky Klassen Klasse Queue Klasse mit Attributen anhängen und auslesen können Java Basics - Anfänger-Themen 4
K Queue enq Fehler Java Basics - Anfänger-Themen 2
F Thread der auf eine Queue wartet, sicher beenden Java Basics - Anfänger-Themen 4
A Queue (Array) leeren Java Basics - Anfänger-Themen 1
F HTTP Get Queue Java Basics - Anfänger-Themen 7
J Queue zyklisch auslesen Java Basics - Anfänger-Themen 4
B Generische Queue programmieren Java Basics - Anfänger-Themen 5
T Priority-Queue Java Basics - Anfänger-Themen 9
S Integer/Value-Paar in Prio-Queue ohne Comparator Java Basics - Anfänger-Themen 5
P Array queue problem Java Basics - Anfänger-Themen 1
L Queue programmieren via BlueJ Java Basics - Anfänger-Themen 5
B Multithreading und eigene Queue entwickeln Java Basics - Anfänger-Themen 3
I Erste Schritte Queue Java Basics - Anfänger-Themen 14
G Queue auf einer Seite löschen, andre Seite schreiben Java Basics - Anfänger-Themen 3
G Queue mit int oder float Java Basics - Anfänger-Themen 3
Q queue.remove Element trotzdem noch vorhanden. Java Basics - Anfänger-Themen 10
P Priority Queue Java Basics - Anfänger-Themen 6
M Compiler-Fehler Queue als ArrayList mit Exceptions Java Basics - Anfänger-Themen 3
S Fehler beim Auslösen des ActionListeners in Verbindung mit einer Queue Java Basics - Anfänger-Themen 5
B Queue mit Daten aus einem Stack füllen Java Basics - Anfänger-Themen 21
P Collections Queue mittels ArrayList Java Basics - Anfänger-Themen 2
T Collections Queue<? extends Number> add() offer() Java Basics - Anfänger-Themen 13
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
B Queue problem! Java Basics - Anfänger-Themen 2
R Queue abhören und Message in Browser ausgeben Java Basics - Anfänger-Themen 3
T Erstellung von Queue mit verkketten listen Java Basics - Anfänger-Themen 3
kulturfenster Stack / Queue Implementationen Java Basics - Anfänger-Themen 11
K Priority Queue - wo ist denn jetzt der Vorteil? Java Basics - Anfänger-Themen 7
W Iterator in Queue Java Basics - Anfänger-Themen 5
Q An erste Stelle in eine Queue eintragen Java Basics - Anfänger-Themen 4
H Stack und Queue Java Basics - Anfänger-Themen 6
M Threadsichere Queue in Java 1.5? Java Basics - Anfänger-Themen 2
G Int-Queue in String-Queue umwandeln Java Basics - Anfänger-Themen 5
A Queue erweitern Java Basics - Anfänger-Themen 13
P Queue, Stacks, Listen Java Basics - Anfänger-Themen 7
S Queue als Array implementiert get()? Java Basics - Anfänger-Themen 4
S Queue als verkettete Liste Java Basics - Anfänger-Themen 9
K Prüfen, ob Queue leer ist Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Neue Themen


Oben