000
06.12.2014, 14:39 Uhr
~clerner
Gast
|
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:
| C++: |
// 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
|
|
