Engenharia de computacao

Ministério da Educação

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
Campus Cornélio Procópio

Estruturas de dados, pesquisa e ordenação Na estrutura de dados chamada Pilha existe uma disciplina de acesso aos dados. É a disciplina de acesso que define a forma como os elementos são inseridos e removidos da estrutura.
Pilha

A Figura abaixo apresenta a estrutura de uma pilha.

7 6 5 4 3 2 1 d b x a
Topo 4

Na Pilha a disciplina de acesso é chamada de LIFO (Last In First Out - último elemento a entrar é o primeiro a sair). Os elementos são sempre inseridos ou removidos de uma posição chamada topo da pilha. Desta forma o último a ser inserido (no topo) será o primeiro a ser removido (do topo). No exemplo da figura a inserção ocorreria na posição 5 (exatamente acima do topo) e a remoção ocorreria na posiçõa 4 (o topo atual da pilha). O nome das operações que inserem e removem dados na pilha são respectivamente empilha e desempilha. É também comum usar as expressões correspondentes em Inglês push(empilha) e pop (desempilha). Implementação de pilha usando vetor É possível implementar pilha usando vetor ou alocação dinâmica. Na primeira opção o tamanho da pilha fica limitado ao tamanho do vetor declarado no programa, isto é, o tamanho da pilha é definido em tempo de compilação. No segundo caso o tamanho da pilha é definido em tempo de execução.
Nesta seção será apresentada a implementação de pilha usando vetor. Como exemplo de uma implementação em C, um tipo de dado pilha será definido em uma struct contendo uma variável para indicar o topo da pilha e um vetor para armazenar os elementos da pilha. É necessário também definir as diciplinas de acesso. Estas são definidas através das funções push e pop. Outras funções auxiliares podem também ser

definidas como “consultar o topo da pilha sem desempilhar”, “verificar se a pilha está vazia”, “verificar se a pilha está cheia”. Abaixo uma descrição breve do que cada função deve fazer: push Pilha SIM: !