05.ED.Pilhas e Filas-2014-1

Prévia do material em texto

DCC013 
 
Estruturas de Dados 
Pilhas e Filas 
 
Definição 
 São listas que possuem uma disciplina de 
acesso: 
 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. 
 Este critério é conhecido como FILO (First In Last 
Out). 
 A ideia desta estrutura é a de uma pilha de pratos. 
Pilhas e Filas 
2 
Definição 
 Visão genérica da estrutura de dados pilha: 
Pilhas e Filas 
3 
FUNDO 
EMPILHA DESEMPILHA 
TOPO 
X1 
X2 
X3 
Xn - 1 
Xn 
Definição 
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. 
Pilhas e Filas 
4 
Definição 
 Visão genérica da estrutura de dados fila: 
Pilhas e Filas 
5 
X1 X2 X3 X Xn ENTRA 
FIM INÍCIO 
SAI 
n-1 
X 
n-2 
Representação por contiguidade dos nós 
 Esquematicamente, seja uma pilha contígua de n 
nós: 
Pilhas 
6 
 
0 1 2 . . . n-1 n . . . m-1 
 
 X = NO0 NO1 NO2 . . . NOn-1 - . . . - 
 
 topo 
 n - 1 
 
 Desta forma, o TAD TPilhaCont de elementos 
reais poderia ser: 
TAD TPilhaCont 
Pilhas 
7 
class TPilhaCont 
{ 
 private: 
 int m; // capacidade máxima de elementos do vetor 
 int topo;// índice do No que está no topo da pilha 
 float *X; // vetor que armazena a pilha 
 public: 
 TPilhaCont(int tam); 
 float ConsultaTopoPC(); 
 void EmpilhaPC(float val); // insere No no Topo
 
 void DesempilhaPC(); // elimina No do Topo 
 bool VaziaPC(); // verifica se pilha está vazia 
 ~TPilhaCont(); 
}; 
 
0 1 2 . . . n-1 n . . . m-1 
 
 X = NO0 NO1 NO2 . . . NOn-1 - . . . - 
 
 topo 
 n - 1 
 
 Construtor e destrutor: 
Pilhas 
8 
TPilhaCont::TPilhaCont(int tam) 
{ 
 m = tam; 
 topo = -1; 
 X = new float[m]; 
} 
TPilhaCont::~TPilhaCont() 
{ 
 delete [] X; 
} 
MI do TAD TPilhaCont 
Condição de pilha contígua vazia: 
topo = -1 
Pilhas 
9 
float TPilhaCont::ConsultaTopoPC() 
{ 
 if(topo != -1) 
 return X[topo]; 
 else 
 { 
 cout << “Pilha vazia!” << endl; 
 exit(1); 
 } 
} 
 Operação ConsultaTopoPC: 
MI do TAD TPilhaCont 
Pilhas 
10 
void TPilhaCont::EmpilhaPC(float val); 
{// insere No contendo val no topo da Pilha
 
 if(topo == (m – 1)) 
 { 
 cout << “Vetor Cheio!” << endl; 
 exit(2); 
 } 
 topo = topo + 1; 
 X[topo] = val; 
} 
 Operação EmpilhaPC: 
MI do TAD TPilhaCont 
Pilhas 
11 
void TPilhaCont::DesempilhaPC() 
{ // elimina No do topo da pilha
 
 if(topo == -1) 
 { 
 cout << “Pilha Vazia!” << endl; 
 exit(3); 
 } 
 topo = topo - 1; 
} 
 Operação DesempilhaPC: 
MI do TAD TPilhaCont 
Pilhas 
12 
bool TPilhaCont::VaziaPC() 
{ // verifica se pilha está vazia
 
 if(topo == -1) 
 return(true); 
 else 
 return(false); 
} 
 Operação VaziaPC: 
MI do TAD TPilhaCont 
Representação por encadeamento dos nós 
 Uma pilha com n nós pode ser representada por 
uma lista simplesmente encadeada. 
Esquematicamente: 
Pilhas 
13 
 Assim, é necessário definir dois TAD’s: No e 
