Uma das estruturas de dados mais simples é a pilha. Possivelmente por essa razão, é a estrutura de dados mais utilizada em programação.

Para entendermos o funcionamento de uma estrutura de pilha, podemos fazer uma analogia com uma pilha de pratos. Se quisermos adicionar um prato na pilha, o colocamos no topo. Para pegar um prato da pilha, retiramos o do topo. Assim, temos que retirar o prato do topo para ter acesso ao próximo prato. A estrutura de pilha funciona de maneira análoga. Cada novo elemento é inserido no topo, e só temos acesso ao elemento do topo da pilha.

A idéia fundamental sobre pilha é que todo acesso a seus elementos é feito a partir do seu topo.

Isto faz com que os elementos da pilha sejam retirados na ordem inversa à ordem em que foram introduzidos: o primeiro que sai é o último que entrou (a sigla LIFO – last in, first out – é usada para descrever esta estratégia).

Existem duas operações básicas que devem ser implementadas numa estrutura de pilha:

  • a operação para empilhar um novo elemento, inserindo-o no topo;
  • a operação para desempilhar um elemento, removendo-o do topo.

  • É comum nos referirmos a essas duas operações pelos termos em inglês push (empilhar) e pop (desempilhar).

Ilustração do funcionamento conceitual de uma pilha P.

a
a

push(P,a)

push(P,a)...

topo 

topo 
P
P
Text is not SVG - cannot display
b
b
a
a

push(P,b)

push(P,b)...

topo 

topo 
P
P
Text is not SVG - cannot display


c
c
b
b
a
a

push(P,c)

push(P,c)...

topo 

topo 
P
P
Text is not SVG - cannot display
b
b
a
a

pop(P) – Devolve c

pop(P) – Devolve c...

topo 

topo 
P
P
Text is not SVG - cannot display


d
d
b
b
a
a

push(P,d)

push(P,d)...

topo 

topo 
P
P
Text is not SVG - cannot display
b
b
a
a

pop(P) – devolve d

pop(P) – devolve d...

topo 

topo 
P
P
Text is not SVG - cannot display

O exemplo de utilização de pilha mais próximo é a própria pilha de execução da linguagem C. As variáveis locais das funções são dispostas numa pilha e uma função só tem acesso às variáveis que estão no topo (não é possível acessar as variáveis locais às outras funções).

Conjunto de valores:

  • Quaisquer elementos (com mesmas características) a ser empilhados.

Operações Básicas:

  • EMPILHA: Insere um elemento (push).
  • DESEMPILHA: Remove um elemento (pop).
  • VAZIA: Verifica se a pilha está vazia.

Estrutura básica de uma Pilha:

typedef struct {
    int topo;
    char dados[50];
} Pilha;

Operação Vazia:

int empty(Pilha *p1) {
    return (p1->topo == -1);
}

Operação PUSH:

void push(Pilha *p1, char simbolo) {
    if(p1->topo == 49) {
        printf("\nPilha CHEIA!!!\n");
    } else {
        p1->topo++;
        p1->dados[p1->topo] = simbolo;
    }
}

Operação POP:

char pop(Pilha *p1) {
    char resposta;
    if(empty(p1)) {
        printf("\nPilha VAZIA!!!\n");
    } else {
        resposta = p1->dados[p1->topo];
        p1->topo--;
        return resposta;
    }
}

Um grande abraço e até o próximo post!