Szukaj…


Wprowadzenie

Algorytmy są podstawą przetwarzania. Dokonanie wyboru algorytmu, który ma być użyty, w której sytuacji odróżnia średnią od dobrego programisty. Mając to na uwadze, oto definicje i przykłady kodu niektórych podstawowych algorytmów.

Sortowanie przez wstawianie

Sortowanie przez wstawianie jest jednym z bardziej podstawowych algorytmów w informatyce. Sortowanie wstawiania szereguje elementy poprzez iterację w kolekcji i pozycjonuje elementy na podstawie ich wartości. Zestaw jest podzielony na posortowane i nieposortowane połówki i powtarza się, aż wszystkie elementy zostaną posortowane. Sortowanie przez wstawianie ma złożoność O (n2). Możesz umieścić go w rozszerzeniu, jak na poniższym przykładzie, lub możesz stworzyć dla niego metodę.

extension Array where Element: Comparable {

func insertionSort() -> Array<Element> {
    
    //check for trivial case
    guard self.count > 1 else {
        return self
    }
    
    //mutated copy
    var output: Array<Element> = self
    
    for primaryindex in 0..<output.count {
        
        let key = output[primaryindex]
        var secondaryindex = primaryindex
        
        while secondaryindex > -1 {
            if key < output[secondaryindex] {
                
                //move to correct position
                output.remove(at: secondaryindex + 1)
                output.insert(key, at: secondaryindex)
            }
            secondaryindex -= 1
        }
    }
    
    return output
}
}

Sortowanie

Sortowanie bąbelkowe

Jest to prosty algorytm sortowania, który wielokrotnie przechodzi przez sortowaną listę, porównuje każdą parę sąsiednich elementów i zamienia je, jeśli są w niewłaściwej kolejności. Przejście przez listę jest powtarzane, dopóki nie są potrzebne żadne zamiany. Chociaż algorytm jest prosty, jest zbyt wolny i niepraktyczny w przypadku większości problemów. Ma złożoność O (n2), ale jest uważany za wolniejszy niż sortowanie przez wstawianie.

extension Array where Element: Comparable {

func bubbleSort() -> Array<Element> {
    
    //check for trivial case
    guard self.count > 1 else {
        return self
    }
    
    //mutated copy
    var output: Array<Element> = self
    
    for primaryIndex in 0..<self.count {
        let passes = (output.count - 1) - primaryIndex
        
        //"half-open" range operator
        for secondaryIndex in 0..<passes {
            let key = output[secondaryIndex]
            
            //compare / swap positions
            if (key > output[secondaryIndex + 1]) {
                swap(&output[secondaryIndex], &output[secondaryIndex + 1])
            }
        }
    }
    
    return output
}

}

Sortowanie przez wstawianie

Sortowanie przez wstawianie jest jednym z bardziej podstawowych algorytmów w informatyce. Sortowanie wstawiania szereguje elementy poprzez iterację w kolekcji i pozycjonuje elementy na podstawie ich wartości. Zestaw jest podzielony na posortowane i nieposortowane połówki i powtarza się, aż wszystkie elementy zostaną posortowane. Sortowanie przez wstawianie ma złożoność O (n2). Możesz umieścić go w rozszerzeniu, jak na poniższym przykładzie, lub możesz stworzyć dla niego metodę.

extension Array where Element: Comparable {

func insertionSort() -> Array<Element> {
    
    //check for trivial case
    guard self.count > 1 else {
        return self
    }
    
    //mutated copy
    var output: Array<Element> = self
    
    for primaryindex in 0..<output.count {
        
        let key = output[primaryindex]
        var secondaryindex = primaryindex
        
        while secondaryindex > -1 {
            if key < output[secondaryindex] {
                
                //move to correct position
                output.remove(at: secondaryindex + 1)
                output.insert(key, at: secondaryindex)
            }
            secondaryindex -= 1
        }
    }
    
    return output
}
}

Sortuj wybór

