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.
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!