TPilhaEncad. 
 Xn Xn – 1 X2 X1 
topo 
Pilhas 
14 
class No 
{ 
 private: 
 float info; // informação real do No 
 No *prox; // ponteiro para o próximo No 
 public: 
 No(); 
 void atribInfo(float val); 
 void atribProx(No *p); 
 float consultaInfo(); 
 No *consultaProx(); 
 ~No(); 
}; 
Representação por encadeamento dos nós 
 TAD No (Definição  No.h): 
Pilhas 
15 
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() {} 
Representação por encadeamento dos nós 
 MI do TAD No (Definição  No.h): 
Pilhas 
16 
class TPilhaEncad 
{ 
 private: 
 No *topo; // ponteiro para o No do topo da pilha 
 public: 
 TPilhaEncad(); 
 float ConsultaTopoPE(); 
 void EmpilhaPE(float val); // insere No no Topo
 
 void DesempilhaPE(); // elimina No do Topo 
 bool VaziaPE(); // verifica se pilha está vazia 
 ~TPilhaEncad(); 
}; 
TAD TPilhaEncad 
 Xn Xn – 1 X2 X1 
topo 
 Construtor: 
Pilhas 
17 
TPilhaEncad::TPilhaEncad() 
{ 
 topo = NULL; 
} 
MI do TAD TPilhaEncad 
Condição de pilha encadeada vazia: 
topo = NULL 
Pilhas 
18 
 Operação ConsultaTopoPE: 
float TPilhaEncad::ConsultaTopoPE() 
{ 
 if(topo != NULL) 
 return topo->consultaInfo(); 
 else 
 { 
 cout << “Pilha vazia!” << endl; 
 exit(1); 
 } 
} 
MI do TAD TPilhaEncad 
Pilhas 
19 
 Operação EmpilhaPE: 
void TPilhaEncad::EmpilhaPE(float val)
 
{ // insere No contendo val no topo da pilha 
 No *p = new No(); // aloca No apontado por p 
 p->atribInfo(val); // preenche info com val 
 p->atribProx(topo); // prox recebe atual topo 
 topo = p; //No apontado por p passa a ser o topo 
} 
MI do TAD TPilhaEncad 
Pilhas 
20 
 Operação DesempilhaPE: 
void TPilhaEncad::DesempilhaPE() 
{ // elimina No do topo da pilha
 
 No *p; 
 if(topo != NULL) // se pilha não está vazia 
 { 
 p = topo; // p aponta para o No a ser excluído 
 topo = p->consultaProx();//topo passa a apontar 
 // para o atual segundo 
 delete p; // exclui o No do topo 
 } 
 else 
 Rotina_Erro(1); 
} 
MI do TAD TPilhaEncad 
Pilhas 
21 
bool TPilhaEncad::VaziaPE() 
{ // verifica se pilha está vazia 
 
 if(topo == NULL) 
 return(true); 
 else 
 return(false); 
} 
 Operação VaziaPE: 
MI do TAD TPilhaEncad 
Pilhas 
22 
 Destrutor: 
TPilhaEncad::~TPilhaEncad() 
{ 
 No *p = topo; 
 while(topo != NULL) 
 { 
 topo = p->consultaProx(); 
 delete p; 
 p = topo; 
 } 
} 
MI do TAD TPilhaEncad 
 Exercício 1: 
 Existem PA’s que utilizam estruturas de dados 
dinâmicas, cujos projetos preveem uma possível 
interrupção no processamento com retomada num 
momento futuro. 
 Uma alternativa para esses programas pode ser a 
transformação da estrutura encadeada em contígua, 
viabilizando o seu armazenamento em memória 
auxiliar e, quando necessário, a recuperação da 
estrutura contígua e posterior transformação 
inversa (em encadeada) para prosseguir com o 
processamento do PA. 
Pilhas 
23 
 Exercício 1: 
 Para auxiliar nesta tarefa, desenvolver um 
