Vektor in Queue



  • Hallo, ich habe folgende Aufgabe:

    Modifizieren Sie die aus der Vorlesung bekannte Klasse Queue, indem Sie zum Speichern der Elemente einen Vektor vewenden. Wenn man mit einer leeren Queue beginnt, soll eine beliebige Folge von k push back- und pop front-Operationen nur Laufzeit O(k) haben. Wenn n dabei die maximale Zahl von Elementen ist, die sich gleichzeitig in der Queue befinden, soll der Speicherbedarf außerdem nur O(n) groß sein.

    Leider habe ich keine Ahnung, was ich machen soll. Es wäre schön, wenn mir hier jemand obiges erklären könnte (mein wissen beschränkt sich dabei auf wenige Stunden gelerntes C++). Hier ist die Klasse, von der oben die Rede ist:

    // queue.h (Queue)
    
    template<typename T> class Queue {  // T is a type to be specified by user
    public:
        ~Queue()                        // destructor
        {
            clear();
        }
    
        bool is_empty()
        {
            return _front == nullptr;
        }
    
        void clear()
        {
            while (not is_empty()) {
                pop_front();
            }
        }
    
        void push_back(const T &object)   // insert object at end of queue
        {
            Item* cur = new Item(object); // get new memory for Item at address cur,
                                          // initialize with object and nullptr
            if (is_empty()) {
                _front = cur;
            }
            else {
                _back->_next = cur;     // p->n is abbreviation for (*p).n
            }
            _back = cur;
        }
    
        T pop_front()                   // delete and return first object of queue
        {                               // ATTENTION: queue must not be empty!
            Item* cur = _front;
            if (_back == _front) {
                _front = nullptr;
                _back  = nullptr;
            }
            else {
                _front = _front->_next;
            }
            T object = cur->_object;
            delete cur;                 // free memory for 1 Item at address cur
            return object;
        }
    
    private:
        struct Item {                           // struct is a class where by
            Item(T object) : _object(object) {} // default everything is public
    
            T _object;
            Item* _next = nullptr;     // pointer to the next Item (or nullptr)
        };
    
        Item* _front = nullptr;        // _front and _back are pointers to
        Item* _back = nullptr;         // variables of type Item, or the
    };                                 // nullptr if queue is empty
    

    Meine Vermutung: In der dritten Zeile irgendwie "typename" durch "vector" ersetzen, und dann die beiden Funktionen in der Klasse "pushback" und "popfront" in geeigneter Weise anpassen. Allerdings weiß ich nicht, wie das genauer geschehen soll.

    Vielen Dank im Voraus



  • Du sollst die Queue für beliebige Datentypen mithilfe eines vector implementieren. Deine Annahme ist falsch, und machen musst du es schon selber.



  • ja, ich habe auch vor, es selber zu machen, nur weiß ich nicht, was ich machen soll 😃

    was ist denn damit gemeint, "die queue für beliebige Datentypen mithilfe eines Vektor implementieren"? Kannst du das etwas ausführen, oder irgendein kleines Beispiel geben?

    Oder vielleicht würde mir auch das schon weiterhelfen: Wie könnte ich zB obige queue-Klasse in einer Main-Funktion verwenden?



  • clerner schrieb:

    Wie könnte ich zB obige queue-Klasse in einer Main-Funktion verwenden?

    Du solltest die Vorlesungen auch besuchen oder wenigstens das Script lesen.



  • Falls mir sonst noch jemand weiterhelfen will, ich nehme die Hilfe gerne entgegen.

    Manni66, brauchst nicht mehr antworten, darauf kann ich auch verzichten. 😉



  • Deine Klasse ist aktuell mit einer verketteten Liste implementiert, und das sollst du dahingehend ändern, als dass du einen vector nutzen sollst.

    Was Vectoren, Verkettete Listen sind sollte aus deienr Vorlesung oder aus dem Script zu entnehmen sein.

    Noch Fragen?



  • Auch hier nochmal die Frage:

    Möchtest du lieber hier oder hier diskutieren?


Anmelden zum Antworten