REPRESENTAÇÃO DE PILHA EM VETOR

É possível representar uma pilha usando um vetor, porém é necessário compreender que vetor e pilha são estruturas diferentes. Vetor apresenta uma estrutura que pressupõem a definição prévia da quantidade de elementos que existira no seu interior.

Em contrapartida, a pilha é um objeto dinâmico, porque o número de elementos aumenta ou diminui a medida que empilhamos ou desempilhamos objetos.

Essa importante observação conduz a possibilidade de ocorrer o chamado estouro de capacidade de uma pilha (“overflow”) quando um vetor é utilizado para representar uma pilha.

Para representar uma pilha utilizando a linguagem c, podemos construir uma estrutura chamada stack. No exemplo sugerido, nossa pilha poderá conter no máximo 100 elementos.

#define maxpilha100

struct stack

{

int topo;

int item [maxpilha];

};

Considerando a estrutura apresentada, uma pilha pode ser declarada da seguinte maneira:

struct stack s;

O campo topo é utilizado para sabermos qual é o elemento do topo da pilha, conforme já dito, é o topo da pilha que se movimenta conforme são empilhados ou desempilhados os elementos.

INICIANDO UMA PILHA

Uma pilha deve ser sempre iniciada antes de sua utilização, sob pena de presenciarmos comportamentos não desejados durante o uso do programa, pois quando a mesma não apresenta nenhum elemento será considerada vazia. Para representar a pilha nesse estado vazio, faremos stopo= -1 antes de qualquer ação sobre a pilha, não sendo necessario inicializar o vetor com zeros para indicar uma pilha vazia, apenas stopo= -1.

Outra opção é pensarmos em uma rotina chamada inicpilha(s), que realiza o inicio de uma pilha s.

inicpilha(s)

topo(s) ← -1

void inicpilha (struct stack *ps)

{

ps → topo= -1;

}

A chamada função inicpilha(s) seria da seguinte forma: inicpilha(&s).

EMPILHANDO UM ELEMENTO

A operação de empilhamento faz a verificação se ocorre ou não a possibilidade de estouro de capacidade da pilha (“overflow”). Só poderá ocorrer o empilhamento de um novo elemento quando o estouro de capacidade da pilha não for concretizado optamos por implementar a operação de empilhamento com a função push.

empilha (s, x)

se (pilhacheia (s)=“v”) então

imprima “Ocorreu overflow na pilha”

senão

topo(s) ← topo(s)+1

conteudo(s)[topo(s)] ← x

fim

int push(struct stack *ps, int x)

{

if(pilhacheia (ps)==1)

{

printf(“%s”, “Ocorreu overflow na pilha!\n”);

exit(1);

}

else

return (ps → item[++(ps → top)]=x);

}

Analisando a rotina push sugerida, observamos que o campo topo, possui um valor que é o próprio índice do vetor item, que será incrementado para determinarmos a posição do vetor item que receberá o valor presente em x. Por exemplo, se a pilha está vazia, o topo será igual a -1. Ao ser empilhado o primeiro elemento na pilha, s topo irá para um ponto importante é que a chamada função pilhacheia(ps), o operador de endereço “&” não está presente. Isso acontece porque “ps” já é um ponteiro.

A chamada função push poderá ser: push(&s, x);

DESEMPILHANDO UM ELEMENTO

Essa operação realiza o inverso da operação de empilhamento, ou seja, se existir um elemento na pilha, ocorrerá o desempilhamento do elemento que estiver no topo da pilha, que será retirado dessa pilha é necessário haver a verificação do estado da pilha antes de executar a operação de desempilhamento. Sua implementação é feita com o nome pop.

desempilha(s)

se(pilhavazia(s)= “v”) então

imprima “Ocorreu underflow na pilha”

senão

desempilha ← conteudo(s)[topo(s)]

topo(s) ← topo(s)-1