procedimento para o PA que transforme uma pilha 
encadeada de valores reais em pilha contígua com 
no máximo 500 nós. 
Pilhas 
24 
void PEncadPCont(PilhaEncad *pe, PilhaCont *pc) 
{ 
 pc = new PilhaCont(500);//cria pilha contígua 
 while(!pe->VaziaPE())//enquanto encadeada não vazia 
 { 
 pc->EmpilhaPC(pe->ConsultaTopoPE()); 
 pe->DesempilhaPE(); 
 } 
 delete pe;//desaloca a pilha encadeada 
}; 
 Exercício 2: 
 Desenvolver um procedimento querealize a 
transformação inversa da anterior, isto é, 
transforme uma pilha contígua com no máximo 500 
nós (reais) em uma pilha encadeada. 
Pilhas 
25 
Representação por contiguidade dos nós 
 Uma fila contígua onde já ocorreram (n + 1) 
entradas e k saídas de nós, teria a seguinte 
representação esquemática: 
Filas 
26 
 Assim, o TAD TFilaCont de elementos reais 
poderia ser: 
 
0 1 . . . k - 1 k k + 1 . . . n - 1 n n + 1 . . . m-1 
 
 X = - - . . . - NOk NOk + 1 . . . NOn - 1 NOn - . . . - 
 
 c f 
 k n 
 
 Sendo c o índice do vetor que contem o nó do 
começo da fila e f o índice do nó que está no fim. 
TAD TFilaCont 
Filas 
27 
class TFilaCont 
{ 
 private: 
 int m; // capacidade máxima de elementos do vetor 
 int c,f;// índices dos Nos que estão no início e 
 // no fim da fila 
 float *X; // vetor que armazena a fila 
 public: 
 TFilaCont(int tam); 
 float ConsultaInicioFC(); // consulta No do início 
 void EntraFC(float val); // insere No no fim
 
 void SaiFC(); // elimina No do início 
 bool VaziaFC(); // verifica se fila está vazia 
 ~TFilaCont(); 
}; 
 
0 1 . . . k - 1 k k + 1 . . . n - 1 n n + 1 . . . m-1 
 
 X = - - . . . - NOk NOk + 1 . . . NOn - 1 NOn - . . . - 
 
 c f 
 k n 
 
 Construtor: 
Filas 
28 
TFilaCont::TFilaCont(int tam) 
{ 
 m = tam; 
 c = 0; 
 f = -1; 
 X = new float[m]; 
} 
MI do TAD TFilaCont 
 As atribuições c = 0 e f = -1, criam uma fila 
contígua. Mas, se ocorrerem n entradas e n 
saídas, a fila ficará vazia e c = n e f = n-1. Assim, a 
condição de fila contígua vazia é c > f. 
Filas 
29 
float TFilaCont::ConsultaInicioFC() 
{ 
 if(c <= f) 
 return X[c]; 
 else 
 { 
 cout << “Fila vazia!” << endl; 
 exit(1); 
 } 
} 
 Operação ConsultaInicioFC: 
MI do TAD TFilaCont 
Filas 
30 
void TFilaCont::EntraFC(float val); 
{// insere No contendo val no fim da Fila
 
 if(f == (m – 1)) 
 { 
 cout <<"Fila no fim do Vetor!" << endl; 
 exit(2); 
 } 
 f = f + 1; 
 X[f] = val; 
} 
 Operação EntraFC: 
MI do TAD TFilaCont 
Filas 
31 
void TFilaCont::SaiFC() 
{ // elimina No do início da fila
 
 if(c > f) 
 { 
 cout << “Fila Vazia!” << endl; 
 exit(3); 
 } 
 c = c + 1; 
} 
 Operação SaiFC: 
MI do TAD TFilaCont 
Filas 
32 
bool TPilhaCont::VaziaPC() 
{ // verifica se fila está vazia 
 
 if(c > f) 
 return(true); 
 else 
 return(false); 
} 
 Operação VaziaFC: 
MI do TAD TFilaCont 
 Destrutor: 
TFilaCont::~TFilaCont() 
{ 
 delete [] X; 
} 
 Obs.: da forma como foram criadas as operações 