Sortowanie zaznaczone jest ze względu na swoją prostotę. Zaczyna się od pierwszego elementu w tablicy, zapisując jego wartość jako wartość minimalną (lub maksymalną, w zależności od kolejności sortowania). Następnie iteruje przez tablicę i zastępuje wartość min dowolną inną wartością mniejszą niż wartość min, którą znajdzie po drodze. Ta minimalna wartość jest następnie umieszczana w skrajnej lewej części tablicy i proces jest powtarzany, od następnego indeksu, aż do końca tablicy. Sortowanie selekcji ma złożoność O (n2), ale jest uważane za wolniejsze niż jego odpowiednik - Sortowanie selekcji.

func selectionSort () -> Array {// sprawdź, czy trywialny case guard self.count> 1 else {return self}

//mutated copy
var output: Array<Element> = self
 
for primaryindex in 0..<output.count {
    var minimum = primaryindex
    var secondaryindex = primaryindex + 1
     
    while secondaryindex < output.count {
        //store lowest value as minimum
        if output[minimum] > output[secondaryindex] {
            minimum = secondaryindex
        }
        secondaryindex += 1
    }
     
    //swap minimum value with array iteration
    if primaryindex != minimum {
        swap(&output[primaryindex], &output[minimum])
    }
}
 
return output 
}

Szybkie sortowanie - czas złożoności O (n log n)

Quicksort jest jednym z zaawansowanych algorytmów. Charakteryzuje się złożonością czasową O (n log n) i stosuje strategię dziel i zwyciężaj. Ta kombinacja skutkuje zaawansowaną wydajnością algorytmiczną. Quicksort najpierw dzieli dużą tablicę na dwie mniejsze pod-tablice: niskie elementy i wysokie elementy. Quicksort może następnie rekurencyjnie sortować pod-tablice.

Kroki są następujące:

Wybierz element zwany osią przestawną z tablicy.

Zmień kolejność tablic, aby wszystkie elementy o wartościach mniejszych niż pivot znajdowały się przed pivotem, a wszystkie elementy o wartościach większych niż pivot pojawiały się po nim (równe wartości mogą iść w obie strony). Po tym podziale punkt obrotu znajduje się w końcowej pozycji. Nazywa się to operacją partycji.

Rekurencyjnie zastosuj powyższe kroki do podgrupy elementów o mniejszych wartościach i osobno do podgrupy elementów o większych wartościach.

mutating func quickSort () -> Array {

func qSort(start startIndex: Int, _ pivot: Int) {
    
    if (startIndex < pivot) {
        let iPivot = qPartition(start: startIndex, pivot)
        qSort(start: startIndex, iPivot - 1)
        qSort(start: iPivot + 1, pivot)
    }
}
qSort(start: 0, self.endIndex - 1)
return self
}

mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {

var wallIndex: Int = startIndex

//compare range with pivot
for currentIndex in wallIndex..<pivot {
    
    if self[currentIndex] <= self[pivot] {
        if wallIndex != currentIndex {
            swap(&self[currentIndex], &self[wallIndex])
        }
        
        //advance wall
        wallIndex += 1
    }
}
    //move pivot to final position
    if wallIndex != pivot {
        swap(&self[wallIndex], &self[pivot])
    }
    return wallIndex
}

Sortuj wybór

Sortowanie zaznaczone jest ze względu na swoją prostotę. Zaczyna się od pierwszego elementu w tablicy, zapisując jego wartość jako wartość minimalną (lub maksymalną, w zależności od kolejności sortowania). Następnie iteruje przez tablicę i zastępuje wartość min dowolną inną wartością mniejszą niż wartość min, którą znajdzie po drodze. Ta minimalna wartość jest następnie umieszczana w skrajnej lewej części tablicy i proces jest powtarzany, od następnego indeksu, aż do końca tablicy. Sortowanie selekcji ma złożoność O (n2), ale jest uważane za wolniejsze niż jego odpowiednik - Sortowanie selekcji.

func selectionSort() -> Array<Element> {
    //check for trivial case
    guard self.count > 1 else {
        return self
    }
     
    //mutated copy
    var output: Array<Element> = self
     
    for primaryindex in 0..<output.count {
        var minimum = primaryindex
        var secondaryindex = primaryindex + 1
         
        while secondaryindex < output.count {
            //store lowest value as minimum
            if output[minimum] > output[secondaryindex] {
                minimum = secondaryindex
            }
            secondaryindex += 1
        }
         
        //swap minimum value with array iteration
        if primaryindex != minimum {
            swap(&output[primaryindex], &output[minimum])
        }
    }
     
    return output
}

