ExercíciosFila_Pilha. resolvidos

Prévia do material em texto

Exercícios sobre Pilha e Fila
Para todos os exercícios aqui propostos utilizar as implementações baseadas em ponteiros. Caso seja 
necessário, altere o tipo de dado a ser utilizado (char para int). 
Pilha
1) Implemente uma função que retorna se duas pilhas são iguais.
Protótipo: bool PilhasIguais(Pilha&, Pilha&).
Possível implementação:
bool PilhasIguais(Pilha& P1, Pilha& P2){
 Pilha Aux1, Aux2; // Declarando pilhas auxiliares
 IniciaPilha(Aux1);
 IniciaPilha(Aux2);
 char v1, v2;
 bool flag = true;
 while(!PilhaVazia(P1) && !PilhaVazia(P2) && flag){
 Desempilha(P1,v1);
 Desempilha(P2,v2);
 Empilha(Aux1,v1);
 Empilha(Aux2,v2);
 if(v1 != v2) // se os valores não são iguais, configura flag para FALSE
 flag = false;
 }
 if ((PilhaVazia(P1) && !PilhaVazia(P2)) || (!PilhaVazia(P1) && PilhaVazia(P2)))
 flag = false; // se as pilhas tem tamanhos diferentes, configura flag para FALSE
 while(!PilhaVazia(Aux1) && !PilhaVazia(Aux2)){ // retorna os valores para as pilhas originais
 Desempilha(Aux1,v1);
 Desempilha(Aux2,v2);
 Empilha(P1,v1);
 Empilha(P2,v2);
 }
 return flag; // retorna True ou False conforme valores das pilhas
}
2) Implemente uma função que retira um elemento específico de uma pilha. A Figura 1 mostra o 
funcionamento dessa função. Protótipo: bool DesempilhaX(Pilha &, char).
Possível implementação:
bool DesempilhaX(Pilha &Topo, char Elemento){
 bool flag = false; // variável de controle
 char elemento;
 No *Aux = new No; // Pilha auxiliar
 Aux = NULL;
 while(Desempilha(Topo,elemento)) // enquanto pilha não estiver vazia, desempilhar
 if(elemento != Elemento) // se não é o elemento certo, empilhar na auxiliar
 Empilha(Aux,elemento);
 else flag = true; // se encontrou o elemento, ajusta o flag para verdadeiro 
 while(Desempilha(Aux,elemento)) // retornar os elementos para a pilha original
 Empilha(Topo,elemento);
 return flag; // retornar o flag – encontrou ou não o elemento na pilha
}
Figura 1 - Exemplo do funcionamento 
da função DesempilhaX().
3) Implemente uma função para inverter os valores em uma pilha. A Figura 2 mostra o funcionamento dessa 
função. Protótipo: void inverte(Pilha &).
Possível implementação:
void inverte(Pilha &Topo){
 char elemento;
 No *Aux = new No; // declara pilha auxiliar
 Aux = NULL;
 while (Desempilha(Topo,elemento)) // enquanto a pilha não estiver vazia, retira os elementos
 Empilha(Aux,elemento); // empilha na pilha auxiliar
 Topo = Aux; // faz o ponteiro Topo (pilha inicial) apontar para a nova pilha invertida
}
4) Implemente uma função que retorna o somatório de todos os elementos de uma pilha de inteiros.
Protótipo: int SomaElementosPilha(Pilha &).
Possível implementação:
int SomaElementosPilha(Pilha& Topo){
 int elemento;
 int soma = 0;
 No *Aux = new No; // declara pilha auxiliar
 Aux = NULL;
 while (Desempilha(Topo,elemento)){ // enquanto a pilha não estiver vazia, retira os elementos
 soma += elemento; // soma os elementos da pilha original 
 Empilha(Aux,elemento); // empilha na pilha auxiliar
 }
 while (Desempilha(Aux,elemento)) // retorna os elemento para a pilha original
 Empilha(Topo,elemento);
 return soma; // retorna o valor da soma dos elementos da pilha
}
Figura 2 - Exemplo do funcionamento da função 
inverte().
Fila 
1) Implemente uma função que retira de uma fila todas as ocorrências de um determinado elemento. A 
Figura 3 mostra o funcionamento da função onde foi pedido para retirar todas as ocorrências do valor -3.
Protótipo: bool RetiraTodosX(Fila&, int).
Possível implementação:
bool RetiraTodosX(Fila& F, int elemento){
 int n = F.Nro; // tamanho da fila
 bool flag = false;
 int dado;
 for(int i=1; i <= n; i++){ // retira todos os elementos da fila conforme seu tamanho
 RetiraFila(F,dado);
 if(dado != elemento) // se o dado for diferente insere na fila novamente
 InsereFila(F,dado);
 else flag = true;
 }
 return flag; // retorna se encontrou ou não o dado para retirar
}
2) Implemente uma função que retorna o menor elemento em uma fila de inteiros.
Protótipo: int MenorFila(Fila&).
Possível implementação:
int MenorFila(Fila& F){
 int dado;
 int n = F.Nro; // tamanho da fila
 RetiraFila(F,dado); // pega o primeiro elemento para comparação
 int menor = dado;
 InsereFila(F,dado); // retorna o primeiro elemento na fila
 for(int i=2; i <= n; i++){ // retira o restante dos elementos para comparação
 RetiraFila(F,dado);
 if(dado < menor) // seleciona o menor
 menor = dado;
 InsereFila(F,dado); // insere novamente na fila
 }
 return menor; // retorna o menor elemento da fila
}
3) Faça uma função para inverter os elementos de uma fila. Protótipo: void InverteFila(Fila&).
Possível implementação:
void InverteFila(Fila& F){
 int tam = F.Nro; // número de elementos na fila
 int *vet;
 int dado, i = 0;
 vet = new int [tam]; // aloca um vetor do tamanho tam
 while(RetiraFila(F,dado)) // retira todos os dados da fila e insere em um vetor 
 vet[i++]=dado;
 i = tam - 1;
 while(i>=0) // retira os dados do vetor do fim para o início e insere na fila
 InsereFila(F, vet[i--]);
}
Figura 3 - Funcionamento da função 
RetiraTodosX() para o valor -3.