Arquivo (estrutura de dados)
Na computação , um arquivo também chamado de fila ( cauda do inglês ) é uma estrutura de dados baseada no princípio " primeiro a entrar , primeiro a sair " ou FIFO, referido em inglês pela sigla FIFO ( " primeiro a entrar , primeiro a sair » ): o primeiro os elementos adicionados à fila serão os primeiros a serem removidos.
Descrição
A estrutura funciona como uma fila : os primeiros a chegar são os primeiros a sair ( PEPS , FIFO em inglês para o primeiro a entrar , o primeiro a sair ). Quando o último a entrar é o primeiro a sair (LIFO, LIFO Último a entrar , primeiro a sair em inglês) é uma pilha ( pilha ).
Os algoritmos usados para rastrear estoques devem ser consistentes com o método usado no gerenciamento de estoque .
Uma lista vinculada da qual apenas as operações addQueue e removeHead são usadas constitui uma fila. Se a fila é baseada em uma matriz , a estrutura registra dois índices, um correspondendo ao último a chegar e o outro ao próximo a sair.
As filas são usadas para organizar o processamento sequencial de blocos de dados de várias origens.
A teoria das filas , desenvolvida para o dimensionamento das redes telefônicas, relaciona o número de usuários, o número de canais disponíveis, o tempo médio de ocupação do canal e os tempos de espera a serem esperados.
Limitações do método
No software de computador , a vantagem dessa programação reside em sua relativa simplicidade; porém penaliza os processos com curto tempo de execução: na verdade, se se lança, seguindo um processo que exige muito tempo de computação, uma pequena tarefa (por exemplo, em um servidor que gerencia apenas uma impressora, imprimir uma página), o pequeno tarefa terá que esperar pelo final da tarefa que requer muito mais tempo (impressão de cem páginas) antes de ser executada. Na época das máquinas de processador único, essa era a técnica mais confiável para garantir que as operações fossem realizadas em uma ordem lógica.
Este algoritmo também é utilizado como política de substituição de linha de cache devido à sua simplicidade de implementação e baixo custo. No entanto, neste uso, ele apresenta uma anomalia conhecida como anomalia Belady : aumentar o número de andares na fila pode ter um efeito negativo no desempenho.
Formulários
Esta estrutura é usada por exemplo:
- em geral, para armazenar temporariamente transações que devem aguardar para serem processadas;
- os servidores de impressão, que processam as solicitações na ordem em que chegam e as inserem em uma fila (também chamada de fila ou spool );
- determinados motores multitarefa , em um sistema operacional , que devem alocar tempo de máquina para cada tarefa, sem privilegiar nenhum;
- um algoritmo de travessia de largura usa uma fila para armazenar os nós visitados;
- para criar todos os tipos de buffers (em inglês " buffers " );
- Na gestão de estoque, os algoritmos devem respeitar a gestão de estoque físico para garantir a consistência / avaliação física.
Primitivas
Aqui estão os primitivos comumente usados para manipular filas. Não há padronização para primitivas de manipulação de fila. Seus nomes são, portanto, indicados informalmente.
- "Thread": adiciona um elemento à fila. O termo inglês correspondente é enqueue .
- "Rolar": retorna o próximo elemento da fila e o remove da fila. O termo inglês correspondente é dequeue .
- "A linha está vazia?" ": Retorna" verdadeiro "se a fila estiver vazia," falso "caso contrário.
- “Quantidade de itens na fila”: retorna a quantidade de itens na fila.
Exemplo em C #
Exemplo em C #
using System;
namespace ExempleFile
{
public class File
{
private object[] _File;
private int _PointeurDeTete;
private int _PointeurDeQueue;
private int _Taille;
private int _NbreElements;
#region Constructeur
public File(int Taille)
{
this._Taille = Taille;
this._File = new object[Taille];
this._PointeurDeTete = 0;
this._PointeurDeQueue = 0;
this._NbreElements = 0;
}
#endregion
#region Fonctions
public virtual void Enfiler(object item)
{
lock (this)
{
if (this.EstPleine())
{
throw new Exception("La file est pleine !");
}
else
{
this._File[this._PointeurDeQueue] = item;
this._NbreElements++;
// Pointer sur le prochain elément libre,
// revenir à zéro si on est au bout de la file
this._PointeurDeQueue = this._PointeurDeQueue + 1;
if (this._PointeurDeQueue >= this._File.Length)
{
this._PointeurDeQueue = 0;
}
}
}
}
public virtual object Defiler()
{
lock (this)
{
object item = null;
if (this.EstVide())
{
throw new Exception("La file est vide !");
}
else
{
item = this._File[this._PointeurDeTete];
this._NbreElements--;
// Faire pointer le pointeur de queue sur le prochain élément valide,
// revenir à zéro si on est au bout de la file
this._PointeurDeTete = this._PointeurDeTete + 1;
if (this._PointeurDeTete >= this._File.Length)
{
this._PointeurDeTete = 0;
}
}
return item;
}
}
public virtual bool EstVide()
{
return (this._NbreElements == 0);
}
public virtual bool EstPleine()
{
return (this._NbreElements == this._Taille);
}
public int NbreElements
{
get { return this._NbreElements; }
}
#endregion
}
}
Notas e referências
-
queue é o termo em inglês emprestado do francês, enquanto arquivo designa um arquivo neste idioma .
-
Cf. Alfred Aho , John Hopcroft e Jeffrey Ullman ( trad. J.-M. Moreau), estruturas de dados e algoritmos , Paris, InterÉditions,1995, 450 p. ( ISBN 978-2-7296-0194-2 ) , “Tipos de dados abstratos elementares”, p. 58-62
-
Bachelet 2011 .
-
Michel Fleutry , Dicionário enciclopédico de eletrônica: Inglês-Francês , Paris, A casa do dicionário,1991, 1054 p. ( ISBN 2-85608-043-X ) , p. 699 ; (en) RL Brewster , Tecnologia de telecomunicações , Chichester, Reino Unido, Ellis Horwood,1986, p. 45.
-
Cf. “ Queues ” , em Université P. et M. Curie Paris - Sistemas operacionais de computador
Veja também
Bibliografia
Artigos relacionados
links externos
- Bruno Bachelet , “Queue” , em Estruturas de dados ,2011( leia online )