Analiza asymptotyczna

Ponieważ mamy wiele różnych algorytmów do wyboru, kiedy chcemy posortować tablicę, musimy wiedzieć, który z nich wykona swoją pracę. Potrzebujemy zatem metody pomiaru szybkości i niezawodności algorytmu. Właśnie tam rozpoczyna się analiza asymptotyczna. Analiza asymptotyczna to proces opisywania wydajności algorytmów wraz ze wzrostem wielkości wejściowej (n). W informatyce asymptotyki są zwykle wyrażane we wspólnym formacie znanym jako Big O Notation.

  • Czas liniowy O (n) : Gdy każdy element w tablicy musi zostać oceniony, aby funkcja mogła osiągnąć swój cel, oznacza to, że funkcja staje się mniej skuteczna w miarę wzrostu liczby elementów. Mówi się, że taka funkcja działa w czasie liniowym, ponieważ jej prędkość zależy od wielkości wejściowej.
  • Czas wielomianowy O (n2) : Jeśli złożoność funkcji rośnie wykładniczo (co oznacza, że dla n elementów tablicy złożoność funkcji jest równa n kwadratowi), funkcja działa w czasie wielomianowym. Są to zwykle funkcje z zagnieżdżonymi pętlami. Dwie zagnieżdżone pętle powodują złożoność O (n2), trzy zagnieżdżone pętle powodują złożoność O (n3) i tak dalej ...
  • Czas logarytmiczny O (log n): Złożoność funkcji czasu logarytmicznego jest zminimalizowana, gdy rośnie wielkość danych wejściowych (n). To są funkcje, o które dąży każdy programista.

Szybkie sortowanie - czas złożoności O (n log n)

Quicksort jest jednym z zaawansowanych algorytmów. Charakteryzuje się złożonością czasową O (n log n) i stosuje strategię dziel i zwyciężaj. Ta kombinacja skutkuje zaawansowaną wydajnością algorytmiczną. Quicksort najpierw dzieli dużą tablicę na dwie mniejsze pod-tablice: niskie elementy i wysokie elementy. Quicksort może następnie rekurencyjnie sortować pod-tablice.

Kroki są następujące:

  1. Wybierz element zwany osią przestawną z tablicy.

  2. Zmień kolejność tablic, aby wszystkie elementy o wartościach mniejszych niż pivot znajdowały się przed pivotem, a wszystkie elementy o wartościach większych niż pivot pojawiały się po nim (równe wartości mogą iść w obie strony). Po tym podziale punkt obrotu znajduje się w końcowej pozycji. Nazywa się to operacją partycji.

  3. Rekurencyjnie zastosuj powyższe kroki do podgrupy elementów o mniejszych wartościach i osobno do podgrupy elementów o większych wartościach.

    mutating func quickSort() -> Array<Element> {
    
    func qSort(start startIndex: Int, _ pivot: Int) {
        
        if (startIndex < pivot) {
            let iPivot = qPartition(start: startIndex, pivot)
            qSort(start: startIndex, iPivot - 1)
            qSort(start: iPivot + 1, pivot)
        }
    }
    qSort(start: 0, self.endIndex - 1)
    return self
    

    }

    mutating func qPartition (start startIndex: Int, _ pivot: Int) -> Int {

    var wallIndex: Int = startIndex
    
    //compare range with pivot
    for currentIndex in wallIndex..<pivot {
        
        if self[currentIndex] <= self[pivot] {
            if wallIndex != currentIndex {
                swap(&self[currentIndex], &self[wallIndex])
            }
            
            //advance wall
            wallIndex += 1
        }
    }
    
    //move pivot to final position
    if wallIndex != pivot {
        swap(&self[wallIndex], &self[pivot])
    }
    return wallIndex
}

Wykres, Trie, Stos

Wykres

