Using a list as a queue?

[monchito]

Hi everyone:
I'm tring to use the core::list as a simple queue but i'm not sure if
tjis can be. It's an idea not really tested. Any sugestion is wellcome.
Thanks in advance.

Code: Select all

struct event {
    u32 id;
    u32 type;
    u32 priority;
    };

class CQueue
{
private:
  core::list<event*>Queue;
  core::list<event*>::Iterator it;
  core::list<event*>::Iterator itm;
  unsigned int MAX_EVENTS;

public:
  CQueue( )
  {
    MAX_EVENTS = 25;
    it = Queue.end();    // start at end position
  }
  
 ~CQueue( )
   {
     if (!Queue.empty( ) )
     {
       Queue.clear();
     }  
   }
  
event* Front( ) // get next item from list
  {
    if (!Queue.empty() )
    {
      if ( it != Queue.end() )
        it++;
      else
        it = Queue.begin();

      return ( *it );
    }
    return NULL;
  } 

void Pop()  // erase last element
  {
    if (!Queue.empty() )
    {
      itm = Queue.getLast();
      
      bool b = ( it == itm );
      Queue.erase( itm );
      
      if ( b )
        it = Queue.end();
    }
  }

void Push( event* e ) 
  {
    if ( !IsFull( ) )        // limits the size of the queue
      Queue.push_back( e );
  }

u32 Size( )
  {
    return Queue.getSize( );
  }

event* Back()
  {
    if ( !Queue.empty() )
    {
      itm =  Queue.end();
      return ( *itm );
    }
    
    return NULL;
  }

bool IsFull( )
  {
    return ( MAX_EVENTS < Queue.getSize( ) );
  }

};

[vitek]

Your implementation is really weird for several reasons.

1. It isn't a queue, it is a stack. Almost. You push onto the back, and you pop from the back. With a queue, you'd push on the front and pop from the back, or vice versa.
2. The front() method doesn't return the front element, it actually walks the list from front to back, and then back around to the front.
3. For an actual queue implementation, you don't need the iterator members.
4. There is no need to clear the list in the destructor. That will happen automatically.
5. The queue keeps pointers to objects, but it looks like you really only need to keep objects by value.
6. The push() function doesn't insert objects if the queue is already full. If the user allocated the object from the heap, they would hae no way to know if the operation failed or not, and if it did, they'd never be able to deallocate the object that they wanted inserted.
7. If your queue does actually need to have a maximum number of events, the MAX_EVENTS member should probably be a template parameter or a parameter to the constructor. Either that, or it shouldn't have a maximum length, and the application should keep track of the max.
8. To be more useful, and generic, you might want to consider templatizing it.

Travis

[vitek]

If I were to implement a queue, I'd write something like this..

Code: Select all

//
// note: some functions assume that the queue
// is not empty. you must ensure the queue is
// not empty when calling such functions.
//

template <class T>
class queue
{
public:
  queue ()
  {
  }

  queue (const queue& q)
    : impl_(q.impl_)
  {
  }

  queue& operator= (const queue& q)
  {
    impl_ = q.impl_;
    return *this;
  }

  bool empty () const
  {
    return impl_.empty ();
  }

  u32 size () const
  {
    return impl_.getSize ();
  }

  // see note
  T& front ()
  {
    return *impl_.begin ();
  }

  // see note
  const T& front () const
  {
    return *impl_.begin ();
  }

  // see note
  T& back ()
  {
    return *impl_.getLast ();
  }

  // see note
  const T& back ()
  {
    return *impl_.getLast ();
  }

  void push (const T& v)
  {
    impl_.push_front (v);
  }

  // disclaimer
  void pop ()
  {
    impl_.erase (impl_.end ());
  }

private:
  core::list<T> impl_;
};

Travis

[monchito]

Hi:
Thanks for the corrections. made a little modifications and woks ok, And you are right is not a queue but i need some attributes from a queue and a stack.
Actually i need to traverse the list with the Front() in a circular fashion, always getting the next element. The total of pushed items must be limited,
hi priority pushed at front, low priority at list back, poping from back.
Thanks.