Go Structures de données: pile

Analyse et implémentation de la structure de données Stack dans Go

Une pile est une collection ordonnée d'articles selon le principe du dernier entré, premier sorti (LIFO). Nous ajoutons et supprimons des éléments de la même partie de la pile, appelée le haut. Nous ne pouvons pas supprimer des éléments de la base. Tout comme une pile de livres.

Les piles ont des tonnes d'utilisations, de la création d'un historique des pages visitées aux commandes entrées et au stockage des actions qui peuvent être annulées.

Mise en œuvre

En interne, la pile sera représentée par unslicetapez, et je vais exposer le

  • Push()
  • Pull()
  • New()

méthodes.

New()sert de constructeur, qui initialise la tranche interne lorsque nous commençons à l'utiliser.

Je vais créer unItemStacktype générique, sécurisé pour la concurrence, qui peut générer des piles contenant n'importe quel type en utilisantgenny, pour créer une implémentation de pile spécifique au type, encapsulant la structure de données spécifique à la valeur réelle contenant les données.

// Package stack creates a ItemStack data structure for the Item type
package stack

import (
“sync”


<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)


// Item the type of the stack
type Item generic.Type


// ItemStack the stack of Items
type ItemStack struct {
items []Item
lock  sync.RWMutex
}


// New creates a new ItemStack
func (s ItemStack) New() ItemStack {
s.items = []Item{}
return s
}


// Push adds an Item to the top of the stack
func (s *ItemStack) Push(t Item) {
s.lock.Lock()
s.items = append(s.items, t)
s.lock.Unlock()
}


// Pop removes an Item from the top of the stack
func (s ItemStack) Pop() Item {
s.lock.Lock()
item := s.items[len(s.items)-1]
s.items = s.items[0 : len(s.items)-1]
s.lock.Unlock()
return &item
}

Des tests

Les tests décrivent l'utilisation de l'implémentation ci-dessus.

package stack

import (
“testing”
)


var s ItemStack


func initStack() *ItemStack {
if s.items == nil {
s = ItemStack{}
s.New()
}
return &s
}


func TestPush(t *testing.T) {
s := initStack()
s.Push(1)
s.Push(2)
s.Push(3)
if size := len(s.items); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
}


func TestPop(t *testing.T) {
s.Pop()
if size := len(s.items); size != 2 {
t.Errorf(“wrong count, expected 2 and got %d”, size)
}


<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Pop</span>()
<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Pop</span>()
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> len(<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">items</span>); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">0</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 0 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

}

Création d'une structure de données de pile en béton

Vous pouvez utiliser cette implémentation générique pour générer des piles spécifiques à un type, en utilisant

//generate a `IntStack` stack of `int` values
genny -in stack.go -out stack-int.go gen "Item=int"

//generate a </span>StringStack<span style="color:#e6db74"> stack of </span>string<span style="color:#e6db74"> values
genny -in stack.go -out stack-string.go gen “Item=string”


Plus de tutoriels go:


Tech Wiki en ligne!