W informatyce wykres jest abstrakcyjnym typem danych, który ma zaimplementować koncepcje grafów bezkierunkowych i grafów ukierunkowanych z matematyki. Struktura danych wykresu składa się ze skończonego (i prawdopodobnie zmiennego) zestawu wierzchołków, węzłów lub punktów, wraz z zestawem nieuporządkowanych par tych wierzchołków dla wykresu niekierowanego lub zestawu uporządkowanych par dla wykresu ukierunkowanego. Pary te są znane jako krawędzie, łuki lub linie dla niekierowanego wykresu oraz jako strzałki, skierowane krawędzie, skierowane łuki lub ukierunkowane linie dla ukierunkowanego wykresu. Wierzchołki mogą być częścią struktury grafu lub mogą być podmiotami zewnętrznymi reprezentowanymi przez indeksy lub odwołania całkowite. Struktura danych wykresu może również powiązać z każdą krawędzią pewną wartość krawędzi, taką jak symboliczna etykieta lub atrybut numeryczny (koszt, pojemność, długość itp.). (Wikipedia, źródło )

//
//  GraphFactory.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 6/7/14.
//  Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation


public class SwiftGraph {
   
    
    //declare a default directed graph canvas
    private var canvas: Array<Vertex>
    public var isDirected: Bool
    
    
    init() {
        canvas = Array<Vertex>()
        isDirected = true
    }
    
    
    //create a new vertex
    func addVertex(key: String) -> Vertex {
        
        
        //set the key
        let childVertex: Vertex = Vertex()
        childVertex.key = key
        
        
        //add the vertex to the graph canvas
        canvas.append(childVertex)
        
        
        return childVertex
    }
    
    
    
