Criando as coleções de pilha e fila

Este artigo explica como criar outras estruturas de dados, como pilhas e filas, a partir de classes de lista MFC. Os exemplos usam classes derivadas de CList, mas você pode usar CList diretamente, a menos que precise adicionar funcionalidade.

Pilhas

Como a coleção de lista padrão tem uma cabeça e uma cauda, é fácil criar uma coleção de lista derivada que imita o comportamento de uma pilha de último a entrar, primeiro a sair. Uma pilha é como uma pilha de bandejas em uma cafeteria. À medida que as bandejas são adicionadas à pilha, elas são colocadas no topo da pilha. A última bandeja adicionada é a primeira a ser removida. As funções do membro da coleção de listas AddHead e RemoveHead podem ser usadas para adicionar e remover elementos especificamente do início da lista; portanto, o elemento adicionado mais recentemente é o primeiro a ser removido.

Para criar uma coleção de pilhas

1. Derive uma nova classe de lista a partir de uma das classes de lista MFC existentes e adicione mais funções membro para suportar a funcionalidade das operações de pilha.

   O exemplo a seguir mostra como adicionar funções de membro para enviar elementos para a pilha, espiar o elemento superior da pilha e exibir o elemento superior da pilha:

   class CTray : public CObject { };
   
   class CStack : public CTypedPtrList< CObList, CTray* >
   {
   public:
      // Add element to top of stack
      void Push(CTray* newTray)
      {
         AddHead(newTray);
      }
   
      // Peek at top element of stack
      CTray* Peek()
      {
         return IsEmpty() ? NULL : GetHead();
      }
   
      // Pop top element off stack
      CTray* Pop()
      {
         return RemoveHead();
      }
   };
   

Observe que essa abordagem expõe a classe subjacente CObList . O utilizador pode chamar qualquer função de membro CObList, quer faça sentido para uma pilha ou não.

Filas

Como a coleção padrão tem uma cabeça e uma cauda, também é fácil criar uma coleção derivada que imita o comportamento de uma fila FIFO (primeiro a entrar, primeiro a sair). Uma fila é como uma fila de pessoas numa cafetaria. A primeira pessoa na fila é a primeira a ser atendida. À medida que mais pessoas chegam, elas vão até o fim da fila para esperar sua vez. As funções de membro da coleção de listas AddTail e RemoveHead podem ser usadas para adicionar e remover elementos especificamente da cabeça ou da cauda da lista; portanto, o elemento mais recentemente adicionado é sempre o último a ser removido.

Para criar uma coleção de filas

1. Derive uma nova classe de lista de uma das classes de lista predefinidas fornecidas com a Microsoft Foundation Class Library e adicione mais funções de membro para dar suporte à semântica de operações de fila.

   O exemplo a seguir mostra como você pode acrescentar funções de membro para adicionar um elemento ao final da fila e obter o elemento da frente da fila.

   class CQueue : public CTypedPtrList< CObList, CPerson* >
   {
   public:
      // Go to the end of the line
      void AddToEnd(CPerson* newPerson)
      {
         AddTail(newPerson);
      }        // End of the queue
   
   // Get first element in line
      CPerson* GetFromFront()
      {
         return IsEmpty() ? NULL : RemoveHead();
      }
   };
   

Ver também

Coleções