Co to jest kolejka?
ogony to struktury danych używane do przechowywania i pobierania elementów w określonej kolejności. Jest to liniowa struktura danych, która przypomina stos i przylega do FIFO (pierwsze weszło, pierwsze wyszło) reguła. Można to porównać do listy oczekujących lub kolejki, gdzie pierwsza osoba, która się pojawi, jest obsługiwana jako pierwsza. Istniejące komponenty są usuwane z przodu kolejka , a z tyłu dodawane są nowe elementy.
Implementacja kolejki w Golang
Wdrożenie kolejka w Go jest prosty i wydajny i można go zaimplementować przy użyciu następujących czterech metod.
1: Plasterki
W Go, A plasterek to dynamiczna tablica, której rozmiar może się zmieniać. Aby wdrożyć kolejka używać plasterek , możemy dodać elementy z tyłu plasterek korzystając z wbudowanej funkcji dołączania i usuwaj elementy z przodu pliku plasterek za pomocą krojenia.
To podejście jest łatwe do zbudowania i zapewnia dobrą wydajność operacji dodawania i krojenia dzięki wbudowanym plasterkom Go. Jednak metoda krojenia, która obejmuje kopiowanie elementów do nowej tablicy źródłowej, może stać się nieefektywna, jeśli kolejka rozszerza się i wymaga powtarzania operacji usuwania z kolejki.
Poniższy kod definiuje kolejka implementacja za pomocą plasterka w Go.
Pakiet główny
import 'fmt'
funkcja główna ( ) {
kolejka := robić ( [ ] interfejs { } , 0 )
kolejka = dodać ( kolejka , 'język angielski' )
kolejka = dodać ( kolejka , „urdu” )
kolejka = dodać ( kolejka , 'matematyka' )
Jeśli tylko ( kolejka ) > 0 {
przedmiot := kolejka [ 0 ]
kolejka = kolejka [ 1 : ]
fmt. Drukuj ln ( przedmiot )
}
Jeśli tylko ( kolejka ) == 0 {
fmt. Drukuj ln ( „Kolejka jest pusta” )
} w przeciwnym razie {
fmt. Drukuj ln ( kolejka )
}
}
Powyższy kod Go używa wycinka do skonstruowania prostego kolejka struktura danych. The dodać() funkcja służy do kolejkowania elementów w kolejka plasterek, a operacja plasterka, która usuwa element początkowy, służy do usunięcia ich z kolejki. Z fmt.Println() , wypisywany jest element z kolejki. Następnie kod używa tylko() funkcja do ustalenia, czy kolejka jest pusta, a jeśli tak, zapisuje „ Kolejka jest pusty” za pomocą funkcji fmt.Println().
Wyjście
2: Połączone listy
Węzły, które przenoszą wartość i wskaźnik do następnego węzła na liście, tworzą listę połączoną. Mając dwa wskaźniki, jeden wskazujący przód (głowę) listy, a drugi tył (ogień), możemy zaimplementować kolejka za pomocą połączonej listy. Usunięcie elementu z kolejki (dequeuing) polega na usunięciu węzła z przodu listy, podczas gdy dodanie elementu do kolejki (enqueuing) polega na dodaniu nowego węzła na końcu listy.
Ta metoda pozwala na wydajne operacje kolejkowania i usuwania z kolejki, ponieważ należy zmienić tylko wskaźniki głowy i ogona, w przeciwieństwie do rozwiązania opartego na plasterkach, w którym elementy musiałyby zostać skopiowane.
Użyj połączonej listy, aby zaimplementować a kolejka korzystając z podanego poniżej kodu:
Pakiet głównyimport 'fmt'
wpisz węzeł struktura {
interfejs wartości { }
Następny * Węzeł
}
wpisz Kolejka struktura {
głowa * Węzeł
ogon * Węzeł
}
funkcja główna ( ) {
kolejka := & Kolejka { głowa : zero , ogon : zero }
nowyWęzeł := & Węzeł { wartość : 'język angielski' , Następny : zero }
kolejka. ogon = nowyWęzeł
kolejka. głowa = nowyWęzeł
nowyWęzeł = & Węzeł { wartość : „urdu” , Następny : zero }
kolejka. ogon . Następny = nowyWęzeł
kolejka. ogon = nowyWęzeł
nowyWęzeł = & Węzeł { wartość : 'matematyka' , Następny : zero }
kolejka. ogon . Następny = nowyWęzeł
kolejka. ogon = nowyWęzeł
Jeśli kolejka. głowa != zero {
przedmiot := kolejka. głowa . wartość
kolejka. głowa = kolejka. głowa . Następny
fmt. Drukuj ln ( przedmiot )
}
Jeśli kolejka. głowa == zero {
fmt. Drukuj ln ( „Kolejka jest pusta” )
}
}
Struktura Node reprezentuje każdy element w kolejce i zawiera dwa pola: pole wartości do przechowywania wartości elementu oraz pole next do wskazywania następnego elementu w kolejce. Struktura Queue używa właściwości head i tail do śledzenia odpowiednio przodu i tyłu kolejki. The ogon pierwszy element jest wskazywany przez właściwość head, a ostatni przez właściwość tail.
Parametry głowy i ogona są początkowo ustawione na zero kiedy nowy kolejka jest ustanowiony w funkcji main(). Wskaźniki głowy i ogona są aktualizowane, aby dodać trzy węzły do pliku kolejka z wartościami „angielski”, „urdu”, I 'matematyka'. The 'język angielski' pozycja jest wtedy „z kolejki” (usunięto) z przodu kolejka wyświetlając jego wartość i przesuwając wskaźnik głowy do następnego węzła w pliku kolejka . Po usunięciu z kolejki, jeśli nagłówek stanie się pusty, oznacza to, że kolejka jest pusta, a komunikat „ Kolejka jest pusty” jest drukowane.
Wyjście
3: Struktury
W Go możesz utworzyć niestandardową strukturę danych o nazwie a struktura reprezentować A kolejka . Ten struktura może mieć pola do przechowywania kolejka elementów i metod dodawania i usuwania elementów, sprawdzania, czy kolejka jest pusta i uzyskiwania aktualnego rozmiaru kolejki.
Ten sposób tworzenia a kolejka in Go oferuje wygodną i zamkniętą implementację z łatwymi w użyciu metodami, które można rozszerzyć i dostosować za pomocą większej liczby funkcji. Jest to elastyczne podejście, które pozwala na wprowadzanie zmian we wdrożeniu lub dodawanie nowych możliwości w razie potrzeby.
Tworzenie zwyczaju struktura z metodami wymaga napisania dodatkowego kodu w porównaniu z pozostałymi dwoma sposobami, co może zwiększyć złożoność. Zapewnia jednak również większą elastyczność i kontrolę nad wdrażaniem kolejka .
Poniższy przykład pokazuje tworzenie struktury danych do reprezentowania kolejka w Go.
Pakiet głównyimport 'fmt'
wpisz Kolejka struktura {
rzeczy [ ] interfejs { }
}
funkcja ( Q * Kolejka ) Ustaw w kolejce ( interfejs pozycji { } ) {
Q. rzeczy = dodać ( Q. rzeczy , przedmiot )
}
funkcja ( Q * Kolejka ) Usuń z kolejki ( ) interfejs { } {
Jeśli tylko ( Q. rzeczy ) == 0 {
powrót zero
}
przedmiot := Q. rzeczy [ 0 ]
Q. rzeczy = Q. rzeczy [ 1 : ]
powrót przedmiot
}
funkcja ( Q * Kolejka ) Jest pusty ( ) bool {
powrót tylko ( Q. rzeczy ) == 0
}
funkcja ( Q * Kolejka ) Rozmiar ( ) int {
powrót tylko ( Q. rzeczy )
}
funkcja główna ( ) {
kolejka := & Kolejka { rzeczy : robić ( [ ] interfejs { } , 0 ) }
kolejka. Ustaw w kolejce ( 'język angielski' )
kolejka. Ustaw w kolejce ( „urdu” )
kolejka. Ustaw w kolejce ( 'matematyka' )
przedmiot := kolejka. Usuń z kolejki ( )
fmt. Drukuj ln ( przedmiot )
Jeśli kolejka. Jest pusty ( ) {
fmt. Drukuj ln ( „Kolejka jest pusta” )
}
rozmiar := kolejka. Rozmiar ( )
fmt. Drukuj ln ( „Wielkość kolejki:” , rozmiar )
}
W powyższym kodzie element jest dołączany do wycinka elementu za pomocą Kolejkuj() metoda, która przenosi go na koniec kolejka . Śledząc Pierwsze weszło, pierwsze wyszło (FIFO) zasada, tzw Usuń z kolejki () Metoda pobiera element z przodu kolejka i zwraca go. Długość wycinka elementu jest sprawdzana jako część Jest pusty() Metoda sprawdza, czy kolejka jest pusty. Zwracając długość wycinka elementów, plik Rozmiar() metoda zwraca prąd ogon rozmiar.
Funkcja main() używa metody Struktura kolejki stworzyć nowy kolejka , dodawać do niego elementy, usuwać z niego elementy, określać, czy kolejka jest pusty i oblicz jego rozmiar.
Wyjście
4: Kanały
W Go wbudowany typ kanału może być użyty do zaimplementowania kolejka struktura danych. Kanał można utworzyć z rozmiarem bufora, aby ograniczyć liczbę elementów, które można umieścić w kolejce w danym momencie. Aby dodać element do kolejka , można go wysłać do kanału za pomocą <- operatora, natomiast aby usunąć element z kolejki, można go odebrać z kanału przy użyciu tego samego operatora.
Takie podejście może być bardzo przydatne w sytuacjach, w których równoczesny dostęp do kolejka jest wymagane, ponieważ kanały są z natury bezpieczne do jednoczesnego użytku.
Należy pamiętać, że kanały Go są typowane. Oznacza to, że kanałem można wysyłać tylko wartości określonego typu i odbierać z kanału tylko wartości tego samego typu.
To jest ilustracja tego, jak używać kanału do konstruowania kolejka struktura danych w Go.
Pakiet głównyimport (
'fmt'
'czas'
)
wpisz Kolejka struktura {
interfejs kanału elementów { }
}
funcNewQueue ( ) * Kolejka {
Q := & Kolejka {
rzeczy : robić ( interfejs Chana { } ) ,
}
idź q. elementy procesu ( )
powrót Q
}
funkcja ( Q * Kolejka ) elementy procesu ( ) {
Do przedmiot := zakres q. rzeczy {
Jeśli przedmiot == 'język angielski' {
fmt. Drukuj ln ( „Wycofany z kolejki:” , przedmiot )
}
}
}
funkcja ( Q * Kolejka ) Ustaw w kolejce ( interfejs pozycji { } ) {
Q. rzeczy <- przedmiot
}
funcmain ( ) {
kolejka := Nowa kolejka ( )
kolejka. Ustaw w kolejce ( 'język angielski' )
kolejka. Ustaw w kolejce ( „urdu” )
kolejka. Ustaw w kolejce ( 'matematyka' )
czas . Spać ( 2 * czas . Drugi )
}
Powyższy kod tworzy plik Struktura kolejki z jednym polem rzeczy który jest kanałem interfejs{} typ. The Nowa kolejka() funkcja tworzy nową instancję Kolejka i inicjalizuje jego 'rzeczy' pole z nowym niebuforowanym kanałem. Uruchamia również nową goroutine w celu przetworzenia elementów dodanych do kolejki za pomocą elementy procesu() funkcjonować. The elementy procesu() funkcja sprawdza, czy otrzymana pozycja jest równa 'język angielski' i drukuje komunikat do konsoli tylko dla tego elementu. The Kolejkuj() służy do dodawania nowych pozycji do kolejki.
Wyjście
Wniosek
Kolejka to podstawowa struktura danych w Go, używana do przechowywania i pobierania elementów w określonej kolejności. Wdrożenie kolejka w Go jest bezpieczny dla wątków, co czyni je idealnym wyborem do implementacji współbieżności w programach. Można go zaimplementować za pomocą plasterków, połączonych list, struktur i kanałów. Pełne szczegóły są już podane w wyżej podanych wytycznych.