Partilhar via


Criando coleções de pilhas e filas

Este artigo explica como criar outras estruturas de dados, como pilhas e filas, com base em 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 listas padrão tem uma cabeça e uma cauda, é fácil criar uma coleção de listas derivada que imita o comportamento de uma pilha do tipo ú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 ficam no topo da pilha. A última bandeja adicionada é a primeira a ser removida. As funções membro da coleção de listas AddHead e RemoveHead podem ser usadas para adicionar e remover elementos especificamente do cabeçalho 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 de uma das classes de lista MFC existentes e adicione mais funções membro para dar suporte à funcionalidade das operações de pilha.

    O exemplo a seguir mostra como adicionar funções membro para efetuar push de elementos para a pilha, espiar o elemento do topo da pilha e tirar o elemento do topo 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 CObList subjacente. O usuário pode chamar qualquer função membro CObList, quer faça sentido para uma pilha ou não.

Filas

Como a coleção de listas padrão tem uma cabeça e uma cauda, é fácil criar uma coleção de listas derivada que imita o comportamento de uma fila do tipo primeiro a entrar, primeiro a sair. Uma fila é como uma fila de pessoas em um refeitório. A primeira pessoa na fila é a primeira a ser servida. À medida que mais pessoas vêm, elas vão para o fim da fila para esperar sua vez. As funções membro da coleção de listas AddTail e RemoveHead podem ser usadas para adicionar e remover elementos especificamente do início ou do final da lista; portanto, o elemento adicionado mais recentemente sempre é o primeiro 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 biblioteca Microsoft Foundation Class e adicione mais funções membro para dar suporte à semântica das operações de fila.

    O exemplo a seguir mostra como você pode acrescentar funções 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();
       }
    };
    

Confira também

Coleções