    //add edge to source vertex
    func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
        
        
        //create a new edge
        let newEdge = Edge()
        
        
        //establish the default properties
        newEdge.neighbor = neighbor
        newEdge.weight = weight
        source.neighbors.append(newEdge)
        
        
        print("The neighbor of vertex: \(source.key as String!) is \(neighbor.key as String!)..")
        
        
        //check condition for an undirected graph
        if isDirected == false {
            
            
           //create a new reversed edge
           let reverseEdge = Edge()
            
            
           //establish the reversed properties
           reverseEdge.neighbor = source
           reverseEdge.weight = weight
           neighbor.neighbors.append(reverseEdge)
            
           print("The neighbor of vertex: \(neighbor.key as String!) is \(source.key as String!)..")
            
        }
        
        
    }

    
    
    
    
    /* reverse the sequence of paths given the shortest path.
       process analagous to reversing a linked list. */

    func reversePath(_ head: Path!, source: Vertex) -> Path! {
        
        
        guard head != nil else {
            return head
        }
        
        //mutated copy
        var output = head
        
        
        var current: Path! = output
        var prev: Path!
        var next: Path!
        
        
        while(current != nil) {
            next = current.previous
            current.previous = prev
            prev = current
            current = next
        }
        
        
        //append the source path to the sequence
        let sourcePath: Path = Path()
        
        sourcePath.destination = source
        sourcePath.previous = prev
        sourcePath.total = nil
        
        output = sourcePath
        
        
        return output
        
    }

    
    
    
    //process Dijkstra's shortest path algorthim
    func processDijkstra(_ source: Vertex, destination: Vertex) -> Path? {
        
        
        var frontier: Array<Path> = Array<Path>()
        var finalPaths: Array<Path> = Array<Path>()
        
        
        //use source edges to create the frontier
        for e in source.neighbors {
            
            let newPath: Path = Path()
            
            
            newPath.destination = e.neighbor
            newPath.previous = nil
            newPath.total = e.weight
            
            
            //add the new path to the frontier
            frontier.append(newPath)
            
        }
        

        //construct the best path
        var bestPath: Path = Path()
        
        
        while frontier.count != 0 {
            
            //support path changes using the greedy approach
            bestPath = Path()
            var pathIndex: Int = 0

            
            for x in 0..<frontier.count {
               
                let itemPath: Path = frontier[x]
                
                if  (bestPath.total == nil) || (itemPath.total < bestPath.total) {
                    bestPath = itemPath
                    pathIndex = x
                }
                
            }
            
            
            
            //enumerate the bestPath edges
            for e in bestPath.destination.neighbors {
                
                let newPath: Path = Path()
                
                newPath.destination = e.neighbor
                newPath.previous = bestPath
                newPath.total = bestPath.total + e.weight
                
                
                //add the new path to the frontier
                frontier.append(newPath)
                
            }
            
            
            //preserve the bestPath
            finalPaths.append(bestPath)
            
            
            //remove the bestPath from the frontier
            //frontier.removeAtIndex(pathIndex) - Swift2
            frontier.remove(at: pathIndex)
            
            
            
        } //end while
        
        
    
        //establish the shortest path as an optional
        var shortestPath: Path! = Path()
        
        
        for itemPath in finalPaths {
            
            if (itemPath.destination.key == destination.key) {
                
                if  (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
                    shortestPath = itemPath
                }
                
            }
            
        }
        
        
        return shortestPath
        
    }
    
    
    
    ///an optimized version of Dijkstra's shortest path algorthim
    func processDijkstraWithHeap(_ source: Vertex, destination: Vertex) -> Path! {
        
        
        let frontier: PathHeap = PathHeap()
        let finalPaths: PathHeap = PathHeap()
        
        
        //use source edges to create the frontier
        for e in source.neighbors {
            
            let newPath: Path = Path()
            
            
            newPath.destination = e.neighbor
            newPath.previous = nil
            newPath.total = e.weight
            
            
            //add the new path to the frontier
            frontier.enQueue(newPath)
            
        }
        
        
        //construct the best path
        var bestPath: Path = Path()
        
        
        while frontier.count != 0 {
                        
            //use the greedy approach to obtain the best path
            bestPath = Path()
            bestPath = frontier.peek()
            
            
            //enumerate the bestPath edges
            for e in bestPath.destination.neighbors {
                
                let newPath: Path = Path()
                
                newPath.destination = e.neighbor
                newPath.previous = bestPath
                newPath.total = bestPath.total + e.weight
                
                
                //add the new path to the frontier
                frontier.enQueue(newPath)
                
            }
            
            
            //preserve the bestPaths that match destination
            if (bestPath.destination.key == destination.key) {
                finalPaths.enQueue(bestPath)
            }
            
            
            //remove the bestPath from the frontier
            frontier.deQueue()
            
            
        } //end while
        
        
        
        //obtain the shortest path from the heap
        var shortestPath: Path! = Path()
        shortestPath = finalPaths.peek()
        
        
        return shortestPath
        
    }
    
    
    //MARK: traversal algorithms
    
    
    //bfs traversal with inout closure function
    func traverse(_ startingv: Vertex, formula: (_ node: inout Vertex) -> ()) {

        
        //establish a new queue
        let graphQueue: Queue<Vertex> = Queue<Vertex>()
        
        
        //queue a starting vertex
        graphQueue.enQueue(startingv)
        
        
        while !graphQueue.isEmpty() {
            
            //traverse the next queued vertex
            var vitem: Vertex = graphQueue.deQueue() as Vertex!
            
            
            //add unvisited vertices to the queue
            for e in vitem.neighbors {
                if e.neighbor.visited == false {
                    print("adding vertex: \(e.neighbor.key!) to queue..")
                    graphQueue.enQueue(e.neighbor)
                }
            }
            

            /*
            notes: this demonstrates how to invoke a closure with an inout parameter.
            By passing by reference no return value is required.
            */
            
            //invoke formula
            formula(&vitem)
            
            
        } //end while
        
        
        print("graph traversal complete..")
        
        
    }

    
    
    
    //breadth first search
    func traverse(_ startingv: Vertex) {
        
        
        //establish a new queue
        let graphQueue: Queue<Vertex> = Queue<Vertex>()
        
        
        //queue a starting vertex
        graphQueue.enQueue(startingv)
        
        
        while !graphQueue.isEmpty() {
            
            //traverse the next queued vertex
            let vitem = graphQueue.deQueue() as Vertex!
            
            guard vitem != nil else {
                return
            }
            
            //add unvisited vertices to the queue
            for e in vitem!.neighbors {
                if e.neighbor.visited == false {
                    print("adding vertex: \(e.neighbor.key!) to queue..")
                    graphQueue.enQueue(e.neighbor)
                }
            }
            
            
            vitem!.visited = true
            print("traversed vertex: \(vitem!.key!)..")
            
            
        } //end while
        
        
        print("graph traversal complete..")
        
        
    } //end function
    
    
    
    //use bfs with trailing closure to update all values
    func update(startingv: Vertex, formula:((Vertex) -> Bool)) {
        
        
        //establish a new queue
        let graphQueue: Queue<Vertex> = Queue<Vertex>()
        
        
        //queue a starting vertex
        graphQueue.enQueue(startingv)
        
        
        while !graphQueue.isEmpty() {
            
            //traverse the next queued vertex
            let vitem = graphQueue.deQueue() as Vertex!            
            
            guard vitem != nil else {
                return
            }
            
            //add unvisited vertices to the queue
            for e in vitem!.neighbors {
                if e.neighbor.visited == false {
                    print("adding vertex: \(e.neighbor.key!) to queue..")
                    graphQueue.enQueue(e.neighbor)
                }
            }
            
            
            //apply formula..
            if formula(vitem!) == false {
                print("formula unable to update: \(vitem!.key)")
            }
            else {
                print("traversed vertex: \(vitem!.key!)..")
            }
            
            vitem!.visited = true
            
            
        } //end while
        
        
        print("graph traversal complete..")
        
        
    }

    

    
    
}