EntraFC e SaiFC, se forem executadas m 
entradas e um determinado número de saídas, a 
fila caminha para o final do vetor, ficando com o 
seguinte aspecto: 
Filas 
33 
 Neste caso, não é possível proceder mais 
entradas na fila, embora hajam posições 
desocupadas no início do vetor. 
 
0 1 . . . i - 1 i i + 1 . . . m-1 
 
 NO = - - . . . - NOi NOi + 1 . . . NOm-1 
 
 C F 
 i m-1 
 
Filas 
34 
1. Alterar a operação EntraFC para deslocar todos os 
elementos da fila para o início do vetor, 
permitindo novas entradas . 
2. Alterar a operação SaiFC de forma que, toda vez 
que ocorrer uma saída (C = 0), a fila seja deslocada 
de uma posição, ficando sempre no início do vetor . 
 As soluções mais comuns para este problema são: 
 
0 1 . . . i - 1 i i + 1 . . . m-1 
 
 NO = - - . . . - NOi NOi + 1 . . . NOm-1 
 
 C F 
 i m-1 
 
 Exercícios: 
Filas 
35 
3. Desenvolver cada uma das operações (EntraFC e 
SaiFC), adotando as soluções sugeridas 
anteriormente. 
4. Qual das duas soluções é a mais eficiente? 
5. Após a realização de cada uma das alterações do 
exercício 3, verificar quais das demais operações 
deveriam ser também alteradas, no sentido de 
melhorar o desempenho geral do TAD TFilaCont. 
 As soluções mais comuns para este problema são: 
Filas 
36 
3. Adotar o conceito de fila circular: 
Onde n é o número 
de nós da fila. 
Nom-1 
NOi 
NOi+1 
0 1 
2 
i-2 
i-1 i 
i+1 
m-1 
c 
i 
f 
m-1 
n 
f – c + 1 
 O TAD TFilaContCirc poderia ser: 
Filas 
37 
class TFilaContCirc 
{ 
 private: 
 int m; // capacidade máxima de elementos do vetor 
 int c,f,n; // índices dos Nos do começo e do fim 
 // da fila e o número atual de Nos 
 float *X; // vetor que armazena a fila 
 int Inc(int ind);//incrementa o índice da fila 
 public: 
 TFilaContCirc(int tam); 
 float ConsultaInicioFCC();// consulta No do início 
 void EntraFCC(float val); // insere No no fim
 
 void SaiFCC(); // elimina No do início 
 bool VaziaFCC(); // verifica se fila está vazia 
 ~TFilaContCirc(); 
}; 
Filas 
38 
 Exercício: 
6. Desenvolver o MI do TAD TFilaContCirc anterior. 
Representação por encadeamento dos nós 
 Esquematicamente, seja uma fila encadeada com 
n nós: 
Filas 
39 
 Neste caso, deve-se também definir dois TAD’s: 
No e TFilaEncad. 
c f 
Filas 
40 
class No 
{ 
 private: 
 float info; // informação real do No 
 No *prox; // ponteiro para o próximo No 
 public: 
 No(); 
 void atribInfo(float val); 
 void atribProx(No *p); 
 float consultaInfo(); 
 No *consultaProx(); 
 ~No(); 
}; 
Representação por encadeamento dos nós 
 TAD No (Definição  No.h): 
Filas 
41 
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() {} 
Representação por encadeamento dos nós 
 MI do TAD No (Definição  No.h): 
Filas 
42 
class TFilaEncad 
{ 
 private: 
 No *c, *f; // ponteiros para os Nos extremos 
 public: 
 TFilaEncad(); 
 float ConsultaInicioFE(); 
 void EntraFE(float val); // insere No no fim
 
 void SaiFE(); // elimina No do início da fila 
 bool VaziaFE(); // verifica se fila está vazia 
 ~TFilaEncad(); 
}; 
TAD TFilaEncad 
c f 
 Construtor: 
