ED AP03 Pilha

Definição
Operações essenciais para manipular pilhas
Exemplos
Algoritmos para manipulação de pilhas

Definição

Uma pilha é um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas numa mesma extremidade, denominada topo.
Em uma pilha o último elemento a ser inserido (empilhado), é o primeiro a ser removido (desempilhado). Esse é o motivo das pilhas serem também conhecidas como uma estrutura LIFO (Last In, First Out).

Estrutura da Pilha

Remoções
Inserções

Fim (topo)

Inicio (base)

Operações sobre pilhas

Uma pilha suporta três operações básicas:
•Top: acessa o elemento posicionado no topo da pilha;
•Push: insere um novo elemento no topo da pilha;
•Pop: remove um elemento do topo da pilha.

•Sendo P uma pilha e x um elemento qualquer, a operação Push(P,x) aumenta o tamanho da pilha P, acrescentando o elemento x no seu topo. A operação Pop(P) faz com que a pilha diminua, removendo e retornando o elemento existente em seu topo. A operação Top(P) simplesmente retorna uma cópia do elemento existente no topo da pilha, sem removê-lo.

Operações para manipulação de pilhas

InicPilha(s) : inicializa a pilha “s” no estado vazio;
PilhaVazia(s) : Retorna V, se a pilha “s” estiver vazia;

PilhaCheia(s) : Retorna V, se pilha “s” estiver cheia.

3.3.Exemplo

Digitar um número inteiro positivo em decimal e mostrar o número no sistema binário.

Para converter um número decimal para binário, devemos dividi-lo sucessivamente por 2, até obtermos um quociente igual a 0. Os restos obtidos nas divisões devem ser tomados em ordem inversa.

13 2 6 2 3 2 1 2
- 12 -6 -2 - 0 6 3 1 0

Assim, o valor 13 decimal fica 1101 em binário

Implementação em C++ (Pilha.h)

#include<conio.h>
#include<stdlib.h>