Filas
Uma fila é uma lista linear em que as inserções são realizadas num extremo, ficando as
remoções restritas a outro.
A palavra da língua inglesa, significa fila. Por tradição, as duas operações básicas que uma fila
suporta são:
Enqueue: Insere um elemento no final da fila.
Dequeue: Remove um elemento do começo da fila.
Sendo F uma fila e x um elemento qualquer, a operação Enqueue(F,x) aumenta o tamanho da
fila, acrescentando o elemento x no seu final. A operação Dequeue(F) faz a fila diminuir, já que
remove e retorna o elemento posicionado no seu começo.
Operação
Estado da Filha
Resultado
------F:[ ]
------ENQUEUE(F,a)
F:[a]
------ENQUEUE(F,b)
F:[a,b]
------ENQUEUE(F,c)
F:[a,b,c]
------ENQUEUE(F,d)
F:[a,b,c,d]
------DEQUEUE(F)
F:[b,c,d]
a
DEQUEUE(F)
F:[c,d]
b
ENQUEUE (F,e)
F:[c,d,e]
------ENQUEUE (F,f)
F:[c,d,e,f]
------ENQUEUE
F:[d,e,f]
c
(F, DEQUEUE(F))
F:[d,e,f,c]
------DEQUEUE(F)
F:[e,f,c]
d
DEQUEUE(F)
F:[f,c]
e
DEQUEUE(F)
F:[c]
f
→COMANDOS EM C++ PARA IMPLEMENTAÇÃO DE UMA FILA←
Biblioteca padrão <queue>
Implementando uma fila
#include<iostream>
#include<stdlib.h>
#include<queue> // biblioteca padrao c++ para fila
using namespace std;
int main()
{
//alguns metodos:
//
push() insere elementos na fila
//
pop()
remove o primeiro elemento da fila
//
front() retorna o primeiro da fila
//
back() retorna o ultimo elemento da fila
//
size() retorna a quantidade de elementos da fila
//
empty() retorna 1 se fila etiver vazia e 0 caso contrario
system("clear"); //limpa a tela no linux
queue<char> q1; //Cria uma fila chamada q1 para armazenar caracteres
queue<int> q2;
//Cria uma fila chamada q2 para armazenar caracteres
q1.push('a');
//insere elementos na fila q1
q1.push('b');
//insere elementos na fila q1
q1.push('c');
//insere elementos na fila q1
q2.push(1);
//insere elementos na fila q2
q2.push(2);
//insere elementos na fila q2
q2.push(3);
//insere elementos na fila q2
cout << "\no elemento que esta no inicio da fila q1 e " <<q1.front();
cout << "\no elemento que esta no fim da fila q1 e " << q1.back();
cout << "\nexistem " << q1.size() << " elementos em q1\n\n";
cout << "\no elemento que esta no inicio da fila q2 e " <<q2.front();
cout << "\no elemento que esta no fim da fila q2 e " << q2.back();
cout << "\nexistem " << q2.size() << " elementos em q2\n\n";
cout << "\nOs elementos que estavam na fila q1 foram " << "\n";
while(!q1.empty()){
//faca enquanto existir elem na fila q1
cout << q1.front(); //imprime o elem. do inicio da fila q1
q1.pop();
//retira o elemento da fila q1
}
cout << "\n\n\n";
return 0;
}
Deque
Implementando uma fila dupla
#include<deque>
using namespace std;
main(){
deque<int>dq1;
dq1.push_front(1);
dq1.push_front(2);
dq1.push_back(3);
dq1.push_back(4);
dq1.pop_front();//remove o primeiro elemento da deque
dq1.pop_back();//remove o último elemento da deque
}
dq1[3]=0//coloca o nº 0 na posição 3 da deque
dq1[2]= 50//coloca o nº 50 na posição 2 da deque
dq1.at(3);//retorna o elemento que está armazenado na 3ª posição da deque
dq1.size();//retorna a quantidade de elementos da deque
dq1.clear();//remove todos os elementos da deque
Lista
<list>
#include<iostream>
#include<list>
using namespace std;
main() {
list<int>x;
x.push_front(1);//1
x.push_front(2);//21
x.push_back(3);//213
x.push_back(4);//2134
x.sort();//ordena a lista//1234
x.reverse();//inverte a lista//4321
while(!x.empty()){
cout<<x.front();
x.pop_front();
}
}
#include<iostream>
#include<list>
using namespace std;
main() {
list<int>x,y;
x.push_back(1);
x.push_back(2);
x.push_back(3);
x.push_back(4);
y.push_back(0);
x.swap(y);
while(!y.empty()){
cout<<y.front();
y.pop_front();
}
}
Árvores
Uma árvore é uma coleção finita de n>0 nodos. Se n=0,dizemos que a árvore é nula;
caso contrário; uma árvore apresenta as seguintes características:
• Existe um nodo denominado raiz;
• Os demais são particionados em T1,T2,...,Tk estruturas dijuntas de árvores;
• As estruturas T1,T2,...,Tk denominam-se subárvores.
A exigência de que as estruturas T1,T2,...,Tk sejam coleções disjuntas, garantem que um
mesmo nodo não aparecerá em mais de uma subárvore de mesmo tempo;ou seja, nunca teremos
subárvores interligadas.
REPRESENTAÇÃO
DE UMA ÁRVORE
GRÁFICA
A
↓
B
C
↓ 
E
F
↓
G

