Fila (tipo de dados abstratos) - Queue (abstract data type)

Representação de uma fila FIFO (primeiro a entrar , primeiro a sair)

Na ciência da computação , uma fila é uma coleção de entidades que são mantidas em uma sequência e podem ser modificadas pela adição de entidades em uma extremidade da sequência e a remoção de entidades da outra extremidade da sequência. Por convenção, o final da sequência na qual os elementos são adicionados é chamado de parte traseira, final ou traseira da fila, e o final na qual os elementos são removidos é chamado de início ou início da fila, analogamente às palavras usadas quando as pessoas fazem fila para esperar por bens ou serviços.

A operação de adição de um elemento para a parte traseira da fila é conhecido como enfileiramento , e a operação de remoção de um elemento a partir da frente é conhecido como Desenfileiramento . Outras operações também podem ser permitidas, muitas vezes incluindo uma operação peek ou front que retorna o valor do próximo elemento a ser retirado da fila sem retirá-lo da fila.

As operações de uma fila tornam-na uma estrutura de dados primeiro a entrar, primeiro a sair (FIFO) . Em uma estrutura de dados FIFO, o primeiro elemento adicionado à fila será o primeiro a ser removido. Isso é equivalente ao requisito de que, uma vez que um novo elemento seja adicionado, todos os elementos que foram adicionados antes devem ser removidos antes que o novo elemento possa ser removido. Uma fila é um exemplo de estrutura de dados linear ou, de forma mais abstrata, uma coleção sequencial. As filas são comuns em programas de computador, onde são implementadas como estruturas de dados acopladas a rotinas de acesso, como uma estrutura de dados abstrata ou em linguagens orientadas a objetos como classes. Implementações comuns são buffers circulares e listas vinculadas .

As filas fornecem serviços em ciência da computação , transporte e pesquisa operacional, onde várias entidades, como dados, objetos, pessoas ou eventos, são armazenados e mantidos para processamento posterior. Nesses contextos, a fila desempenha a função de um buffer . Outro uso de filas é na implementação da pesquisa em amplitude .

Implementação de fila

Teoricamente, uma característica de uma fila é que ela não possui uma capacidade específica. Independentemente de quantos elementos já estão contidos, um novo elemento sempre pode ser adicionado. Também pode estar vazio, momento em que a remoção de um elemento será impossível até que um novo elemento seja adicionado novamente.

Matrizes de comprimento fixo têm capacidade limitada, mas não é verdade que os itens precisam ser copiados para o início da fila. O simples truque de transformar a matriz em um círculo fechado e deixar a cabeça e a cauda vagarem indefinidamente nesse círculo torna desnecessário mover itens armazenados na matriz. Se n for o tamanho da matriz, então o cálculo dos índices módulo n transformará a matriz em um círculo. Esta ainda é a maneira conceitualmente mais simples de construir uma fila em uma linguagem de alto nível, mas admite que as coisas ficam um pouco mais lentas, porque os índices da matriz devem ser comparados a zero e o tamanho da matriz, que é comparável ao tempo necessário para verifique se um índice de array está fora dos limites, o que algumas linguagens fazem, mas este certamente será o método de escolha para uma implementação rápida e suja, ou para qualquer linguagem de alto nível que não tenha sintaxe de ponteiro. O tamanho do array deve ser declarado com antecedência, mas algumas implementações simplesmente dobram o tamanho do array declarado quando ocorre estouro. A maioria das linguagens modernas com objetos ou ponteiros pode implementar ou vir com bibliotecas para listas dinâmicas. Essas estruturas de dados podem não ter especificado um limite de capacidade fixo além das restrições de memória. O estouro da fila resulta da tentativa de adicionar um elemento a uma fila cheia e o estouro negativo da fila ocorre ao tentar remover um elemento de uma fila vazia.

Uma fila limitada é uma fila limitada a um número fixo de itens.

Existem várias implementações eficientes de filas FIFO. Uma implementação eficiente é aquela que pode realizar as operações - enfileiramento e retirada da fila - em tempo O (1) .

