7 de dez de 2012

Pilha em C.

Vamos dar uma olhada em pilha e suas operações básicas...
Para ter uma ideia melhor sobre pilha, pense que você está lavando pratos e para isso você empilha os pratos em uma única pilha, desta forma quando você colocar um novo prato na pilha este será colocado no topo da pilha e quando você tirar um para lavar ira retira-lo também do topo.

Tendo a ideia de pilha em mente percebe-se que a grande sacada é a inserção de novos elementos e remoção no inicio de uma lista comum, desta forma você poderá utilizar qualquer tipo de lista para implementar uma pilha, hoje vamos ver uma pilha usando lista estática encadeada.

Nossa estrutura então será a mesma de uma lista estática encadeada:
#define MAX 30
struct pilha{
    int v[MAX];
    int topo;
};

No caso desta pilha serão necessárias as funções:
int inicializar_pilha(Pilha *p);
int pilha_vazia(Pilha p);
int pilha_cheia(Pilha p);

mais estas você pode ver no tutorial Lista com alocação estática e acesso sequencial em C. pois serão idênticas.
Agora o grande truque para transforma a até então lista estática sequencial em um pilha:
A inserção e remoção no inicio da lista(TOPO DA PILHA).

Inserção:
int empilha(Pilha *p, int elem)
{
    if(pilha_cheia(*p))
        return 0;

    (*p)->topo++;
    (*p)->v[(*p)->topo] = elem;
    return 1;
}

Remoção:
int desempilha(Pilha *p, int *elem)
{
    if(pilha_vazia(*p))
        return 0;

    *elem = (*p)->v[(*p)->topo];
    (*p)->topo--;
    return 1;
}

Então é isso, tendo a ideia de pilha concretizada você poderá implementa-la utilizando qualquer tipo de lista, de acordo com o que melhor atender suas necessidades.

Caso ainda não tenha visto de uma olhada, vale apena:

Lista com alocação estática e acesso sequencial em C.
Lista com alocação dinâmica encadeada em C.
Lista utilizando nó-cabeçalho em C.
Lista com encadeamento circular em C.
Lista Duplamente Encadeada em C.

Nenhum comentário:

Postar um comentário