Trie

W informatyce trie, zwane także drzewem cyfrowym, a czasem drzewem radix lub drzewem prefiksu (ponieważ można je wyszukiwać za pomocą prefiksów), jest rodzajem drzewa wyszukiwania - uporządkowanej struktury danych drzewa, która służy do przechowywania zestawu dynamicznego lub asocjacyjnego tablica, w której klucze są zwykle łańcuchami. (Wikipedia, źródło )

//
//  Trie.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 10/14/14.
//  Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation


public class Trie {
    
    private var root: TrieNode!
    
    
    init(){
        root = TrieNode()
    }
    
    
    
    //builds a tree hierarchy of dictionary content
    func append(word keyword: String) {
        
        
        //trivial case
        guard keyword.length > 0 else {
            return
        }
        
        
        var current: TrieNode = root
        
        
        while keyword.length != current.level {
            
            var childToUse: TrieNode!
            let searchKey = keyword.substring(to: current.level + 1)
            
            
            //print("current has \(current.children.count) children..")
            
            
            //iterate through child nodes
            for child in current.children {
                
                if (child.key == searchKey) {
                    childToUse = child
                    break
                }
                
            }
            
            
            //new node
            if childToUse == nil {
                
                childToUse = TrieNode()
                childToUse.key = searchKey
                childToUse.level = current.level + 1
                current.children.append(childToUse)
            }
            
            
            current = childToUse
            
            
        } //end while
        
        
        //final end of word check
        if (keyword.length == current.level) {
            current.isFinal = true
            print("end of word reached!")
            return
        }
        
        
        
    } //end function
    
    

    
    //find words based on the prefix
    func search(forWord keyword: String) -> Array<String>! {
        
        
        //trivial case
        guard keyword.length > 0 else {
            return nil
        }
        
        
        var current: TrieNode = root
        var wordList = Array<String>()
        
        
        while keyword.length != current.level {
            
            var childToUse: TrieNode!
            let searchKey = keyword.substring(to: current.level + 1)
            

            //print("looking for prefix: \(searchKey)..")
            
            
            //iterate through any child nodes
            for child in current.children {
                
                if (child.key == searchKey) {
                    childToUse = child
                    current = childToUse
                    break
                }
                
            }
            
 
            if childToUse == nil {
               return nil
            }
            
            
        } //end while
        
        
        
        //retrieve the keyword and any descendants
        if ((current.key == keyword) && (current.isFinal)) {
            wordList.append(current.key)
        }

        
        //include only children that are words
        for child in current.children {
            
            if (child.isFinal == true) {
                wordList.append(child.key)
            }
            
        }
        
        
        return wordList

        
    } //end function
    

}

