• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

nDray

[C++] Queue (FIFO)

12 mensagens neste tópico

isto foi só para praticar pointers, classes, tipos genéricos, etc....

/********************************************************
*                     queue (FIFO)                     *
*                                                      *
*    author: nDray                                     *
*    e-mail: cyberdray@gmail.com                       *
* v1.0 date: 29-Jun-2007                               *
*                                                      *
*                                                      *
* NOTE: this piece of software was written entirely    *
*       from the ground-up, and was meant for me to    *
*       get familiar with the c++ language tools, so   *
*       any resemblance to any software living or      *
*       dead is purely coincidential.                  *
*       its use, modification and redistribuition      *
*       are fully supported and encouraged.            *
*                                                      *
* about: this class allows the creation of "queue"     *
*        types. this type of data allocation           *
*        structure works in a First In First Out       *
*        (FIFO) method and, in this case, accepts      *
*        every type of data, working allways in the    *
*        specified way.                                *
*                                                      *
* TO DO: addition of the '+' and '+=' operators to     *
*        allow merging of queues                       *
*                                                      *
* USAGE: the user should notice the pre-conditions,    *
*        as the program will crash if not taken in     *
*        mind. All available services allow the user   *
*        to control these situations.                  *
*        post-conditions are (expected ) to work     *
*                                                      *
* SERVICES: void queue.in      (TYPE);                 *
*           TYPE queue.out     (void);                 *
*           TYPE queue.head    (void);                 *
*           TYPE queue.tail    (void);                 *
*           int  queue.size    (void);                 *
*           bool queue.isFull  (void);                 *
*           bool queue.isEmpty (void);                 *
*           void queue.clear   (void);                 *
*                                                      *
********************************************************/

// make it accept all types of data
template <class TYPE>
class queue
{
   private:

       struct node
       {
           TYPE  elem;
           node* next_ptr;
       };

       int   queue_size; // current size of the queue
       int   MAX_SIZE;   // if defined
       bool  limited;    // is MAX_SIZE defined?
       node* head_ptr;   // the head of the queue
       node* tail_ptr;   // the tail of the queue

   public:

       queue(int);         // construct the queue
       ~queue(void);       // destroy the queue (by clearing it)

       void clear(void);   // clear the queue
       void in(TYPE);      // "push" a value
       TYPE out(void);     // "pop" a value
       TYPE head(void);    // returns next value to come out
       TYPE tail(void);    // returns last inserted value
       bool isFull(void);  // is the queue full?
       bool isEmpty(void); // is the queue empty?
       int  size(void);    // return current size of the queue
};


/*
* Initialize the queue. If a size grater than 0 is defined,
* the queue will have a limited size. If not, limits
* are not defined and the queue can grow as needed
*
*          params: int size
* post-conditions: isEmpty()
*
*/
template <class TYPE>
inline queue<TYPE>::queue(int size = -1)
{
   if(size > 0)
   {
       limited  = true;
       MAX_SIZE = size;
   }
   else
   {
       limited = false;
   }

   queue_size = 0;
   head_ptr   = 0;
   tail_ptr   = 0;
}


/*
* Destroys the queue by clearing it
*
* post-conditions: isEmpty()
*
*/
template <class TYPE>
inline queue<TYPE>::~queue(void)
{
   clear();
}



/*
* Clears the stack.
*
* both head_ptr and tail_ptr will point to
* null while size will be reset to zero
*
* post-conditions: isEmpty()
*
*/
template <class TYPE>
inline void queue<TYPE>::clear(void)
{
   node* temp;
   while(head_ptr)
   {
       temp     = head_ptr;
       head_ptr = head_ptr->next_ptr;

       delete temp;
   }

   queue_size = 0;
   tail_ptr   = head_ptr /* = 0 */;
}


/*
* Inserts a value in the queue.
* Returns false if operation fails
*
*          params: TYPE val
*  pre-conditions: !isFull()
* post-conditions: !isEmpty()
*
*/
template <class TYPE>
void queue<TYPE>::in(TYPE val)
{
   assert(!isFull());

   node* temp_ptr     = new node;
   temp_ptr->elem     = val;
   temp_ptr->next_ptr = 0;

   if(isEmpty())
   {
       head_ptr = temp_ptr;
       tail_ptr = head_ptr;
   }
   else
   {
       tail_ptr->next_ptr = temp_ptr;
       tail_ptr           = tail_ptr->next_ptr;
   }

   queue_size++;
}


/*
* Gets the head value out of
* the queue and returns it
*
* pre-conditions: !isEmpty()
*
*/
template <class TYPE>
inline TYPE queue<TYPE>::out(void)
{
   // assert(!isEmpty()); // <-- ensured in head();
   TYPE temp = head();

   node* temp_ptr = head_ptr;
   head_ptr = head_ptr->next_ptr;
   queue_size--;
   delete temp_ptr;

   return (temp);
}


/*
* Returns the head value of the queue
*
* pre-conditions: !isEmpty()
*
*/
template <class TYPE>
inline TYPE queue<TYPE>::head(void)
{
   assert(!isEmpty());

   return (head_ptr->elem);
}


/*
* Returns the last value that was inserted
*
* pre-conditions: !isEmpty()
*
*/
template <class TYPE>
inline TYPE queue<TYPE>::tail(void)
{
   assert(!isEmpty());

   return (tail_ptr->elem);
}


/*
* Returns true if the queue is full.
*
* The queue can't be full if a maximum
* size wasn't defined at creation stage.
*
* Memory allocation and related problems
* are'nt handled by this queue
*
*/
template <class TYPE>
inline bool queue<TYPE>::isFull(void)
{
   return ((size() == MAX_SIZE) && limited);
}


