Stack,QueueNr #1 Jednym z absurdów szukania pracy jako programista są pytania, które nie są związane z tym, co będziesz robił. Jednym z tych zagadnień są struktury danych? Czy ta wiedza będzie Ci potrzebna przy tworzeniu strony internetowej?
Raczej nie . Mimo to widząc e-maile od swoich fanów widzę, że ten trend w rozmowach kwalifikacyjnych szybko nie zginie. Po studiach informatycznych być może miałeś przedmiot "Algorytmy struktury danych". Ja miałem i musiałem pisać te struktury w Pascalu na zaliczenie.
Jak się jednak to ma JavaScript i tworzenie stron internetowych? No cóż, możemy narzekać cały dzień. Postanowiłem zrobić o tym wpis i kto wie może początkującemu programiście, który szuka pracy się to przyda.
Co omówimy w tej serii wpisów :
- Stos
- Kolejki
- Lista jednokierunkowa
- Grafy
- Drzewa
Co jest strukturą danych
Struktur dany jest to organizacja informacji w taki sposób, aby można było ją modyfikować czy odczytywać w odpowiednie sposób.
Wiele struktur danych, które będą potrzebne na rozmowie kwalifikacyjnej nie są wbudowane natywnie w JavaScript. To utrudnia trochę naukę, ale hej JavaScript kiedyś nie był językiem back-end-owym (Node.js) więc brak taki struktur nie powinien Cię zaskoczyć.
Oto najbardziej popularne struktury :
Stack - Stos
Stos to struktura "ostatni pierwszy wychodzi" , czyli najnowszy element dodany do struktury wyjdzie pierwszy. To tak jak stos książek. Książka, która jest na samej górze zostanie wyjęta jako pierwsza, nawet jeśli interesuje Cię książka niżej.
Czyli jeśli chcesz zdobyć 3 książkę na stosie 5 książek to najpierw musisz usnąć książkę numer 5 i 4.
Zalety? Koszt wyjęcia elementu, jak i jego dodanie zawsze będzie taki sam. Nie wykonujesz żadnego sortowania w trakcie takiego działania
Wady. Koszt wyjęcia elementu N z tego stosu będzie zależny od tego, jak głęboko w nim on jest. W tablicy możesz wyjąc dowolny element bez zbędnych operacji.
Metody potrzebne do stworzenia klasy stosu w JavaScript.
- pop() : Wyjmuje element górny ze stosu
- push() ; Dodaje element na gore stosu
- peek() : Zwraca element z góry stosu, ale go nie usuwa
- isEmpty() : Zwraca true, jeśli stos jest pusty
- get length(): zwraca liczbę elementów znajdujących się na stosie
JavaScript wspiera klasy więc użyjemy tej notacji do implementacji stosu. Chociaż jest możliwe stworzenie stosu używając tylko funkcji.
Na początku potrzebujemy konstruktora, który zadeklaruje nam tablicę, która będzie rdzeniem naszego stosu.
Górna część naszego stosu będzie po stronie prawej naszej tablicy.
class Stack {
constructor() {
this.stack = [];
}
}Będziemy musieli mieć opcję sprawdzenie ile elementów ma nasz stos.
get lenght() {
return this.stack.length;
}Później dodajmy metodę, która doda element na górze stosu. Możemy skorzystać z gotowej metody array.push(), która doda nowy element do tablicy po prawej stronie.
push(item) {
return this.stack.push(item);
}
W podobny sposób możemy rozwiązać problem z wyjmowaniem górnego elementu stosu . Mamy do dyspozycji metodę array.pop(), która to zrobi za nas.
pop() {
return this.stack.pop();
}Metoda peek ma zwrócić element na samym spodzie stosu. Wyjmujemy więc element z tablicy o najwyższym indeksie w tablicy, aby to zrobić.
peek() {
return this.stack[this.length - 1];
}Do implementacji dodałem też metodę, która sprawdzi, czy obecnie stos jest pusty
isEmpty() {
return this.length === 0;
}Cały kod wygląda tak:
class Stack {
constructor() {
this.stack = [];
}
get lenght() {
return this.stack.length ;
}
push(item) {
return this.stack.push(item);
}
pop() {
return this.stack.pop();
}
peek() {
return this.stack[this.length - 1];
}
isEmpty() {
return this.length === 0;
}
}Queues - Kolejki
Kolejki działają podobnie jak stos tylko one używają filozofii ("Pierwszy wchodzi i pierwszy wychodzi"). Czyli najstarszy element, który wszedł do kolejki jako pierwszy wyjdzie w pierwszej kolejności.
Kolejkę łatwo sobie wyobrazić jako rzeczywistą kolejkę do sklepu lub kolejkę do okienka w urzędzie. Człowiek, który stał najdłużej zostanie obsłużony jako pierwszy.
Kolejki są zbliżone list jednokierunkowych (linked list) i są one głównie używane do przeszukiwania wszerz w strukturach drzewiastych. Kolejki też są używane do implementacji pamięci cache.
Jak jest wada kolejki? Ciężko jest aktualizować istniejące elementy w kolejce. Pamiętaj, że elementy wchodzące i wychodzące są po przeciwstawnych końcach tej kolekcji elementów.
Metody potrzebne do kolejki:
- enqueue() : Dodaje element to końca kolejki
- dequeue() : Usuwa pierwszy element z kolejki
- peek() : Zwraca pierwszy element z kolejki, ale go nie usuwa
- isEmpty() : Sprawdza, czy dana kolejka jest pusta
- get length(): Zwraca długość kolejki
Użyjemy ponownie klas w JavaScript. W konstruktorze tworzymy tablicę, która będzie reprezentować naszą kolejkę. Przód kolejki będzie lewą stroną naszej tablicy, a prawa strona będzie jej tyłem. Czyli pierwszy element z tablicy będzie wychodził.
class Queue {
constructor() {
this.queue = [];
}
}
Ponownie tworzymy metodę, która zwróci wielkość tablicy.
get length() {
return this.queue.length;
}
Teraz napiszemy metodę dodania elementu do kolejki. Metoda array.push() doda nowy element z prawej strony tablicy.
Natomiast metoda usuwający pierwszy element z kolejki/tablicy też już istnieje w JavaScript i jest to metoda array.shift()
enqueue(item) {
this.queue.push(item);
}
dequeue() {
return this.queue.shift();
}
Odwołujemy się do elementu na indeksie 0, aby zwrócić element, który najszybciej zostanie zwrócony z tej kolejki.
peek() {
return this.queue[0];
}
isEmpty() {
return this.length === 0;
}
Kompletna implementacja kolejki wygląda tak:
class Queue {
constructor() {
this.queue = [];
}
get length() {
return this.queue.length;
}
enqueue(item) {
this.queue.push(item);
}
dequeue() {
return this.queue.shift();
}
peek() {
return this.queue[0];
}
isEmpty() {
return this.length === 0;
}
}
To by było na tyle do zobaczenia w trudniejszych przykładach z listą jednokierunkową. Przynajmniej teraz wiesz jak się przygotować z pytań o struktury danych w JavaScript
