fila

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