Verständnisfrage Double-ended Queues
-
Erstmal hallo, bin neu hier.
Ich habe ne Frage zu "Double-ended Queues" und dem Einfügen von Elementen am Start der Liste:
Beim Vector ist es so (bitte berichtigt mich), falls ein Element ganz vorne (links) eingefügt werden soll, alle anderen Elemente nach rechts verschoben werden.
Warum ist das bei der Queue schneller mit dem Einfügen am Start?
Wie funktioniert das (intern) da genau?PS: Zum Thema rtfm: Ich finde immer nur in Dokus, warum man das und das anwenden soll, aber nicht wie sie intern aufgebaut sind und wie sie funktionieren.
Danke und Gruß,
Kai
-
Schau Dir doch einfach selbst die Implementierung an, zB bei STLport oder der gcc-C++-Standardlibrary.
-
Könnt ich machen, aber ob ich da was verstehe ist eher fraglich.
Vielleicht steht es ja doch in einem meiner Bücher und ich habs nur übersehen...
-
Also wenn du bei Google nach "Double-ended Queue" suchst findest du über 6000 Treffer. Da ist mit Sicherheit auch irgendwo erklärt wie sowas intern funktioniert.
-
`kk schrieb:
Erstmal hallo, bin neu hier.
Beim Vector ist es so (bitte berichtigt mich), falls ein Element ganz vorne (links) eingefügt werden soll, alle anderen Elemente nach rechts verschoben werden.
also nicht bei std::vector. es heist ja auch push_back und net push_front.
-
Man kann in einem vector sehr wohl etwas am Anfang einfügen (über insert()), und dann wird der Rest nach hinten verschoben. Der OP hat da schon Recht.
-
Ok, dann werd ich nochmal selbst suchen.
Gruß, Kai.
-
Der Unterschied ist ganz einfach, dass vector ein Array ist und Queues Listen sind, daher läuft das Einfügen an Anfang und Ende in O(1) ab. Bei den 08/15 Liste auch an beliebiger Stelle, aber das ist ja nicht der Sinn und nZweck von Queues.
Also such nach Listen und bilde dir damit Queues als Sonderform dieser.