Criando coleções de pilhas e filas

Artigo
06/16/2023

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

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

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

Compartilhar via