(GitHub, źródło )

Stos

W informatyce stos jest abstrakcyjnym typem danych, który służy jako zbiór elementów, z dwiema głównymi operacjami: push, która dodaje element do kolekcji, i pop, który usuwa ostatnio dodany element, który nie został jeszcze usunięty. Kolejność, w jakiej elementy schodzą ze stosu, powoduje powstanie alternatywnej nazwy LIFO (ostatnie wejście, pierwsze wyjście). Dodatkowo operacja podglądania może dać dostęp do góry bez modyfikowania stosu. (Wikipedia, źródło )

Zobacz informacje o licencji poniżej i oryginalny kod źródłowy na ( github )

//
//  Stack.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 8/1/14.
//  Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation


class Stack<T> {
    
    private var top: Node<T>
    
    init() {
        top = Node<T>()
    }
    
    
    //the number of items - O(n)
    var count: Int {
        
        
        //return trivial case
        guard top.key != nil else {
          return 0
        }
                
        
        var current = top
        var x: Int = 1
        
        
        //cycle through list
        while current.next != nil {
            current = current.next!
            x += 1
        }
            
        return x        
        
    }
    
    
    //add item to the stack
    func push(withKey key: T) {
        
        
        //return trivial case
        guard top.key != nil else {
            top.key = key
            return
        }
        
        
        //create new item
        let childToUse = Node<T>()
        childToUse.key = key
            
            
        //set new created item at top
        childToUse.next = top
        top = childToUse        

    }
    

    //remove item from the stack
    func pop() {
        
        if self.count > 1 {
            top = top.next
        }
        else {
            top.key = nil
        }
        
    }
    
    
    //retrieve the top most item
    func peek() -> T! {

        
        //determine instance
        if let topitem = top.key {
            return topitem
        }
            
        else {
            return nil
        }
        
    }
    
    
    
    //check for value
    func isEmpty() -> Bool {
        
        if self.count == 0 {
            return true
        }
        
        else {
            return false
        }
        
    }
    

}

Licencja MIT (MIT)

Prawa autorskie (c) 2015, Wayne Bishop & Arbutus Software Inc.

Niniejszym udziela się bezpłatnie każdej osobie, która otrzymuje kopię tego oprogramowania i powiązanych plików dokumentacji („Oprogramowanie”), do czynienia z Oprogramowaniem bez ograniczeń, w tym między innymi prawa do używania, kopiowania, modyfikowania, łączenia , publikować, rozpowszechniać, udzielać podlicencji i / lub sprzedawać kopie Oprogramowania oraz zezwalać na to osobom, którym Oprogramowanie zostało dostarczone, z zastrzeżeniem następujących warunków:

Powyższa informacja o prawach autorskich i niniejsza informacja o pozwoleniu będą zawarte we wszystkich kopiach lub znacznych częściach Oprogramowania.

OPROGRAMOWANIE JEST DOSTARCZANE „W STANIE, W JAKIM JEST”, BEZ ŻADNEJ GWARANCJI, WYRAŹNEJ LUB DOROZUMIANEJ, W TYM, ALE NIE OGRANICZONE DO GWARANCJI PRZYDATNOŚCI HANDLOWEJ, PRZYDATNOŚCI DO OKREŚLONEGO CELU I NARUSZENIA. W ŻADNYM WYPADKU AUTORZY LUB POSIADACZE PRAW AUTORSKICH NIE PONOSZĄ ODPOWIEDZIALNOŚCI ZA JAKIEKOLWIEK ROSZCZENIE, SZKODY LUB INNE ODPOWIEDZIALNOŚCI, NAWET W DZIAŁANIU UMOWY, TORTU LUB INNYCH INNYCH DZIAŁALNOŚCI, WYNIKAJĄCE Z, LUB W ZWIĄZKU Z OPROGRAMOWANIEM LUB WYKORZYSTANIEM LUB INNYCH OKREŚLENIAMI OPROGRAMOWANIE.



Modified text is an extract of the original Stack Overflow Documentation
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow