Pilha e Fila - Os Algorítmos Clássicos

Na série sobre Listas Ligadas, mencionei dois tipos especializados de listas lineares: Pilha e Fila. Neste post vou apresentar os algorítmos clássicos de implementação destes tipos usando alocação sequencial.

Pilha

Uma pilha é uma lista onde as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido primeiro é o que foi inserido por último (LIFO - Last In First Out). As pilhas são úteis quando queremos armazenar temporariamente uma informação que vamos usar logo depois. Por exemplo, a maioria dos processadores utiliza uma pilha para armazenar os endereços de retorno de subrotinas, permitindo que subrotinas sejam chamadas dentro de subrotinas. Algorítmos recursivos (como o quicksort) também costumam usar pilhas.

É costume chamar a operação de inserção na pilha de Push e a inserção de remoção de Pop (na inserção estamos 'empurrando' um elemento no alto da pilha e na remoção o elemento no topo 'pula' para fora da pilha).

A implementação de uma pilha é muito simples. Temos um vetor de N posições para armazenar os elementos e um índice (ou ponteiro) para indicar o topo. Algumas variações são possíveis:

• Podemos empilhar os itens no sentido de índices (ou endereços) crescentes ou decrescentes.
• O índice do topo pode apontar para a posição de remoção ou para a posição de inserção.

Duas situações de erro devem ser previstas: tentar inserir um item em uma pilha cheia (overflow) e tentar remover um item de uma pilha vazia (underflow).

Segue um exemplo de implementação em C, empilhando no sentido de índices crescentes e com o índice de topo apontando para a posição de inserção. Neste exemplo a pilha contém ponteiros e o valor NULL é usado para indicar underflow.

#define N 10 // número de elementos na pilha
void *pilha[N]; // a pilha
int topo = 0; // índice para o topo da pilha

// Coloca um elemento no topo da pilha
// Retorna FALSE se pilha cheia
int Push (void *elemento)
{
   if (topo == N)
       return FALSE;
   pilha [topo++] = elemento
   return TRUE;
}

// Retira o elemento no topo da pilha
// Retorna NULL se pilha vazia
void *Pop ()
{
   if (topo == 0)
       return NULL;
   return pilha [--topo];
}

(Esta implementação é também um exemplo clássico do uso dos operadores de pós incremento e pré decremento do C).

Fila

Uma fila é uma lista onde as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra. Desta forma remove-se sempre o item mais antigo (FIFO - First In First Out). AS filas são úteis para sincronizar duas tarefas assíncronas, armazenado temporariamente dados produzidos por uma delas até serem consumidos pela outra.

Quando examinamos as listas genéricas sequenciais , verificamos que era preciso mover os elementos após uma inserção ou remoção. No caso específico da fila isto pode ser evitado implementando uma fila circular, na qual os ponteiros voltam ao início quando passam do final.

A forma mais convencional de implementar uma fila circular é ter um vetor de N+1 elementos e dois índices (ou ponteiros), um apontando para onde será feita a próxima inserção e outro apontando para onde será feita a próxima remoção. A fila vazia é indicada pela igualdade dos índices (ou ponteiros). Para não confundir fila cheia com fila vazia, deixa-se sempre pelo menos uma posição livre no vetor (daí ele ter N+1 posições para armazenar N elementos).

#define N 10  // número máximo de elementos na fila
void *fila [N+1]; // a fila
int iPoe = 0;  // indice para onde inserir
int iTira = 0;  // indice para onde retirar

// Coloca um elemento na fila
// Retorna FALSE se fila cheia
int Poe (void *elemento)
{
   int aux;

   // calcula o valor de pPoe após a inserção
   aux = iPoe + 1;
   if (aux > N)
       aux = 0; // circula

   // Testa fila cheia
   if (aux == iTira)
       return FALSE;

   // Coloca na fila
   fila [iPoe] = elemento
   iPoe = aux;
}

// Retira elemento da fila
// Retorna NULL se fila vazia
void *Tira ()
{
   void *aux;

   // Testa fila vazia
   if (iPoe == iTira)
       return NULL;

   // Pega o elemento a retirar
   aux = fila [iTira];

   // Avanca iTira
   iTira = iTira + 1;
   if (iTira > N)
       iTira = 0; // circula

   return aux;
}

Um truque comum é usar uma potência de pois para N+1 e fazer o índice dar a volta através de um AND. Por exemplo, Se N+1 for 16, o avanço de iTira no final da rotina Tira pode ser simplificado para

iTira = (iTira+1) & 15;