Jak napisać stos w Swift

30 Października 2017

Dzisiejszy wpis zainspirował mnie do stworzenia nowej kategorii na tym blog, który z dumą nazwałem Algorytmy💥. Brzmi dumnie, nie?

Ale do rzeczy – podczas swojej pierwszej rozmowy o pracę jako mobile deweloper, zostałem poproszony o napisanie stosu. W zasadzie zadanie wydaje się dość proste, ale jako osoba, która wtedy nie miała na studiach zajęć z podstaw programowania, poczułem jak pot leci mi po plecach.

Ale od początku, czym jest stos i po się to pisze? Zapraszam do lektury🚀.

Czym jest stos?

Stos, z angielskiego Stack(to ważne bo zapewne spotkacie się z tą nazwą w 90%) to liniowa strutura danych, w której dane mogę być dokładane na wierzch, pobierane i usuwane.

Idea stosu
Stos przedstawiony w postaci urządzeń Apple

Podobnie jak na powyższym obrazku, stos możesz sobie zwizualizować jako po prostu stertę urządzeń mobilnych📱, książek📚, sztabek złota🏆 etc., na który to możemy dokładać kolejne przedmioty lub je z niego ściągać. Możemy także odczytać, tz. zobaczyć co jest na szczycie (peek) stosu.

Stos jest obecnie wykorzystywany w systemach komuterowych, np. do przechowywania zmiennych lokalnych czy przechowywania rejestrów systemowych. Stosy znajdują swoje zastosowanie również w programowaniu wysokopoziomowym.

Skąd wziął się stos?

Wikipedia głosi, że stos pojawił się w literaturze w 1946r. Kiedy to Alan Turing użył pojęć bury and unbury jako wyjaśnienie dla podprogramu.

Implementacja stosu w języku Swift 4

Stos możemy implementować z zastosowaniem zmiennych typu kolekcja. W naszym przypadku posłużę się tablicą. Swift jest językiem na tyle dojrzałym, że struktura typu Array bardzo ułatwi nam implementację. Zatem Panie, Panowie, do kodu!

Na początek musimy stworzyć typ stosu. Chcemy też, żeby w stosie mogły być przechowywane zmienne typu, który określimy sobie przy inicjalizacji. Z pomocą przychodzą Generics:


    struct Stack<Thing>{}

Do tego tworzymy sobię naszą tablicę, która będzie reprezentowała nasz stos. Zmienną tworzę jako zmienną prywatną, na której będą przeprowadzane operację dokładanie i usuwania elementów stosu:


    struct Stack<Thing>{
        private var array: [Thing] = []
    }

Stos musi posiadać takie metody, jak dokłądanie na wierzch, usuwanie oraz odczyt ostatniego elementu. Ok, dodajmy te metody.


    struct Stack<Thing>{
        private var array: [Thing] = []
        
        mutating func push(_ element: Thing){
            array.append(element)
        }
        
        mutating func pop() -> Thing?{
            return array.popLast()
        }
        
        func peek() -> Thing? {
            return array.last
        }
    }

Ja ze zwojej strony dodałbym jeszcze metodę, która sprawdzi, czy stos jest pusty.


    func isEmpty() -> Bool{
        if array.count <= 0{
            return true
        }
        return false
    }

I jest! Stos jest zaimplementowany. Jeszcze tylko mały test:


    var stack = Stack<String>()
    stack.push("Welcome, Stack!")
    stack.peek()                     // "Welcome, Stack!"
    stack.isEmpty()                  // false
    stack.pop()                      // "Welcome, Stack!"
    stack.pop()                      // nil
    stack.isEmpty()                  // true

Like a charm 💥. Działa wszystko jak należy.

Konkluzje

Stos to prosty algorytm, który każdy student informatyki realizuje w pare minut, a przynajmniej powinien. Jeśli to była dla Ciebie nowość, to cieszę się że akurat tutaj trafiłeś 😎.

Podczas mojej pierwszej rozmowy w roli mobile dewelopera to właśnie napisanie stosu było moim zadaniem. Wiem, że dziś jest to stosowane zarówno w Swift, jak i innych językach jako pytanie techniczne dla młodych stażem, aspisujących deweloperów. Dlatego warto się z tym zapoznać, nie ważne w jakim języku programujesz.

To tyle na dzisiaj, dzięki za wspólnie spędzony czas, doceniam!!
Mam nadzieję że znalazleś tu dla siebie jakąś wartość!
Jeśli masz coś ciekawego do dodania, chcesz o coś zapytać, znalazłeś błąd albo po prsotu chcesz podagać, daj proszę znać w komentarzach albo napisz do mnie na Twittku (@jkornat), albo daj follow na Snapie (jakornat).

Trzymaj się i do następnego wpisu! 👊
@jkornat

Jak napisać stos w Swift

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *