C++ Crashkurs

Classes | Public Member Functions | List of all members
Queue< T > Class Template Reference

This class implements a simple, singly-linked list of objects implementing the base class Queue::Node. More...

#include <object/queue.h>

Classes

class  Iterator
 A Queue Iterator. More...
 
class  Node
 Base class Node for all queueable classes. More...
 

Public Member Functions

 Queue ()
 Default constructor; initialized the queue as empty.
 
void enqueue (T *item)
 Enqueues the provided item at the end of the queue. More...
 
T * dequeue ()
 Removes the first element in the queue and returns it. More...
 
Iterator begin ()
 
Iterator end ()
 
T * remove (T *item, bool(*cmp)(T *, T *)=[](T *a, T *b) {return a==b;})
 Removes and returns a single element from the queue. More...
 
void insertFirst (T *item)
 Adds item to the beginning of the queue. More...
 
void insertAfter (T *old_item, T *new_item)
 Inserts the element new_item directly after old_item. More...
 
T * first ()
 Returns the first element in the queue without removing it. More...
 
T * next (T *o)
 Returns the next element in the queue for a given element.
 

Detailed Description

template<typename T>
class Queue< T >

This class implements a simple, singly-linked list of objects implementing the base class Queue::Node.

Queue::Node itself merely adds an attribute _next_node to the parent object, allowing to enqueue the element into a single Queue.

Warning
One instance of a class inheriting from Queue::Node can be at most in one Queue

The following example illustrates the usage of Queue::Node : 

class Foo : public Queue<Foo>::Node {
  // ...
}

This Queue implementation supports using C++11 range expressions:

Queue<Foo> list;
Foo a, b, c;

list.enqueue(&a);
list.enqueue(&b);
list.enqueue(&c);

for(Foo * elem : list) {
  // use elem
}
Note
Implementation details: Unlike in other implementations, the tail pointer does not point to the last element in the queue, but to the last element's next pointer. As long as the queue is empty, tail points to the queue's head pointer; therefore inserting can be implemented without further special cases handling empty queues. The check for emptiness can, however, not be omitted on removal.

Member Function Documentation

template<typename T >
void Queue< T >::enqueue ( T *  item)
inline

Enqueues the provided item at the end of the queue.

Parameters
itemQueue element to be appended.
template<typename T >
T* Queue< T >::dequeue ( )
inline

Removes the first element in the queue and returns it.

Returns
The removed head, or 0 if the queue was empty.
template<typename T >
Iterator Queue< T >::begin ( )
inline

Returns an iterator referring to the head of the queue.

template<typename T >
Iterator Queue< T >::end ( )
inline

Returns an end iterator.

template<typename T >
T* Queue< T >::remove ( T *  item,
bool(*)(T *, T *)  cmp = [] (T* a, T* b) {return a == b;} 
)
inline

Removes and returns a single element from the queue.

This method removes and returns a single element (provided via parameter item) from the queue, irrespective of its position. By default, this function compares pointers; it is possible to override the default comparator lambda function by specifying a function type as second parameter.

Parameters
itemElement to be removed.
cmpComparator function.
Returns
Returns the removed element, or 0 if no element matches.
template<typename T >
void Queue< T >::insertFirst ( T *  item)
inline

Adds item to the beginning of the queue.

Parameters
itemThe element to be inserted.
template<typename T >
void Queue< T >::insertAfter ( T *  old_item,
T *  new_item 
)
inline

Inserts the element new_item directly after old_item.

Parameters
old_itemElement to insert after.
new_itemElement to be inserted.
template<typename T >
T* Queue< T >::first ( )
inline

Returns the first element in the queue without removing it.

Returns
The first element in the queue
The documentation for this class was generated from the following file: