10.LabII.PilhaFila

Prévia do material em texto

Laboratório de Programação II 
Departamento de Ciência da Computação 
UFJF 
Aula de hoje 
• TAD Pilha 
– Pilha com Lista Encadeada 
• TAD Fila 
– Fila com Lista Encadeada 
 
• Pilha é uma lista onde todas 
as inclusões e exclusões de 
nós são feitas em uma única 
extremidade. 
• Usa-se o critério de retirar em 
primeiro lugar o último nó que 
foi incluído na lista. 
• FILO (First In Last Out) 
Pilhas 
3 
Fila 
• Fila é uma lista onde todas as inclusões são feitas em 
uma extremidade e todas as exclusões na outra 
extremidade. 
• Usa-se o critério de retirar em primeiro lugar o 
primeiro nó incluído na lista. 
• Este critério é chamado de FIFO (First In First Out). 
• Esta estrutura é equivalente a uma fila de banco. 
 
Pilha e Fila 
• Vamos trabalhar com representações de Pilha e Fila 
com encadeamento dos nós. 
• O TAD Nó já foi apresentado para listas encadeadas, 
mas vamos revisa-lo. 
class No 
{ 
 private: 
 float info; 
 No* prox; 
 public: 
 No(); 
 ~No(); 
 void atribInfo(float val); 
 void atribProx(No* p); 
 float consultaInfo(); 
 No * consultaProx(); 
}; 
 
No::No() { } 
 
void No::atribInfo(float val) { info = val; } 
 
void No::atribProx(No* p) { prox = p; } 
 
float No::consultaInfo() { return info; } 
 
No* No::consultaProx() { return prox; } 
 
No::~No() { } 
 
Pilha Encadeada 
class PilhaEncadeada 
{ 
 private: 
 No* topo; // ponteiro p/ o No do topo 
 
 public: 
 PilhaEncadeada(); 
 ~PilhaEncadeada(); 
 float consultaTopo(); 
 void empilha(float val); // insere No no Topo
 
 void desempilha(); // elimina No do Topo 
 bool vazia(); // verifica se está vazia 
}; 
 Xn Xn – 1 X2 X1 
topo 
Pilha Encadeada 
// construtor 
PilhaEncadeada::PilhaEncadeada() 
{ 
 topo = NULL; 
} 
 
// destrutor 
PilhaEncadeada::~PilhaEncadeada() 
{ 
 No* p = topo; 
 while(topo != NULL) 
 { 
 topo = p->consultaProx(); 
 delete p; 
 p = topo; 
 } 
} 
 
Pilha Encadeada 
void PilhaEncadeada::empilha(float val){ 
 No* p = new No(); 
 p->atribInfo(val); 
 p->atribProx(topo); 
 topo = p; 
} 
 
void PilhaEncadeada::desempilha(){ 
 No* p; 
 if(topo != NULL) 
 { 
 p = topo; 
 topo = p->consultaProx(); 
 delete p; 
 } else { 
 cout << “Erro” << endl; exit(1); 
 } 
} 
 
Pilha Encadeada 
float PilhaEncadeada::consultaTopo() 
{ 
 if(topo != NULL) 
 return topo->consultaInfo(); 
 else 
 { 
 cout << “Pilha vazia!“ << endl; 
 exit(1); 
 } 
} 
 
bool PilhaEncadeada::vazia() 
{ 
 if(topo == NULL) 
 return(true); 
 else 
 return(false); 
} 
Fila Encadeada 
class FilaEncadeada 
{ 
 private: 
 No *ini, *fim; // ponteiros para os No’s extremos 
 public: 
 FilaEncadeada(); 
 ~FilaEncadeada(); 
 float consultaInicio(); 
 void entra(float val); // insere No no fim
 
 void sai(); // elimina No do início da fila 
 bool vazia(); // verifica se fila está vazia 
}; 
Fila Encadeada 
FilaEncadeada::FilaEncadeada() 
{ 
 ini = NULL; 
 fim = NULL; 
} 
 
FilaEncadeada::~FilaEncadeada() 
{ 
 No* p = ini; 
 while(ini != NULL) 
 { 
 ini = p->consultaProx(); 
 delete p; 
 p = ini; 
 } 
 fim = NULL; 
} 
bool 
FilaEncadeada::vazia() 
{ 
 
 if(ini == NULL) 
 return true; 
 else 
 return false; 
} 
 
