Diferente das pilhas, que funcionam como um "tubo", onde o último elemento é adicionado e somado até encher o tubo, as filas, os primeiros elementos saem à medida que entram novos, na verdade, as filas funcionam como "túneis".
Em resumo, nas pilhas o último elemento é o primeiro a sair e vice-versa, nas filas o primeiro que entra é o primeiro que sai.
Alguns dos exemplos em que uma fila pode ser usada é em controle de documentos (para impressão, por exemplo), troca de mensagem entre dispositivos numa rede, etc.
Para trabalharmos com filas, devemos adicionar a biblioteca queue.
Os elementos básicos das filas são os mesmos das pilhas, empty, size, push e pop, mas não existe o top, no lugar existe o front e back.
| Método | Funcionalidade |
|---|---|
| push() | Adiciona um elemento à fila |
| pop() | Remove um elemento da fila |
| size() | Exibe o tamanho da fila |
| front() | Exibe o primeiro elemento da fila |
| back() | Exibe o último elemento da fila |
| empty() | Verifica se a fila está vazia |
De forma parecida, criamos as filas assim:
#include <iostream>
#include <queue> // Importe para trabalharmos com filas
using namespace std;
int main() {
queue<string> cartas;
cartas.push("Rei de Copas"); // Isso é uma chamada de objeto, que adiciona elementos.
cartas.push("Rei de Espadas");
cartas.push("Rei de Ouros");
cartas.push("Rei de Paus");
cout << "Tamanho da fila: " << cartas.size() << endl; // Isso exibe os dados da fila
while(!cartas.empty()) {
cartas.pop();
}
return 0;
}
No caso de filas, não existe o top(), no lugar existe os métodos front() (retorna o primeiro elemento da fila), e back() (retorna o último elemento).
Como podemos ver abaixo, o método pop() retira o primeiro elemento, no caso das filas:
while(!cartas.empty()) {
cout << "Primeira carta: " << cartas.front() << endl;
cout << "Última carta: " << cartas.back() << endl << endl;
cartas.pop();
}
Para trabalharmos com listas, devemos incluir a biblioteca list.
De forma parecida com pilhas e filas, nós criamos as listas, só que com tamanho definido, veja abaixo:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> aula(50);
return 0;
}
Podemos passar mais de um parâmetro nas listas, nesse caso, ela terá 5 posições com valores de 50:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> aula(5, 50);
return 0;
}
PS: Podemos também criar mais de uma lista na mesma linha, separados por vírgulas, desde que sejam do mesmo tipo.
Os elementos básicos usados nas listas são os mesmos das filas, empty, size, front e back, e as variações de push e pop (push_front, push_back, pop_front e pop_back), alguns são usados em conjunto.
Veja um exemplo de uso abaixo:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> aula;
int tam;
tam = 10;
for(int i = 0; i < tam; i++) {
aula.push_front(i);
}
cout << "Tamanho da lista: " << aula.size() << endl;
tam = aula.size();
for(int i = 0; i < tam; i++) {
cout << aula.front() << endl;
aula.pop_front();
}
return 0;
}
PS: Se mudar o front pelo back, ele imprimirá ao contrário, veja abaixo:
for(int i = 0; i < tam; i++) {
cout << aula.back() << endl;
aula.pop_back();
}
O mais interessante é que não é só no fim e no começo que podemos inserir valores nas listas, podemos inserir em qualquer posição. É um pouco mais trabalhoso, mas é possível. Para isso, utilizamos o operador iterator, dessa forma, abaixo da declaração da lista:
list<int> aula;
list<int>::iterator it;
E nas posições, fazemos assim:
it = aula.begin();
advance(it, 5); // Substituir pelo número da posição desejada (a partir do zero).
aula.insert(it, 0); // Aqui insere o valor desejado.
Código completo abaixo:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> aula;
list<int>::iterator it;
int tam;
tam = 10;
for(int i = 0; i < tam; i++) {
aula.push_front(i);
}
it = aula.begin();
advance(it, 5); // Substituir pelo número da posição desejada (a partir do zero).
aula.insert(it, 0); // Aqui insere o valor desejado.
cout << "Tamanho da lista: " << aula.size() << endl;
tam = aula.size();
for(int i = 0; i < tam; i++) {
cout << aula.front() << endl;
aula.pop_front();
}
return 0;
}
Para ordenar as posições, usamos o método sort, assim:
aula.sort();
E para inverter a ordem, usamos o reverse:
aula.reverse();
Continuando a aula anterior, deixe o código dessa forma aqui:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> aula;
list<int>::iterator it;
int tam;
tam = 10;
for(int i = 0; i < tam; i++) {
aula.push_front(i);
}
cout << "Tamanho da lista: " << aula.size() << endl;
tam = aula.size();
for(int i = 0; i < tam; i++) {
cout << aula.front() << endl;
aula.pop_front();
}
cout << "Tamanho da lista: " << aula.size() << endl;
return 0;
}
Embaixo do primeiro for, colocamos isso pra adicionar elementos:
it = aula.begin();
advance(it, 3); // Define a posição
aula.insert(it, 0); // Define o valor
Para tirar esse mesmo elemento, usamos o erase com a posição decrementada, dessa forma:
it = aula.begin();
advance(it, 3);
aula.insert(it, 0);
aula.erase(--it);
Para definir a posição a ser removida, é só mudar o número do advance.
Para limpar e remover tudo na lista, usamos o clear, assim:
aula.clear();
Agora criaremos uma segunda lista, sem excluir a primeira, assim:
list<int> teste;
teste.push_front(9);
teste.push_front(9);
teste.push_front(9);
teste.push_front(9);
Agora uniremos as duas listas com o método merge, assim:
aula.merge(teste);
PS: Ao fazer isso, a segunda lista é esvaziada, passando todos os dados pra primeira.