Ir a estructuras de datos: apilar

Análisis e implementación de la estructura de datos Stack en Go

Una pila es una colección ordenada de elementos que sigue el principio de último en entrar, primero en salir (LIFO). Agregamos y eliminamos elementos de la misma parte de la pila, llamada parte superior. No podemos quitar elementos de la base. Como una pila de libros.

Las pilas tienen muchos usos, desde crear un historial de páginas visitadas hasta comandos ingresados y almacenar acciones que se pueden deshacer.

Implementación

Internamente, la pila se representará con unslicetipo, y expondré el

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

métodos.

New()sirve como constructor, que inicializa el segmento interno cuando comenzamos a usarlo.

Voy a crear unItemStacktipo genérico, seguro para la concurrencia, que puede generar pilas que contengan cualquier tipo usandogenny, para crear una implementación de pila específica de tipo, encapsulando la estructura de datos específica del valor real que contiene los datos.

// 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
}

Pruebas

Las pruebas describen el uso de la implementación anterior.

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>)
}

}

Crear una estructura de datos de pila de hormigón

Puede usar esta implementación genérica para generar pilas específicas de tipo, usando

//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”


Más tutoriales de go:


Tech Wiki en línea!