# Algoritmos e Estruturas de Dados/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 do programa inversa daquela em que foram inseridos de modo que o último elemento que entra é sempre o primeiro ser executado , por isto este tipo de estrutura é chamada LIFO (Last In - First Out) ou FILO (First In - Last 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 4 operações básicas:
* TOP: acessa-se o elemento posicionado no topo da pilha;
* PUSH: insere um novo elemento no topo da pilha;
* POP: remove o elemento do topo da pilha.
* PULL:altera o elemento posicionado no topo da pilha;
As pilhas são úteis quando queremos armazenar temporariamente uma informação que vamos usar logo depois. 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ência da Computação. Um dos mais salientes casos é a análise de expressões e sintaxe. Calculadores que utilizam a Notação Polonesa Inversa ( ou RPN na sigla em inglês, de Reverse Polish Notation), utilizam pilha para expressar seus valores, podendo ser representadas de forma prefixa, pós-fixa 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 Inversa

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.

## Ver também

* Notação Polonesa

## Bibliografia

* Stack program in c++
* Stack Machines - the new wave
* Bounding stack depth
* Libsafe - Protecting Critical Elements of Stacks
* Stack Size Analysis for Interrupt-driven Programs (322 KB)
* Stack Implementation ( Graphical & Text Mode) C Language implementation of Stack
* Pointers to stack visualizations