• Lista ligada
  • Uma lista duplamente vinculada tem inserção e exclusão O (1) em ambas as extremidades, portanto, é uma escolha natural para filas.
  • Uma lista regular unida individualmente tem inserção e exclusão eficientes apenas em uma extremidade. No entanto, uma pequena modificação - manter um ponteiro para o último nó além do primeiro - permitirá que ele implemente uma fila eficiente.
• Um deque implementado usando uma matriz dinâmica modificada

Filas e linguagens de programação

As filas podem ser implementadas como um tipo de dados separado ou podem ser consideradas um caso especial de uma fila dupla (deque) e não implementadas separadamente. Por exemplo, Perl e Ruby permitem o push e popping de uma matriz de ambas as extremidades, então é possível usar as funções push e unshift para enfileirar e retirar da fila uma lista (ou, ao contrário, pode-se usar shift e pop ), embora em alguns casos essas operações não são eficientes.

A Biblioteca de Modelos Padrão do C ++ fornece uma queueclasse " " modelo que é restrita apenas a operações push / pop. Desde J2SE5.0, a biblioteca Java contém uma Queueinterface que especifica operações de fila; classes de implementação incluem LinkedListe (desde J2SE 1.6) ArrayDeque. PHP tem uma classe SplQueue e bibliotecas de terceiros como beanstalk'd e Gearman .

Exemplo

Uma fila simples implementada em JavaScript :

class Queue {
    constructor() {
        this.items = new Array(0);
    }

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        return this.items.shift();
    }
}

Implementação puramente funcional

As filas também podem ser implementadas como uma estrutura de dados puramente funcional . Existem duas implementações. O primeiro só atinge por operação, em média . Ou seja, o tempo amortizado é , mas as operações individuais podem ocorrer, onde n é o número de elementos na fila. A segunda implementação é chamada de fila em tempo real e permite que a fila seja persistente com operações no pior caso O (1). É uma implementação mais complexa e requer listas preguiçosas com memoização . ${\ displaystyle O (1)}$${\ displaystyle O (1)}$${\ displaystyle O (n)}$

Fila amortizada

Os dados dessa fila são armazenados em duas listas unidas individualmente chamadas e . A lista contém a parte da frente da fila. A lista contém os elementos restantes (também conhecidos como a parte traseira da fila) na ordem inversa . É fácil inserir na frente da fila adicionando um nó no início de . E, se não estiver vazio, é fácil remover do final da fila removendo o nó no início de . Quando está vazio, a lista é revertida e atribuída a e, em seguida, o cabeçalho de é removido. ${\ displaystyle f}$${\ displaystyle r}$${\ displaystyle f}$${\ displaystyle r}$${\ displaystyle f}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle f}$${\ displaystyle r}$${\ displaystyle r}$

A inserção ("enfileirar") sempre leva tempo. A remoção ("desenfileirar") ocorre quando a lista não está vazia. Quando está vazio, o reverso leva onde está o número de elementos em . Mas, podemos dizer que é tempo amortizado , pois cada elemento em teve que ser inserido e podemos atribuir um custo constante para cada elemento no reverso de quando foi inserido. ${\ displaystyle O (1)}$${\ displaystyle O (1)}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle O (n)}$${\ displaystyle n}$${\ displaystyle f}$${\ displaystyle O (1)}$ ${\ displaystyle f}$

Fila em tempo real

A fila em tempo real atinge o tempo para todas as operações, sem amortização. Essa discussão será técnica, portanto, lembre-se que, para uma lista, denota seu comprimento, que NIL representa uma lista vazia e representa a lista cuja cabeça é he cuja cauda é t . ${\ displaystyle O (1)}$${\ displaystyle l}$${\ displaystyle | l |}$${\ displaystyle \ operatorname {CONS} (h, t)}$

