Réapprendre les bases de CS - Implémentation de la pile

J'ai essayé d'apprendre un nouveau langage de programmation et quelle meilleure façon de le faire que de partir des bases. Dans cette série d'articles à venir, je tenterai d'implémenter une structure de données et des algorithmes simples à l'aide de Go. 

Dans le livre An Introduction to algorithms By CLRS dans le chapitre Structure de données élémentaire, la première structure de données dont on parle est la pile.

Qu'est-ce qu'une pile

La pile est une structure de données simple utilisée pour stocker un ensemble d'éléments. Les propriétés d'une pile sont qu'elle nous permet d'ajouter un élément en haut de la pile et de le supprimer de la pile afin qu'il suive le principe Last In First Out ou LIFO.

L'opération d'insertion s'appelle un Push et l'opération de suppression s'appelle un Pop. Puisque nous ne voulons pas qu'une pile vide apparaisse et que nous traitions les erreurs de mémoire, nous implémentons également une vérification pour savoir si une pile est vide ou non. Structure de données assez simple.

Vous trouverez ci-dessous l'implémentation de la stack dans Golang. La complexité temporelle est O(N) et la complexité spatiale de l'utilisation d'une pile est 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())
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!