Ostatnio widzieliśmy strukturę danych stosu i jak zaimplementować własną wersję stosów za pomocą JavaScript. W tym artykule przyjrzymy się innemu typowi struktury danych, który znajduje się w tym samym zasobniku i jest często wymieniany obok stosów. Tym razem porozmawiamy o kolejkach .

Kolejki: koncepcje

W świecie informatyki kolejki są równie ważne jak stosy. Używane są w wielu różnych sytuacjach. Mógłbym twierdzić, że są one koniecznością w każdym dużym i dużym systemie, który wymaga dużo komunikacji, planowania i ustalania priorytetów.

# Co to są kolejki?

Kolejka to liniowa struktura danych, w której elementy są ułożone jeden po drugim. Podobnie jak stosy, mają pewne ograniczenia, jeśli chodzi o sposób wykonywania na nich operacji (wstawiania i usuwania). W kolejkach operacje są wykonywane na dwóch końcach, a nie na jednym końcu, jak w przypadku stosów. Kolejka działa na zasadzie First In First Out (FIFO). Gdybyśmy chcieli zilustrować kolejki przykładem z naszego codziennego życia, moglibyśmy obserwować kolejkę ludzi w sklepie Starbucks czekających na kawę. Kto pierwszy przyjdzie ten zostanie obsłużony i tak dalej...

Tak więc, gdy ktoś przychodzi kupić kawę, idzie na koniec kolejki . Jeśli chodzi o struktury danych, powiedzielibyśmy, że ustawiamy się w kolejce. Innymi słowy, wstawiamy nowy element z tyłu kolejki. Z drugiej strony, jeśli ten z przodu kolejki zostanie obsłużony, zostawi swoje miejsce następnemu i tak dalej. Ponownie, jeśli chodzi o struktury danych, powiedzielibyśmy, że usuwamy element z kolejki lub usuwamy element z początku kolejki.

# Dlaczego miałbyś używać kolejek?

Nie mogę policzyć różnych scenariuszy, w których kolejki są bardziej odpowiednie niż jakikolwiek inny typ struktury danych. Wymienię jednak dwa główne powody, które mogą dać ci wgląd w to, że być może potrzebujesz użyć kolejek w określonej sytuacji.

1. Czekanie…

2. Uczciwy porządek…

Jeśli problem, który rozwiązujesz, wymaga, abyś gwarantował, że pierwszy, który przyjdzie, będzie pierwszym, który zostanie obsłużony, to kolejka na ratunek. Fakt, że kolejki są zgodne z zasadą FIFO, daje pewność uczciwego porządku.

Kolejki: Implementacja w JavaScript

Teraz zaimplementujemy naszą niestandardową wersję kolejek przy użyciu JavaScript. W poprzednim artykule wspomnieliśmy, że stosy można zaimplementować za pomocą tablic lub połączonych list, w zależności od potrzeb. Jednak w przypadku struktury danych kolejki użycie połączonej listy byłoby mądrzejszym podejściem bez względu na to. Czemu?

Mówiąc najprościej, jeśli używamy tablic, na przykład operacja usunięcia z kolejki wymagałaby przesunięcia tablicy za każdym razem, gdy usuwamy element z kolejki. To byłoby czasochłonne. W związku z tym zwiększa złożoność czasową rozwiązania. Co więcej, zakładając, że nie wykonasz żadnego przesunięcia po usunięciu elementu z kolejki, może to spowodować marnowanie pamięci, ponieważ pozostawiasz puste miejsca w tablicy. Ponownie prowadzi to do wzrostu złożoności przestrzennej rozwiązania.

A teraz zróbmy to za pomocą połączonych list…

Jeszcze nie skończyliśmy… Ten fragment kodu wymaga pewnych ulepszeń…

Kolejki: teraz Twoja kolej…

# Zadanie pierwsze

Użyj preferowanego języka programowania, aby dodać nową operację back() w celu wyświetlenia wartości z tyłu kolejki.

# Zadanie drugie

Potrzebujemy operacji, aby wydrukować kolejkę, możesz to dla nas zrobić, proszę? Mimo to użyj preferowanego języka programowania…

Poczekaj chwilę, proszę! Zanim wyruszymy, jeśli chcesz, połączmy się…

• Na YouTubie
• Na Linkedinie
• na Twitterze