Torre de hanoi

Aula Prática – Pilha

Considere o Tipo Abstrato de Dado (TAD) Pilha que representa uma pilha de caracteres:

typedef struct pilha Pilha;

/* Cria uma pilha de caracteres */

Pilha* pilha_cria();

/* Empilha caractere no topo de pilha */

void pilha_push (Pilha* pilha,char caractere);

/* Desempilha um caractere do topo de pilha e retorna este caractere*/

char pilha_pop(Pilha* pilha);

/* Imprime o conteúdo da pilha */

void pilha_imprime(Pilha* pilha);

/* Retorna 1 se pilha estiver vazia, senão retorna 0 */

int pilha_vazia (Pilha* pilha);

/* Libera a estrutura da Pilha */

void pilha_libera (Pilha* pilha);

1. Implemente este TAD.

2. Implemente uma função que receba duas pilhas, p1 e p2, e verifique se elas são iguais, ou seja se elas possuem os mesmos elementos na mesma ordem. Caso elas sejam iguais a função deve retornar 1, caso contrário ela retornará 0. Ao final desta função, as pilhas p1 e p2 devem conter todos os valores originais e as ordens dos elementos originais das pilhas não devem estar alteradas. Essa função deve obedecer ao protótipo:

int iguais(Pilha* p1, Pilha* p2);

3. Implemente uma função que receba duas pilhas, p1 e p2, e passe todos os elementos da pilha p2 para o topo de p1, como ilustrdo na figura abaixo. Note que ao final dessa função, a pilha p2 vai estar vazia, e a pilha p1 conterá todos os elementos das 2 pilhas. Essa função deve obedecer ao protótipo:

void concatena_pilhas (Pilha* p1, Pilha* p2);

[pic]

4. Torres de Hanói é um quebra-cabeça muito antigo conhecido. Ele é constituído de um conjuntode N discos de tamanhos diferentes e três pinos verticais, nos quais os discos podem ser encaixados.
[pic]
Cada pino pode conter uma pilha com qualquer número de discos, desde que cada disco não seja colocado acima de outro disco de menor tamanho. A configuração inicial consiste de todos os discos no