Filas 
43 
TFilaEncad::TFilaEncad() 
{ 
 c = NULL; 
 f = NULL; 
} 
MI do TAD TFilaEncad 
Condição de fila encadeada vazia: 
c = NULL e/ou f = NULL 
Filas 
44 
 Operação ConsultaInicioFE: 
float TFilaEncad::ConsultaInicioFE() 
{ 
 if(c != NULL) 
 return c->consultaInfo(); 
 else 
 { 
 cout << “Fila vazia!” << endl; 
 exit(1); 
 } 
} 
MI do TAD TFilaEncad 
Filas 
45 
 Operação EntraFE: 
void TFilaEncad::EntraFE(float val);
 
{ // insere No contendo val no fim da fila 
 No *p = new No(); // cria No apontado por p 
 p->atribInfo(val); // preenche info com val 
 p->atribProx(NULL); // prox recebe NULL 
 if(f == NULL) 
 c = p; // inserção do primeiro No 
 else 
 f->atribProx(p);//liga No apontado por p a fila 
 f = p; //No apontado por p passa a ser o último 
} 
MI do TAD TFilaEncad 
Filas 
46 
 Operação SaiFE: 
void TFilaEncad::SaiFE() 
{ // elimina No do início da fila
 
 No *p; 
 if(c != NULL){ // se fila não está vazia 
 p = c; // p aponta para o No a ser excluído 
 c = p->consultaProx();//cpassa a apontar para 
 //o atual segundo No 
 if(c == NULL) 
 f = NULL; // a fila esvaziou 
 delete p;} // exclui o No do início 
 else 
 Rotina_Erro(1); 
} 
MI do TAD TFilaEncad 
Filas 
47 
bool TFilaEncad::VaziaFE() 
{ // verifica se fila está vazia 
 
 if(c == NULL) 
 return(true); 
 else 
 return(false); 
} 
 Operação VaziaFE: 
MI do TAD TFilaEncad 
Filas 
48 
 Destrutor: 
TFilaEncad::~TFilaEncad() 
{ 
 No *p = c; 
 while(c != NULL) 
 { 
 c = p->consultaProx(); 
 delete p; 
 p = c; 
 } 
 f = NULL; 
} 
MI do TAD TFilaEncad 
Aplicações 
1. Desenvolver um procedimento para inverter o 
sentido de uma fila representada por uma lista 
encadeada. 
2. Considerando uma pilha representada por lista 
encadeada onde cada nó possui um valor real, 
desenvolver um procedimento para 
desempilhar os seus nós montando uma lista 
circular (duplamente encadeada). 
Pilhas e Filas 
49 
Aplicações 
3. O gerente de desenvolvimento de aplicações de 
uma empresa observou que diversos 
programas trabalham com filas encadeadas 
que devem ser gravadas em memória auxiliar. 
Para isso é necessário representar a fila 
contiguamente. Desenvolver um procedimento 
para fazer esta transformação sabendo que 
cada nó possui um valor real e que uma fila 
possui no máximo 500 nós. 
Pilhas e Filas 
50 
Aplicações 
4. Desenvolver um procedimento para fazer a 
transformação inversa da anterior. 
5. Desenvolver um procedimento para montar 
duas filas contíguas, sendo que uma deve 
conter somente números inteiros negativos e a 
outra, os demais números. Os números inteiros 
serão fornecidos através de uma pilha 
encadeada em que cada nó possui um número 
inteiro e qualquer. Considerar que a pilha 
possui no máximo 100 nós. 
Pilhas e Filas 
51 
Aplicações 
6. Desenvolver um PA para ler diversos valores X 
inteiros e montar uma fila encadeada, usando o 
TAD TFilaEncad e atendendo as seguintes 
características: 
a) O último valor a ser lido é um FLAG com X = 0. 
b) Na fila só podem entrar nós com X > 0 e maior 
que a informação X do último nó já incluído 
na fila. 
c) Toda vez que for lido um valor X < 0, retirar 
um nó da fila, desde que ela não esteja vazia. 
d) No final, imprimir todos os nós da fila. 
Pilhas e Filas 
52