Fila Encadeada 
void FilaEncadeada::entra(float val){ 
 No* p = new No(); 
 p->atribInfo(val); 
 p->atribProx(NULL); 
 if(fim == NULL) 
 ini = p; 
 else 
 fim->atribProx(p); 
 fim = p; 
} 
 
float FilaEncadeada::consultaInicio(){ 
 if(ini != NULL) return ini->consultaInfo(); 
 else { 
 cout << “Fila vazia!“ << endl; 
 exit(1); 
 } 
} 
Fila Encadeada 
void FilaEncadeada::sai() 
{ 
 No* p; 
 if(ini != NULL){ 
 p = ini; 
 ini = p->consultaProx(); 
 
 if(ini == NULL) 
 fim = NULL; 
 delete p; 
 } 
 else 
 { 
 cout << “Fila vazia” << endl; 
 exit(1); 
 } 
} 
 
Exercícios 
1. Desenvolver a operação, tanto para o TAD 
Pilha quanto para o TAD Fila, Imprimir(). Esta 
operação deve mostrar os elementos da pilha do 
topo para o final e do início para fim da fila. 
Exercícios 
2. Modifique o TAD Pilha Encadeada de forma que 
este guarde o número de itens que estão na Pilha. 
Implemente uma operação tamanho() que retorna 
quantos itens possuem na pilha. 
 
3. Implementar uma função Inverte() que, dado um 
vetor V com n números reais, cria e retorna um 
novo vetor com os elementos de V na ordem 
inversa. Utilizar uma pilha para realizar esta 
inversão. A função Inverte() não deve ser uma 
operação do TAD PilhaEncadeada. 
 
Exercícios 
4. Considere uma pilha P vazia e uma fila F não 
vazia. Utilizando as operações de fila (vazia, entra 
e sai) e pilha (vazia, empilha e desempilha), e 
uma variável auxiliar do tipo float, escreva uma 
função que inverta a ordem dos elementos da 
fila. 
Exercícios 
5. Desenvolver uma função (não uma operação) 
para, dadas duas filas F1 e F2, criar e retornar uma 
nova fila que representa a concatenação destas 
duas filas (sem repetição de valores). Considere que 
as filas F1 e F2 não possuem valores repetidos e 
tanto F1 quanto F2 tornam-se vazias após a 
concatenação. 
Obs: Deve-se implementar uma operação lógica 
para verificar se um valor não se encontra na fila 
antes de adicioná-lo à esta fila. 
Exercícios 
6. Utilizando as operações de manipulação de 
pilhas (vazia, empilha, desempilha) , uma pilha 
auxiliar Paux e uma variável do tipo float, 
escrever uma função para remover um item com 
valor C de uma posição qualquer da pilha. 
Exemplo: Pilha (9, 2, 5, 6, 1) Topo = 9 
 Remove(5) 
 Saída: Pilha (9, 2, 6, 1) Topo = 9 
Exercícios 
7. Escreva um programa para converter um número 
de notação decimal em um número expresso em 
um sistema de número cuja base (ou raiz) é um 
número entre 2 e 9. A conversão é realizada pela 
divisão repetitiva, pela base, à qual um número está 
sendo convertido, e então tomando-se os restos da 
divisão na ordem inversa. Por exemplo, para 
converter para binário, o número 6 exige três de 
tais divisões: 6/2 = 3 com resto 0, 3/2=1 com resto 1 
e, finalmente, 1/2 = 0 com resto 1. Os restos 0, 1 e 1 
são colocados na ordem inversa, de modo que o 
binário equivalente de 610 é igual a 110 na base 2. 
Exercícios 
8. Usando obrigatoriamente uma estrutura de 
pilha, implemente uma função que verifica se 
um dado vetor de N inteiros é um palíndromo, 
ou seja, se ele é o mesmo quando lido da 
esquerda para a direita ou da direita para a 
esquerda. 
Exemplo: {1,2,3,4,5,4,3,2,1} é palíndromo, 
{1,2,3,6,7,8} não é palíndromo. 
Exercícios 
9. Faça um programa para verificar se uma 
expressão aritmética está com o número de 
parênteses corretamente balanceado, ou seja, 
para cada parêntese aberto deve existir um 
parêntese fechado. 
Exemplo: (3+(4*3)/2)+1 está ok, mas (((3 * 4)+ 
2) não está!