H
↓
K
D

L
I

J

M
Grau- É o número de subárvores de um nodo.
Ex: O nodo A tem grau 3, o nodo D tem grau 2, o nodo C tem grau 1.
O nodo que não possui subárvores tem grau ∅.
Folha ou terminal- são nodos que não possuem subárvores.
Ex: E,G,I,J,K,L e M
OBS: Os outros nodos são denominados não terminais.
O grau de uma árvore é definida como sendo igual ao máximo dos graus de todos
os seus nodos.
Ex: O grau da árvore da ilustração é 3, pois nenhum nodo tem mais de 3 subárvores.
Filhos- Os filhos do nodo B são E,F e G. H é o pai dos nodos L e M.
Por definição dizemos que a raiz de uma árvore encontra-se no nível 1. Estando um
nodo no nível n, seus filhos estarão no nível n+1.
Altura- de uma árvore é definida como sendo o máximo dos níveis de todos os seus
nodos. Uma árvore nula tem altura ∅. Na ilustração a árvore tem altura a nível igual 4. A
subárvore com raiz D tem altura 2.
ÁRVORES BINÁRIAS
Uma árvore binária é uma árvore que pode ser nula, ou então tem as seguintes
características:
• Existe um nodo especial denominado raiz;
• Os demais nodos são particionados em T1 e T2;
• T1 é denominada subárvore esquerda e T2, subárvore direita da raiz.
Árvore binária é um caso especial de árvore em que nenhum nodo tem grau superior a 2, isso é
nenhum nodo tem mais que dois filhos.
A
A


B
B
Árvore de busca binária
Inserindo e removendo elementos em uma árvore binária
•
Todo elemento armazenado na subárvore esquerda é menor que raiz R(raiz
da árvore);
Todo elemento armazenado na subárvore direita é maior que R;
As subárvores esqueda e direita também são árvores de busca binária.
•
•
Ex:
a)
D

C

A

F

 
B
Ordenada
E
G
b)
D
 
A
F


B   C
E


G
Não ordenada
Remoção de Elementos em uma árvore de busca binária
Vamos admitir inicialmente que o elemento a ser removido encontra-se na raiz da
árvore de busca binária T. Nestas condições, temos três possibilidades:
• A raiz não possui filhos: podemos remover e anular T;
• A raiz possui um único filho: podemos remover o nodo raiz, substituindo-o pelo seu
nodo-filho;
• A raiz possui um único filho: podemos remover o nodo raiz, substituindo-o pelo seu
nodo-filho;
• A raiz possui dois filhos: assume o maior elemento armazenado na subárvore
esquerda de T.
ATENÇÃO:
Não se esqueçam de estudar como inserir e remover
elementos em uma árvore de busca binária.