Introdução
Uma fila é uma coleção de itens, onde o primeiro item adicionado à lista deve ser o primeiro item a ser removido em seguida. Assim, à medida que os itens são adicionados à coleção, ela cresce em tamanho, ou seja, em comprimento. Sempre que algum item deve ser removido, ele deve ser o primeiro a ser adicionado. Se os itens forem removidos continuamente, o próximo item removido é o segundo; o terceiro é removido posteriormente e assim por diante.
Depois que o primeiro item da lista original foi removido, o segundo se torna o primeiro item. Depois que o segundo item for removido, o terceiro se tornará o primeiro item e assim por diante.
Um bom exemplo da vida real de fila é quando as pessoas fazem fila para esperar pelo serviço ou mercadoria. A primeira pessoa é servida antes da última. Porém, a fila de que falamos neste tutorial, é a fila de software, projetada em C ++.
FIFO
FIFO significa Primeiro a Entrar, Primeiro a Sair. É outra forma de valorizar a fila. Isso significa que o primeiro item a entrar na lista, é o primeiro item a ser removido, sempre que ocorrer a remoção. O início da lista é denominado cabeça ou frente; o final da lista é chamado de costas ou cauda.
Operações Essenciais
Uma fila de software deve ter pelo menos as seguintes operações:
Empurre
Esta operação adiciona um novo elemento no final da fila. Esta operação é oficialmente chamada de enfileiramento.
mudança
Esta operação remove o primeiro elemento da fila e o segundo elemento se torna o novo primeiro elemento. Esta operação é oficialmente chamada de dequeue. É chamado de pop em C ++.
Este artigo explica como usar a estrutura de dados da fila C ++. Você deve conhecer os ponteiros e referências de C ++ para entender o restante deste artigo.
Classe e Objetos
Uma classe é um conjunto de variáveis e funções que funcionam juntas, onde as variáveis não têm valores atribuídos. Quando os valores são atribuídos às variáveis, a classe se torna um objeto. Valores diferentes dados à mesma classe resultam em objetos diferentes; ou seja, objetos diferentes são a mesma classe com valores diferentes. A criação de um objeto a partir de uma classe é considerada uma instância do objeto.
O nome, fila, é uma classe. Um objeto criado a partir da classe de fila tem um nome escolhido pelo programador.
Uma função que pertence a uma classe é necessária para instanciar um objeto da classe. Em C ++, essa função tem o mesmo nome que o nome da classe. Os objetos criados (instanciados) a partir da classe têm nomes diferentes dados a eles, pelo programador.
Criar um objeto da classe significa construir o objeto; também significa instanciar.
Um programa C ++ que usa a classe de fila começa com as seguintes linhas na parte superior do arquivo:
#incluir#incluir
usando namespace std;
A primeira linha é para entrada / saída. A segunda linha é para permitir que o programa use todos os recursos da classe de fila. A terceira linha permite que o programa use os nomes no namespace padrão.
Sobrecarregando uma função
Quando duas ou mais assinaturas de função diferentes têm o mesmo nome, diz-se que esse nome está sobrecarregado. Quando uma função é chamada, o número e o tipo de argumentos determinam qual função é realmente executada.
Construção
fila<modelo>nome()A declaração a seguir instancia uma fila chamada, que do tipo int.
fila<int>naquela;A fila está vazia. A declaração começa com a palavra reservada, fila seguida por colchetes angulares com o tipo de dados. Então você tem o nome dado ao programador para a fila.
Construindo com Lista de Inicializadores
A definição a seguir mostra como criar uma fila com lista de inicializadores:
fila<flutuador>naquela({1,1, 2,2, 3,3, 4,4});Destruindo uma fila
Para destruir uma fila, basta deixá-la sair do escopo.
Acesso ao elemento da fila
push (valor)
Uma fila é uma lista do primeiro a entrar, primeiro a sair. Portanto, cada valor é adicionado na parte de trás. O segmento de código a seguir cria uma fila vazia, após a qual cinco valores flutuantes são adicionados na parte de trás:
fila<flutuador>naquela;naquela.Empurre(1,1);
naquela.Empurre(2,2);
naquela.Empurre(3,3);
naquela.Empurre(4,4);
naquela.Empurre(5,5);
size () const
Isso retorna o número de elementos na fila. O código a seguir ilustra:
fila<flutuador>naquela;naquela.Empurre(1,1);naquela.Empurre(2,2);naquela.Empurre(3,3);naquela.Empurre(4,4);naquela.Empurre(5,5);
custo<<naquela.Tamanho() << ' n';
A saída é 5.
frente()
Isso retorna uma referência ao primeiro elemento da fila, sem remover o elemento. A saída do código a seguir é 1.1.
fila<flutuador>naquela;naquela.Empurre(1,1);naquela.Empurre(2,2);naquela.Empurre(3,3);naquela.Empurre(4,4);naquela.Empurre(5,5);
custo<<naquela.frente() << ' n';
O elemento não é removido da fila.
front () const
Quando a construção da fila é precedida por const, a expressão front () const é executada em vez de front (). Ele é usado no código a seguir, por exemplo.
constfila<flutuador>naquela({1,1, 2,2, 3,3, 4,4, 5,5});custo<<naquela.frente() << ' n';
Uma referência constante é retornada. O elemento não é removido do vetor. Os elementos da fila não podem ser alterados.
de volta()
Isso retorna uma referência ao último elemento da fila, sem remover o elemento. A saída do código a seguir é 5.5.
fila<flutuador>naquela;naquela.Empurre(1,1);naquela.Empurre(2,2);naquela.Empurre(3,3);naquela.Empurre(4,4);naquela.Empurre(5,5);
custo<<naquela.de volta() << ' n';
back () const
Quando a construção da fila é precedida por const, a expressão back () const é executada em vez de back (). Ele é usado no código a seguir, por exemplo.
constfila<flutuador>naquela({1,1, 2,2, 3,3, 4,4, 5,5});custo<<naquela.de volta() << ' n';
Uma referência constante é retornada. O elemento não é removido da fila. Com a const anterior para a construção da fila, os elementos na fila não podem ser alterados.
Capacidade da fila
size () const
- Veja acima
empty () const
Isso retorna 1 para verdadeiro se não houver elementos na fila ou 0 para falso se a fila estiver vazia. O código a seguir ilustra isso:
fila<flutuador>aquele1({1,1, 2,2, 3,3, 4,4, 5,5});custo<<that1.vazio() << ' n';
fila<flutuador>that2;
custo<<that2.vazio() << ' n';
O resultado é:
01
Modificadores de fila
pop ()
Uma fila é FIFO, portanto, qualquer elemento que precise ser removido deve ser removido do topo (cabeça) da fila. Esta função de membro remove o primeiro elemento sem retorná-lo. O código a seguir ilustra isso:
fila<flutuador>naquela({1,1, 2,2, 3,3, 4,4, 5,5});custo<<naquela.frente() << ' n';
naquela.pop();
custo<<naquela.Tamanho() << ' n';
O resultado é:
1,14
a.swap (b)
Duas filas podem ser trocadas, conforme ilustrado neste segmento de código:
fila<flutuador>aquele1({1,1, 2,2, 3,3, 4,4, 5,5});fila<flutuador>that2({10, vinte});
that1.troca(that2);
custo<< 'Primeiro elemento e tamanho de que1:
'<<that1.frente() <<','<<that1.Tamanho() << ' n';
custo<< 'Primeiro elemento e tamanho de que2'<<
that2.frente() <<','<<that2.Tamanho() << ' n';
O resultado é:
Primeiro elemento e tamanho de que1: 10, 2
Primeiro elemento e tamanho de que2: 1.1, 5
Observe que o comprimento de uma fila é aumentado, se necessário. Além disso, os valores que não tiveram substituições são substituídos por algum valor padrão. Os tipos de dados devem ser do mesmo tipo.
Operadores relacionais e de igualdade para filas
Para caracteres comuns em C ++, em ordem crescente, os números vêm antes das letras maiúsculas, que vêm antes das letras minúsculas. O caractere de espaço vem antes de zero e todos eles.
Operadores de igualdade
Retorna 1 para verdadeiro e 0 para falso.
O == Operador
Retorna 1 se as duas filas tiverem o mesmo tamanho e os elementos correspondentes forem iguais; caso contrário, retorna 0. Exemplo:
fila<const Caracteres*>aquele1({'Gentil', 'algo mais'});fila<const Caracteres*>that2({'malvado'});
intnum=aquele1==that2;
custo<<num<< ' n';
A saída é: 0.
O! = Operador
- o oposto do anterior. Exemplo:
fila<const Caracteres*>aquele1({'Gentil', 'algo mais'});fila<const Caracteres*>that2({'malvado'});
intnum=aquele1! =that2;
custo<<num<< ' n';
O resultado é: 1.
Operadores relacionais
Retorna 1 para verdadeiro e 0 para falso.
o
Retorna 1 se a primeira fila for o subconjunto inicial da segunda fila, com os elementos das duas partes iguais sendo os mesmos e na mesma ordem. Se ambas as filas forem do mesmo tamanho ou tamanhos diferentes, e movendo-se da esquerda para a direita, um elemento for encontrado na primeira fila que seja menor que o elemento correspondente na segunda fila, então 1 ainda será retornado. Caso contrário, 0 é retornado. Exemplo:
fila<const Caracteres*>aquele1({'Gentil', 'algo mais'});fila<const Caracteres*>that2({'malvado'});
intnum=aquele1<that2;
custo<<num<< ' n';
A saída é 1. O> Operador - o oposto do anterior. Exemplo: Produto: 0 o<= Operator - igual a Produto: 1 O> = Operador - o oposto do anterior. Exemplo: Produto: 0 Um valor está para um tipo de dados, assim como um objeto instanciado está para uma classe. A construção da fila também pode aceitar uma classe como um tipo de dados. O programa a seguir ilustra isso: A saída é 5. A lista de filas é tecnicamente chamada de lista vinculada. Existem dois tipos de listas vinculadas para a fila: lista unicamente vinculada e lista duplamente vinculada. Um elemento de lista vinculada individualmente pode ser implementado por uma estrutura de dois membros. Um membro mantém um ponteiro para o próximo elemento e o outro membro mantém o datum (singular para dados). Um elemento de lista duplamente vinculado pode ser implementado por uma estrutura de três membros. O membro do meio contém o datum, enquanto o primeiro e o terceiro membros contêm ponteiros para seus elementos adjacentes. A fila é uma estrutura de dados primeiro a entrar, primeiro a sair. Existem situações na computação em que os dados chegam na forma de uma fila, exigindo um comportamento de primeiro a entrar, primeiro a sair. Um recurso em um computador é qualquer componente físico ou virtual de disponibilidade limitada. Eles incluem CPU, placa de vídeo, disco rígido e memória. O compartilhamento de tal recurso precisa de uma fila. Os periféricos de computador precisam interromper o computador de vez em quando. As interrupções devem ser tratadas da mesma maneira que chegaram. Isso precisa de uma fila. A fila pode ser usada, por exemplo, para gerenciar arquivos de aplicativo para um trabalho, se os arquivos estiverem armazenados no computador. Uma fila é uma estrutura de dados de lista, que pode ser uma lista unida ou duplamente vinculada. Via de regra, o primeiro elemento que entra na lista é o primeiro elemento a sair. C ++ fornece uma estrutura de dados de fila em sua biblioteca padrão. As categorias de funções de membro e operadores disponíveis para esta estrutura são construção de fila, acesso a elemento de fila, capacidade de fila, modificadores de fila e operadores sobrecarregados de fila. Qualquer estrutura de dados de fila deve fornecer, pelo menos, as funções de membro push () e pop (). push () significa enviar um novo elemento no final da fila; e pop () significa remover o elemento que está na frente da fila. Infelizmente, em C ++, essas funções não retornam o valor enviado ou exibido. Portanto, para saber o último elemento antes de empurrar, a função extra back () deve ser usada; e para saber o primeiro elemento antes de popping, a função extra front () deve ser usada. Um valor está para um tipo de dados, assim como um objeto instanciado está para uma classe. Portanto, uma classe específica pode ser usada como um tipo de dados para a instanciação do modelo de fila. Objetos diferentes para a classe tornam-se valores diferentes para a classe. A fila possui aplicativos no computador. Ele pode ser usado, por exemplo, para gerenciar arquivos de aplicativo para um trabalho, se os arquivos estiverem armazenados no computador. Chrys
fila<const Caracteres*>that2({'malvado'});
intnum=aquele1>that2;
custo<<num<< ' n';
fila<const Caracteres*>that2({'malvado'});
intnum=aquele1<=that2;
custo<<num<< ' n';
fila<const Caracteres*>that2({'malvado'});
intnum=aquele1> =that2;
custo<<num<< ' n'; Classe e seus objetos instanciados
#incluir
usando namespace std;
classe TheCla
{
público:
intnum;
estático CaracteresCH;
vaziofunção(Caracteresnão, const Caracteres *p)
{
custo<< 'Existem ' <<num<< 'livros que valem' <<não<<p<< ' na loja.' << ' n';
}
estático vazioDiversão(CaracteresCH)
{
E se (CH== 'para')
custo<< 'Função de membro estático oficial' << ' n';
}
};
inta Principal()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
fila<TheCla>naquela;
naquela.Empurre(obj1);naquela.Empurre(obj2);naquela.Empurre(obj3);naquela.Empurre(obj4);naquela.Empurre(obj5);
custo<<naquela.Tamanho() << ' n';
Retorna 0;
} Lista Vinculada
Aplicações da Fila
Compartilhando recursos de computador
Manipulação de interrupções
Gerenciar informações.
Conclusão