A estrutura de dados usada para implementar nossas filas consiste em três listas unidas individualmente, onde f é a frente da fila, r é a parte traseira da fila na ordem inversa. O invariante da estrutura é que s é a parte traseira de f sem seus primeiros elementos, isto é . A cauda da fila é então quase e a inserção de um elemento x a é quase . É dito quase, porque em ambos os resultados ,. Uma função auxiliar deve então ser chamada para que o invariante seja satisfeito. Dois casos devem ser considerados, dependendo se é a lista vazia, caso em que , ou não. A definição formal é e onde é f seguido por r invertido. ${\ displaystyle (f, r, s)}$${\ displaystyle | r |}$${\ displaystyle | s | = | f | - | r |}$${\ displaystyle (\ operatorname {CONS} (x, f), r, s)}$${\ displaystyle (f, r, s)}$${\ displaystyle (f, r, s)}$${\ displaystyle (f, \ operatorname {CONS} (x, r), s)}$${\ displaystyle | s | = | f | - | r | +1}$${\ displaystyle aux}$${\ displaystyle s}$${\ displaystyle | r | = | f | +1}$${\ displaystyle \ operatorname {aux} (f, r, \ operatorname {Cons} (\ _, s)) = (f, r, s)}$${\ displaystyle \ operatorname {aux} (f, r, {\ text {NIL}}) = (f ', {\ text {NIL}}, f')}$${\ displaystyle f '}$

Vamos chamar a função que retorna f seguido de r invertido. Além disso, vamos supor que , uma vez que é o caso quando esta função é chamada. Mais precisamente, definimos uma função preguiçosa que recebe como entrada três listas tais que , e retorna a concatenação de f , de r invertido e de a . Então . A definição indutiva de rotação é e . Seu tempo de execução é , mas, como a avaliação lenta é usada, o cálculo é atrasado até que os resultados sejam forçados pelo cálculo. ${\ displaystyle \ operatorname {reverso} (f, r)}$${\ displaystyle | r | = | f | +1}$${\ displaystyle \ operatorname {rotate} (f, r, a)}$${\ displaystyle | r | = | f | +1}$${\ displaystyle \ operatorname {reverso} (f, r) = \ operatorname {girar} (f, r, {\ text {NIL}})}$${\ displaystyle \ operatorname {rotate} ({\ text {NIL}}, \ operatorname {Cons} (y, {\ text {NIL}}), a) = \ operatorname {Cons} (y, a)}$${\ displaystyle \ operatorname {girar} (\ operatorname {CONS} (x, f), \ operatorname {CONS} (y, r), a) = \ operatorname {Cons} (x, \ operatorname {girar} (f, r, \ operatorname {CONS} (y, a)))}$${\ displaystyle O (r)}$

A lista s na estrutura de dados tem duas finalidades. Essa lista serve como um contador para , de fato, se e somente se s for a lista vazia. Este contador nos permite garantir que a parte traseira nunca seja maior do que a lista da frente. Além disso, o uso de s , que é uma cauda de f , força o cálculo de uma parte da lista (preguiçosa) f durante cada cauda e operação de inserção . Portanto, quando , a lista f é totalmente forçada. Se não fosse o caso, a representação interna de f poderia ser algum apêndice de append de ... de append, e forçar não seria mais uma operação de tempo constante. ${\ displaystyle | f | - | r |}$${\ displaystyle | f | = | r |}$${\ displaystyle | f | = | r |}$

Veja também

• Tampão circular
• Fila dupla (desenfileirar)
• Fila de prioridade
• Teoria das filas
• Pilha (tipo de dados abstratos) - o "oposto" de uma fila: LIFO (Last In First Out)

Referências

Referências gerais

•  Este artigo incorpora material de domínio público  do  documento NIST :  Black, Paul E. "Bounded queue" . Dicionário de Algoritmos e Estruturas de Dados .

Leitura adicional

• Donald Knuth . The Art of Computer Programming , Volume 1: Fundamental Algorithms , Third Edition. Addison-Wesley, 1997. ISBN  0-201-89683-4 . Seção 2.2.1: Pilhas, filas e desenfileiramentos, pp. 238–243.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 2001. ISBN  0-262-03293-7 . Seção 10.1: Pilhas e filas, pp. 200–204.
• William Ford, William Topp . Estruturas de dados com C ++ e STL , segunda edição. Prentice Hall, 2002. ISBN  0-13-085850-1 . Capítulo 8: Filas e filas prioritárias, pp. 386–390.
• Adam Drozdek . Estruturas de dados e algoritmos em C ++ , terceira edição. Thomson Course Technology, 2005. ISBN  0-534-49182-0 . Capítulo 4: Pilhas e Filas, pp. 137–169.

links externos

• Referência rápida de STL
• Implementação de VBScript de stack, queue, deque e Red-Black Tree