/*
* Returns true if the queue is empty
*
*/
template <class TYPE>
inline bool queue<TYPE>::isEmpty(void)
{
   return (size() == 0);
}


/*
* Returns the current size of the queue
*
*/
template <class TYPE>
inline int queue<TYPE>::size(void)
{
   return (queue_size);
}
// EOF :~

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Belo trabalho :D

Só acho que o destrutor não é um destrutor  :\  Penso que o destrutor deveria libertar a memória gasta pelos elementos da queue em vez de simplesmente deixar os nodos em memória.

O operador '+' parece-me uma bela ideia. Talvez pudesses incluir o operador '=' , costumo usá-lo quando uso a queue da STL.

Continuação ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só acho que o destrutor não é um destrutor  :\  Penso que o destrutor deveria libertar a memória gasta pelos elementos da queue em vez de simplesmente deixar os nodos em memória.

Realmente tens aí um grande leak...

E porquê os comentários em inglês?

De resto, bom trabalho!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Têm toda a razão..... :\

Estão em inglês não sei bem porquê, mas foi um hábito que ganhei... Tal como as variáveis uso em InglÊs, e tudo... Sinceramente, não gosto de ver o português no meio de código........

Gestão de memória ainda não é comigo........ Vim habituado a não me preocupar com isso, de java...

O que me sugerem? Faço queue::out() até ficar vazia, ou isso dá para fazer tudo de uma vez?

Em vez de asserções também devia usar excepções... Só comecei a usar há pouco tempo, mas vejo que são muito vantajosas, e fazem muito mais sentido....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que me sugerem? Faço queue::out() até ficar vazia, ou isso dá para fazer tudo de uma vez?

O out fica muito pesado... estás a criar 2 variáveis e a retornar um valor, o que não é necessário para o erase.

O melhor será fazer um for para percorrer todos os nós, apagando-os enquanto não apontar para 0. A ideia é a mesma do out... mas sem a criação e retorno.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ok, que acham disto, com as respectivas alterações no resto do código?

no destructor chamo a função clear(head_ptr)

template <class TYPE>
inline void queue<TYPE>::clear(node *del)
{
    if(del == 0)
    {
        return;
    }
    else
    {
        clear(del->next_ptr);
        delete del;
        queue_size--;
    }
}

Com ciclo for acho que tinha de armazenar o node, pois não podia apagá-lo e descobrir o seu next_ptr....... E da maneira que fiz não dá para andar para trás...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

template <class TYPE>
inline void queue<TYPE>::clear(void)
{
node * temp ;	
while ( head_ptr )
{
	temp = head_ptr;
	head_ptr = head_ptr->next_ptr;
	delete temp;
}
queue_size = 0;
tail_ptr = head_ptr;
}

Menos código e sem recursividade  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Concordo com a solução do mogers.

Ao usares recursividade ias tornar o código ineficiente desnecessariamente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque é menos eficiente?

Menos código? Não necessariamente....

Usaria variáveis auxiliares que não preciso, com recursividade..... Foi um dos motivos pelo qual não fiz out(), out() out()..... É capaz de ser menos eficiente talvez por chamar funções e passar argumentos...

Gostava de ouvir uma opinião fundamentada.....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque é menos eficiente?

Menos código? Não necessariamente....

Usaria variáveis auxiliares que não preciso, com recursividade..... Foi um dos motivos pelo qual não fiz out(), out() out()..... É capaz de ser menos eficiente talvez por chamar funções e passar argumentos...

Gostava de ouvir uma opinião fundamentada.....

A menos de optimizações do compilador, as versões iterativas (com ciclos) são quase sempre mais eficientes do que as recursivas. Isto porque na versão recursiva, a cada invocação, é necessário colocar uma série de informações na stack, processo que consome tempo e memória.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque é menos eficiente?

Menos código? Não necessariamente....

Usaria variáveis auxiliares que não preciso, com recursividade..... Foi um dos motivos pelo qual não fiz out(), out() out()..... É capaz de ser menos eficiente talvez por chamar funções e passar argumentos...

Gostava de ouvir uma opinião fundamentada.....

:eek:

A questão do menos código não tem nada a ver com a eficiência... só referia o facto de ter menos linhas, embora isso fosse mais visivel antes do meu edit para melhorar a função.

Em relação a recursividade, suponho que isto já tenha sido explicada no forum.

Quando chamas a função clear, esta vai para a stack e coloca lá alguns elementos, como o parametro *del e outras coisas de modo a voltar à função que chamou a clear. Ao chamares a função recursivamente, é adicionada a mesma informação à stack, só que agora é para voltar à primeira função clear. Quando a 2ª função clear chama recursivamente uma 3ª, repete-se o processo.

Se tiveres 1000 elementos, tens 1000 funções na stack. Quando chegas ao último elemento (del = 0) a 1000ª clear retorna para a 999ª, para isso tem de reajustar a stack (que leva algum tempo), a 999ª retorna pa 998ª e assim sucessivamente.

O problema aqui é aquele ajuste da stack: se somarmos 1000 vezes esse tempo começa a ser significativo. Outro problema é que podemos atinguir o limite de tamanho da stack e o nosso programa crasha. Claro que para atingirmos este limite creio que presisamos de uma profundidade (número de funções chamadas) de alguns milhões.

Sendo assim, ter uma variável local e um ciclo iterativo, é sempre melhor.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora