Pilhas

A pilha (stack) se encaixa como uma ferramenta útil e extremamente simples tendo em vista que apenas vetores apresentam formato mais simplório, temos um conjunto ordenado de dados no qual os itens são inseridos e eliminados em uma extremidade denominada topo, com duas operações nomeadas pela sua representação, empilhar (push) para inserção e desempilhar (pop) em eliminação, tais operações primitivas caracterizam este conceito abstrato para tratamento de dados.

Diferente também do que acontece nos vetores, a pilha é um objeto dinâmico e por consequência mutável em seu formato de inserir e excluir elemento do seu topo, o topo por efeito da operação será deslocado para o alto ou abaixo respectivamente. A seguir temos uma figura exemplificando o funcionamento e como o topo é alterado conforme a ação.

>

J

>

I

I

>

I

>

H

H

H

H

>

H

>

G

G

G

G

G

G

>

G

>

F

F

F

F

F

F

F

F

>

F

>

K

E

E

E

E

E

E

E

E

E

>

E

E

>

E

D

D

D

D

D

D

D

D

D

D

D

D

>

D

C

C

C

C

C

C

C

C

C

C

C

C

C

>

C

B

B

B

B

B

B

B

B

B

B

B

B

B

B

A

A

A

A

A

A

A

A

A

A

A

A

A

A

push

push

push

push

pop

pop

pop

pop

pop

push

pop

pop

Através da movimentação do topo da pilha, temos ilustrado o atributo mais importante de uma pilha, em que o ultimo elemento inserido na pilha é o primeiro elemento a ser eliminado, sendo descrita como uma fila LIFO (Last In, First Out).

Para representarmos a pilha em C, iremos implementar quatro rotinas, será empty, full, pop e push, a inclusão de empty e full parece inclusive estar contradizendo o que foi escrito anteriormente sobre as operações necessárias, e sua implementação não é uma obrigatoriedade em pilhas, mas a modularização permite aumentar a legibilidade do programa, assim optamos por uma função empty, ao invés de uma condicional testando um valor negativo e fica incluída a verificação de condições excepcionais. Quanto à função full, serve como um aviso de que a pilha sendo uma estrutura dinâmica que pode aumentar ou diminuir de tamanho pode extrapolar a área reservada e gerar um estouro ao tentar inserir um elemento além do limite.

#include <stdio.h> #define STACK_SIZE         6 int iStack[STACK_SIZE]; int iTop; int Empty(void) {        return (iTop == -1); } int Full(void) {        return (iTop == STACK_SIZE); } void Push(int i) {        if (Full())        {              fprintf(stderr, "STACK OVERFLOW\n");        }        else        {              iStack[iTop++] = i;        } } int Pop(void) {        if (Empty())        {              return (-1);        }        else        {              return (iStack[iTop--]);        } } void ShowStack(void) {        int i;        for (i = 0; i < iTop; i++)        {              printf("%i ", iStack[i]);        }        printf("\n"); } void main(void) {        Push(1);     ShowStack();        Push(2);     ShowStack();        Pop();       ShowStack();        Push(3);     ShowStack();        Push(4);     ShowStack();        Pop();       ShowStack();        Pop();       ShowStack();        Pop();       ShowStack();        Push(5);     ShowStack();        Push(6);     ShowStack();        Push(7);     ShowStack();        Pop();       ShowStack();        Push(8);     ShowStack();        Push(9);     ShowStack();        Push(10);    ShowStack();        Pop();       ShowStack();        Push(11);    ShowStack();        Push(12);    ShowStack();        Push(13);    ShowStack(); }

O resultado da execução do programa irá gerar as seguintes mensagens:

1 1 2 1 1 3 1 3 4 1 3 1 5 5 6 5 6 7 5 6 5 6 8 5 6 8 9 5 6 8 9 10 5 6 8 9 5 6 8 9 11 5 6 8 9 11 12 STACK OVERFLOW 5 6 8 9 11 12

Apesar de indicarmos o estouro de pilha, o mesmo não aconteceu da forma como indicada, na realidade o elemento não foi armazenado em vez ter sido alocado em uma região não reservada e ocasionando nesse caso um acesso indevido a memoria, vale lembrar que o programa em si não realiza nenhuma operação útil e está sendo usado para apresentar o conceito de pilha, este tipo operação proporcionado pela pilha é usado em calculadora, os compiladores da linguagem C armazenam as chamadas de função neste formato, em breve apresentaremos um modelo mais completo de uma implementação genérica de pilha junto de uma aplicação.