Princípio de implementação da fila java
A palavra "fila" é o que o britânico chama "fila". "Teto na fila" no Reino Unido significa ficar em uma fileira. Na ciência da computação, uma fila é uma estrutura de dados, que é um pouco como uma pilha, exceto que o primeiro item de dados inserido na fila será removido primeiro e, na pilha, o último item de dados inserido é removido primeiro. A fila funciona como as fileiras de pessoas que estão em frente ao cinema: a primeira pessoa que entra no afiliada chegará à frente da equipe para comprar ingressos. A última pessoa que faz filas pode comprar ingressos.
As filas também são usadas como ferramentas para programadores, como pilhas. Ele também pode ser usado para simular ambientes do mundo real, como simular pessoas esperando em um banco, aviões esperando para decolar ou pacotes na Internet estão esperando para serem transmitidos.
No sistema operacional de computador, várias filas estão funcionando em silêncio. O trabalho de impressão está esperando a impressão na fila de impressão. Ao digitar no teclado, também há uma fila que armazena a digitação. Da mesma forma, se uma chave for tocada usando um processador de texto e o computador precisará fazer outra coisa temporariamente, o conteúdo tocado não será perdido e esperará na fila até que o processador de texto tenha tempo para lê -lo. A fila é usada para garantir que a ordem de digitação não seja alterada quando processada.
Operações básicas de filas
As duas operações básicas de uma fila estão inserindo (inserindo) um item de dados, ou seja, colocando um item de dados na cauda da fila, e o outro está removendo (removendo) um item de dados, ou seja, removendo o item de dados na cabeça da equipe. Isso é semelhante aos amantes de filmes na fila até o final da linha quando eles se enquadram para comprar ingressos, depois chegam à cabeça da linha e depois saem da fila.
A nomeação de métodos para inserir e remover itens de dados na pilha é muito padrão, chamado push e pop. O método da fila não foi nomeado padronizado até agora. "Inserir" pode ser chamado de put, add ou enquistar, enquanto "excluir" pode ser chamado de excluir, obter ou deque. O final do item de dados de inserção também pode ser chamado de volta, cauda ou final. O chefe da equipe que remove o item de dados também pode ser chamado de cabeça. Insira, remova, dianteiro e traseiro serão usados abaixo.
Insira insira o valor na cauda da fila e a cauda da seta da fila é adicionada para apontar para o novo item de dados.
Após a remoção do item de dados, o chefe da equipe é adicionado por um. Geralmente, ao implementar uma fila, o item de dados excluído será salvo na memória, mas não pode ser acessado porque a cabeça da fila foi movida para sua próxima posição.
Ao contrário do caso na pilha, os itens de dados na fila nem sempre começam no subscrito 0 da matriz. Depois de remover alguns itens de dados, o ponteiro do cabeçalho aponta para uma posição de subscrito mais alta.
A operação de exibição retorna o valor do item de dados do cabeçalho, mas não exclui o item de dados da equipe.
Se você deseja remover um item de dados de uma fila vazia ou inserir um item de dados em uma fila completa, o aplicativo solicitará uma mensagem de erro.
Fila de loop
Quando um novo item de dados é inserido na fila, a seta traseira na cabeça da equipe se move para cima em direção à grande posição do subscrito da matriz. Ao remover itens de dados, a cauda da fila do ponteiro frontal também se move para cima. Esse design pode ser contrário à observação direta das pessoas, porque quando as pessoas fazem fila para ingressos para cinema, a fila sempre avança e depois que a pessoa na frente deles compra o bilhete e deixa a fila, os outros avançam. Depois de excluir um item de dados na fila no computador, você também pode levar todos os outros itens de dados, mas isso é muito eficiente. Em vez disso, mantemos todos os itens de dados na posição da mesma através do movimento dos ponteiros da cabeça e da cauda da fila.
O problema com esse design é que o ponteiro da cauda passará rapidamente para o final da matriz. Embora exista uma unidade de item de dados vazio no início da matriz, que é a localização do item de dados removido, mas como o ponteiro da cauda não pode mais se mover para trás, novos itens de dados não podem ser inseridos. O que devo fazer?
Tratamento de embrulho
Para evitar o problema de estar insatisfeita, mas não ser capaz de inserir novos itens de dados, os ponteiros da cabeça e da cauda podem ser embrulhados de volta ao início da matriz. Esta é a fila de loop (às vezes também chamada de "anel de buffer").
O processo de embrulho de ponteiro: insira itens de dados suficientes na fila para fazer com que o ponteiro da cauda aponte para o final tardio da matriz. Exclua mais alguns itens de dados na extremidade frontal da matriz. Agora insira um novo item de dados. Você verá que o ponteiro da cauda será revertido do final para a posição inicial. Novos itens de dados serão inseridos neste local.
Insira mais itens de dados. O ponteiro da cauda se move para cima como esperado. Observe que depois que o ponteiro da cauda está rebocando, agora está abaixo do ponteiro da cabeça, que reverte a posição inicial. Isso pode ser chamado de "sequência quebrada": os itens de dados na fila estão presentes em duas seqüências diferentes na matriz.
Depois de excluir itens de dados suficientes, o chefe da equipe também envolve. Nesse momento, o ponteiro da fila retorna ao estado de posição no tempo de execução inicial, e o ponteiro da cabeça está abaixo do ponteiro da cauda. Os itens de dados também são restaurados para uma única sequência contínua.
Código Java para filas
O programa da fila.java cria uma classe de fila, que tem métodos insert (), remove (), peek (), isEmpty () e size ().
pilha de pacotes e fila;
classe fila {private int maxsize; privado longo [] Quearray; Frente privada int; private int traseiro; private int nitems; fila pública (int s) {maxsize = s; Quearray = novo longo [maxSize]; front = 0; traseiro = -1; nitems = 0; } public void insert (longo j) {if (traseiro == maxSize-1) traseiro = -1; Quearray [++ traseiro] = j; nitems ++; } public Long Remow () {Long Temp = Quearray [FRONT ++]; if (front == maxSize) front = 0; nitems--; retornar temp; } public long peekfront () {return Quayray [FRONT]; } public boolean isEmpty () {return (nitems == 0); } public boolean iffull () {return (nitems == maxSize); } public int size () {return nitems; }}A classe de fila implementada pelo programa não apenas possui campos front (cabeça) e traseira (chefe da equipe), mas também o número de itens de dados atuais na fila: Nitems.
O pré -requisito para a operação do método insert () é que a fila está insatisfeita. Este método não é exibido em main (), mas o método insert () geralmente deve ser chamado primeiro e, em seguida, o método isfull () deve ser chamado após retornar false. (Uma abordagem mais geral é adicionar um julgamento ao método insert () para verificar se a fila está cheia. Se um item de dados for inserido na fila completa, uma exceção será lançada.)
De um modo geral, a operação de inserção é adicionar um traseiro (ponteiro da cauda da equipe) e inserir novos dados na posição apontada pelo ponteiro da cauda. No entanto, quando o ponteiro traseiro aponta para a parte superior da matriz, ou seja, a posição MaxSize-1, ele deve ser enrolado de volta à parte inferior da matriz antes de inserir o item de dados. A operação de enrolamento define a parte traseira para -1; portanto, quando a traseira é adicionada 1, é igual a 0, que é o valor do subscrito na parte inferior da matriz e, finalmente, o Nitem é adicionado.
O pré -requisito para a operação do método Remover () é que a fila não está vazia. Antes de chamar esse método, você deve chamar o método isEmpty () para garantir que a fila não esteja vazia ou adicione esse mecanismo de verificação de erros ao método Remow ().
A operação Remover sempre obtém o valor do item de dados do cabeçalho do ponteiro frontal e adiciona o frontal. No entanto, se você o fizer que o valor da frente exceda a parte superior da matriz, a frente deve voltar à posição em que o subscrito da matriz é 0. Ao fazer esse teste, o valor de retorno é temporariamente armazenado. Finalmente, o Nitem é reduzido por um.
O método Peek () é simples e fácil de entender: retorna o valor do item de dados apontado pelo ponteiro frontal. Algumas implementações de fila também permitem visualizar o valor do item de dados da extremidade da fila; Por exemplo, esses métodos podem ser chamados de Peekfront (), Peekrear () ou apenas front () e traseira ().
Os métodos de implementação dos métodos isEmpty (), isfull () e size () dependem do campo Nitems, que retorna se o NITEMS é igual a 0, seja igual a maximizar ou retornar seu próprio valor.
A inclusão dos campos de contagem de itens de dados na classe de filas adicionará um pouco de operação extra aos métodos insert () e remove (), porque os métodos insert () e remover () devem aumentar e diminuir o valor dessa variável, respectivamente. Isso pode não ser uma sobrecarga extra, mas se você lidar com muita inserção e remover operações, isso poderá afetar o desempenho.
Porque, algumas implementações da fila não usam os campos da contagem de itens de dados, mas use a frente e a traseira para calcular se a fila está vazia ou cheia e o número de itens de dados. Se você fizer isso, as rotinas isEmpty (), iffull () e size () serão bastante complicadas porque, como mencionado anteriormente, a sequência de itens de dados será recolhida em dois segmentos ou um segmento contínuo.
E, surgiu um problema estranho. Quando a fila está cheia, os ponteiros dianteiros e traseiros assumem uma certa posição, mas quando a fila está vazia, a mesma relação de posição também pode aparecer. Portanto, ao mesmo tempo, a fila pode parecer cheia ou vazia. A solução para esse problema é: Torne a capacidade da matriz ser uma a mais que o número máximo de itens de dados da fila.
Obrigado pela leitura, espero que isso possa ajudá -lo. Obrigado pelo seu apoio a este site!