# Estruturas de Dados Intermediário/Pilhas

Pilha ou stack é um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas pela mesma extremidade chamada topo.
Os elementos são removidos na ordem inversa daquela em que foram inseridos de modo que o último elemento que entra é sempre o primeiro que sai, por isto este tipo de estrutura é chamada LIFO (Last In - First Out).
O exemplo mais prático que costuma utilizar-se para entender o processo de pilha é como uma pilha de livros ou pilha de pratos, no qual ao se colocar diversos elementos uns sobre os outros, se quisermos pegar o livro mais abaixo deveremos tirar todos os livros que estiverem sobre ele."

## Operações sobre pilhas

Uma pilha geralmente suporta três operações básicas:
* TOP: acessa-se o elemento posicionado no topo da pilha;
* PUSH: insere um novo elemento no topo da lista;
* POP: remove o elemento do topo da lista.
Se tivermos uma pilha p e um elemento x qualquer, a operação PUSH (p,x) acrescenta o elemento x no topo da pilha e aumenta-lhe o tamanho. Já a operação POP(P) remove o elemento que está no topo da pilha fazendo com que esta diminua. Já a operação TOP não altera o tamanho da estrutura , pois simplesmente visita o topo da pilha retornado uma cópia do elemento que encontra-se no seu topo.

### Visualização do comportamento de uma pilha

Na tabela abaixo é descrito o comportamento de uma pilha. A primeira coluna descreve qual operação é efetuada sobre uma pilha que inicia vazia, a segunda coluna descreve os elementos da pilha e como estão organizados (estando o "topo" à direita), visualização descreve o elemento visitado quando utilizado o TOP e a quarta coluna mostra a quantidade de elementos na pilha.
| Operação | Pilha | Visualização | Tamanho da Pilha |
| PUSH (P,1) | 1 | | 1 |
| PUSH (P,2) | 1,2 | | 2 |
| TOP | 1,2 | 2 | 2 |
| PUSH (P,3) | 1,2,3 | | 3 |
| POP (P) | 1,2 | | 2 |
| POP (P) | 1 | | 1 |
| POP (P) | | | 0 |

### Operações auxiliares

Ao implementar uma pilha dentro do computador a quantidade de memória alocada funciona como um dos fatores limitantes da pilha. Assim são necessárias mais três operações para manipular corretamente a estrutura.
* INIT: inicia a pilha como "Vazia"
* IS_EMPTY: verifica se a pilha está "Vazia"
* IS_FULL: verifica se a pilha está "cheia"
Toda vez que criamos uma estrutura de pilha, esta deve ser inicializada para garantir que não haja nenhuma "sujeira" no local onde esteja montada. Para verificar se uma pilha P está vazia, devemos usar uma função Is_Empty(P) que retorna verdadeiro se uma pilha estiver vazia. A função Is_Full (P) é utilizada para verificar se a pilha está cheia, retornando verdadeiro caso não haja espaço para armazenar mais elementos.
Is_Full não é o contrário de Is_Empty. Quando Is_Empty retorna falso, não siginifica no entanto que ela esteja cheia. Do mesmo modo se uma função Is_Full retorna falso não significa que a pilha esteja vazia.

## Aplicações de Pilhas

Pilhas são utilizados em diversas aplicações em Ciências da Computação. Um dos mais salientes casos é a análise de expressões e sintaxe. Calculadores que utilizam a Notação Polonesa Reversa utilizam pilha para expressar seus valores, podendo ser representadas de forma prefixa, posfixa ou infixa. Conversões de uma forma de expressão para outras também necessitam de pilhas. Muitos compiladores utilizam pilhas para análise sintática de expressões, blocos de programas e afins.

### Exemplo de uso de pilha em Notação Polonesa Reversa

Por exemplo: ((1 + 2) * 4) + 3 em notação pós-fixa
Utilizando uma pilha consideramos:
* empilhar quando encontrar um operando;
* sacar dois operandos e achar o valor quando encontrar uma operação.
* empilhar o resultado.
| Entrada | Operação | Pilha |
| 1 | push operando | 1 |
| 2 | push operando | 1, 2 |
| + | adicionar | 3 |
| 4 | Push operando | 3, 4 |
| * | multiplicar | 12 |
| 3 | push operando | 12, 3 |
| + | adicionar | 15 |
O resultado final 15 estará no topo da pilha no fim do cálculo.

## Aula-Auxílio

* Notação Polonesa