O que é uma Fila?
Caudas são estruturas de dados usadas para armazenar e recuperar elementos em uma ordem predeterminada. É uma estrutura de dados linear que se assemelha a uma pilha e adere ao FIFO (primeiro a entrar, primeiro a sair) regra. Pode ser comparada a uma lista de espera ou a uma fila onde o primeiro a chegar é atendido primeiro. Os componentes existentes são descartados da frente do fila , e novos elementos são adicionados na parte de trás.
Implementação de uma fila em Golang
A implementação de um fila em Go é simples e eficiente e pode ser implementado usando os quatro métodos a seguir.
1: Fatias
Em Go, um fatiar é uma matriz dinâmica que pode mudar de tamanho. Para implementar um fila usando um fatiar , podemos adicionar elementos na parte de trás do fatiar usando a função append integrada e remova elementos da frente do fatiar usando fatiamento.
Essa abordagem é fácil de construir e oferece bom desempenho para anexar e fatiar operações graças às fatias integradas do Go. No entanto, o método de divisão, que inclui a cópia de elementos para uma nova matriz subjacente, pode se tornar ineficiente se o fila expande e requer repetidas operações de desenfileiramento.
O código a seguir define o fila implementação usando uma fatia em Go.
pacote principal
importar 'fmt'
função principal ( ) {
fila := fazer ( [ ] interface { } , 0 )
fila = acrescentar ( fila , 'inglês' )
fila = acrescentar ( fila , 'urdu' )
fila = acrescentar ( fila , 'Matemáticas' )
se apenas ( fila ) > 0 {
item := fila [ 0 ]
fila = fila [ 1 : ]
fmt. Println ( item )
}
se apenas ( fila ) == 0 {
fmt. Println ( 'A fila está vazia' )
} outro {
fmt. Println ( fila )
}
}
O código Go acima usa uma fatia para construir um fila estrutura de dados. O acrescentar() função é usada para enfileirar elementos no fila fatia, e uma operação de fatia que remove o elemento inicial é usada para retirá-los da fila. Com fmt.Println() , o elemento desenfileirado é impresso. O código então usa o apenas() função para determinar se a fila está vazia e, se estiver, escreve “ Fila está vazio” usando a função fmt.Println().
Saída
2: Listas Ligadas
Os nós que carregam um valor e um ponteiro para o próximo nó na lista formam uma lista encadeada. Com dois ponteiros, um apontando para a frente (cabeça) da lista e outro apontando para trás (cauda), podemos implementar um fila usando uma lista encadeada. A remoção de um item da fila (desenfileiramento) envolve a remoção do nó no início da lista, enquanto a adição de um item à fila (enfileiramento) envolve a adição de um novo nó no final da lista.
Esse método permite operações de enfileiramento e desenfileiramento eficientes porque apenas os ponteiros de início e fim precisam ser alterados, em oposição à solução baseada em fatias, em que os elementos precisariam ser copiados.
Use uma lista encadeada para implementar um fila usando o código fornecido abaixo:
pacote principalimportar 'fmt'
tipo nó estrutura {
interface de valor { }
próximo * Nó
}
digite Fila estrutura {
cabeça * Nó
cauda * Nó
}
função principal ( ) {
fila := & Fila { cabeça : nada , cauda : nada }
newNode := & Nó { valor : 'inglês' , próximo : nada }
fila. cauda = newNode
fila. cabeça = newNode
newNode = & Nó { valor : 'urdu' , próximo : nada }
fila. cauda . próximo = newNode
fila. cauda = newNode
newNode = & Nó { valor : 'Matemáticas' , próximo : nada }
fila. cauda . próximo = newNode
fila. cauda = newNode
se fila. cabeça != nada {
item := fila. cabeça . valor
fila. cabeça = fila. cabeça . próximo
fmt. Println ( item )
}
se fila. cabeça == nada {
fmt. Println ( 'A fila está vazia' )
}
}
A estrutura Node representa cada item na fila e contém dois campos: um campo de valor para armazenar o valor do item e o próximo campo para apontar para o próximo item na fila. A estrutura Queue usa as propriedades head e tail para acompanhar o início e o fim da fila, respectivamente. O da cauda primeiro item é indicado pela propriedade head, enquanto seu último item é indicado pela propriedade tail.
Os parâmetros head e tail são inicialmente definidos para nada quando um novo fila é estabelecido na função main(). Os ponteiros de cabeça e cauda são atualizados para adicionar três nós ao fila com os valores “inglês”, “urdu”, e 'Matemáticas'. O 'inglês' item é então “desenfileirado” (removido) da frente do fila exibindo seu valor e avançando o ponteiro da cabeça para o nó seguinte no fila . Após o desenfileiramento, se a cabeça ficar nula, significa que a fila está vazia e a mensagem “ Fila está vazio” é impresso.
Saída
3: Estruturas
Em Go, você pode criar uma estrutura de dados personalizada chamada estrutura para representar um fila . Esse estrutura pode ter campos para armazenar o fila elementos e métodos para adicionar e remover itens, verificar se a fila está vazia e obter o tamanho atual da fila.
Esta forma de criar um fila in Go oferece uma implementação conveniente e encapsulada com métodos fáceis de usar que podem ser expandidos e personalizados com mais recursos. É uma abordagem flexível que permite alterações na implementação ou adicionar novos recursos sempre que necessário.
Criando um costume estrutura com métodos envolve escrever código adicional em comparação com as outras duas formas, o que pode aumentar a complexidade. No entanto, também fornece mais flexibilidade e controle sobre a implementação do fila .
O exemplo a seguir mostra a criação de uma estrutura de dados para representar um fila em Ir.
pacote principalimportar 'fmt'
digite Fila estrutura {
Unid [ ] interface { }
}
função ( q * Fila ) Enfileirar ( interface do item { } ) {
q. Unid = acrescentar ( q. Unid , item )
}
função ( q * Fila ) Defilar ( ) interface { } {
se apenas ( q. Unid ) == 0 {
retornar nada
}
item := q. Unid [ 0 ]
q. Unid = q. Unid [ 1 : ]
retornar item
}
função ( q * Fila ) Está vazia ( ) bool {
retornar apenas ( q. Unid ) == 0
}
função ( q * Fila ) Tamanho ( ) int {
retornar apenas ( q. Unid )
}
função principal ( ) {
fila := & Fila { Unid : fazer ( [ ] interface { } , 0 ) }
fila. Enfileirar ( 'inglês' )
fila. Enfileirar ( 'urdu' )
fila. Enfileirar ( 'Matemáticas' )
item := fila. Defilar ( )
fmt. Println ( item )
se fila. Está vazia ( ) {
fmt. Println ( 'A fila está vazia' )
}
tamanho := fila. Tamanho ( )
fmt. Println ( 'Tamanho da fila:' , tamanho )
}
No código acima, um item é anexado à fatia do item por meio do Enfileirar() método, que o move para o final do fila . Seguindo o Primeiro a entrar, primeiro a sair (FIFO) princípio, o Defilar() método tira um item da frente do fila e o devolve. O comprimento da fatia do item é verificado como parte do Está vazia() verificação do método para ver se o fila está vazia. Ao retornar o comprimento da fatia de itens, o Tamanho() método retorna o atual da cauda tamanho.
A função main() usa o Estrutura da fila para criar um novo fila , adicione elementos a ele, remova itens dele, determine se o fila está vazio e calcule seu tamanho.
Saída
4: Canais
Em Go, o tipo de canal embutido pode ser usado para implementar um fila estrutura de dados. O canal pode ser criado com um tamanho de buffer para limitar o número de elementos que podem ser enfileirados a qualquer momento. Para adicionar um elemento ao fila , ele pode ser enviado para o canal usando o <- operador, enquanto para remover um elemento da fila, ele pode ser recebido do canal usando o mesmo operador.
Essa abordagem pode ser bastante útil em situações em que o acesso simultâneo ao fila é necessário, pois os canais são inerentemente seguros para uso simultâneo.
É crucial lembrar que os canais Go são digitados. Isso significa que você só pode enviar valores de um tipo específico por meio de um canal e só pode receber valores desse mesmo tipo do canal.
Esta é uma ilustração de como usar um canal para construir um fila estrutura de dados em Go.
pacote principalimportar (
'fmt'
'tempo'
)
digite Fila estrutura {
itens chaninterface { }
}
funçãoNovaFila ( ) * Fila {
q := & Fila {
Unid : fazer ( interface chan { } ) ,
}
vai q. processItems ( )
retornar q
}
função ( q * Fila ) processItems ( ) {
para item := intervalo q. Unid {
se item == 'inglês' {
fmt. Println ( 'Fora da fila:' , item )
}
}
}
função ( q * Fila ) Enfileirar ( interface do item { } ) {
q. Unid <- item
}
funcmain ( ) {
fila := NovaFila ( )
fila. Enfileirar ( 'inglês' )
fila. Enfileirar ( 'urdu' )
fila. Enfileirar ( 'Matemáticas' )
tempo . Dormir ( 2 * tempo . Segundo )
}
O código acima cria um Estrutura da fila com um único campo Unid que é um canal de interface{} tipo. O NovaFila() função cria uma nova instância do Fila e inicializa seu 'Unid' campo com um novo canal sem buffer. Ele também inicia uma nova goroutine para processar os itens adicionados à fila usando o processItems() função. O processItems() função verifica se o item recebido é igual a 'inglês' e imprime uma mensagem no console apenas para esse item. O Enfileirar() A função é usada para adicionar novos itens à fila.
Saída
Conclusão
A fila é uma estrutura de dados essencial em Go usada para armazenar e recuperar elementos em uma ordem específica. A implementação de um fila em Go é thread-safe, tornando-os uma escolha ideal para implementar simultaneidade em programas. Ele pode ser implementado usando fatias, listas encadeadas, estruturas e canais. Os detalhes completos já são fornecidos nas diretrizes fornecidas acima.