Grundlagen von CS neu erlernen – Stack implementieren

Ich habe versucht, eine neue Programmiersprache zu lernen und wie könnte man das besser machen, als mit den Grundlagen anzufangen? In dieser Reihe von Beiträgen werde ich versuchen, eine einfache Datenstruktur und Algorithmen mithilfe von Go zu implementieren. 

Im Buch „An Introduction to algorithms“ von CLRS wird im Kapitel „Elementare Datenstruktur“ als erste Datenstruktur über den Stapel gesprochen.

Was ist ein Stapel?

Stack ist eine einfache Datenstruktur, die zum Speichern einer Reihe von Elementen verwendet wird. Die Eigenschaften eines Stapels bestehen darin, dass wir ein Element oben auf den Stapel legen und daraus entfernen können, sodass es dem Last-In-First-Out-Prinzip oder LIFO folgt.

Der Einfügungsvorgang wird Push genannt und der Entfernungsvorgang wird Pop genannt. Da wir nicht wollen, dass ein leerer Stack auftaucht und wir uns nicht mit Speicherfehlern befassen, implementieren wir auch eine Prüfung, ob ein Stack leer ist oder nicht. Ziemlich einfache Datenstruktur.

Unten finden Sie die Implementierung des Stacks in Golang. Die Zeitkomplexität beträgt O(N) und die räumliche Komplexität der Verwendung eines Stapels beträgt O(1)

package main

import "fmt"

type Stack []int

func (stack *Stack) Push (value int){
    *stack = append(*stack, value)
}

func (stack *Stack) Pop () int{
    if stack.IsEmpty() {
        return 0
    }
    top := (*stack)[len(*stack)-1]
    *stack = (*stack)[:len(*stack)-1]
    return top
}

func (stack *Stack) IsEmpty() bool{
    return len(*stack) == 0
}


func main(){
    st := Stack{}
    st.Push(1)
    st.Push(2)
    fmt.Println(st.Pop())
}

Das obige ist der detaillierte Inhalt vonGrundlagen von CS neu erlernen – Stack implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!