Ir a estructuras de datos: cola

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

Una cola es una colección ordenada de elementos que sigue el principio de primero en entrar, primero en salir (FIFO). Agregamos elementos de un extremo de la cola y recuperamos elementos del otro extremo.

Las aplicaciones de cola tienen todo tipo de usos, que se pueden inferir fácilmente de las colas del mundo real. No es difícil imaginar una representación de la cola de una fila de un supermercado o la cola para entrar en una sala de conciertos.

Implementación

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

  • New()
  • Enqueue()
  • Dequeue()
  • Front()
  • IsEmpty()
  • Size()

métodos.

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

Voy a crear unItemQueuetipo genérico, seguro para la concurrencia, que puede generar colas que contengan cualquier tipo utilizandogenny, para crear una implementación de cola de tipo específico, encapsulando la estructura de datos específica del valor real que contiene los datos.

// Package queue creates a ItemQueue data structure for the Item type
package queue

import (
“sync”


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

)


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


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


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


// Enqueue adds an Item to the end of the queue
func (s *ItemQueue) Enqueue(t Item) {
s.lock.Lock()
s.items = append(s.items, t)
s.lock.Unlock()
}


// Dequeue removes an Item from the start of the queue
func (s ItemQueue) Dequeue() Item {
s.lock.Lock()
item := s.items[0]
s.items = s.items[1:len(s.items)]
s.lock.Unlock()
return &item
}


// Front returns the item next in the queue, without removing it
func (s ItemQueue) Front() Item {
s.lock.RLock()
item := s.items[0]
s.lock.RUnlock()
return &item
}


// IsEmpty returns true if the queue is empty
func (s *ItemQueue) IsEmpty() bool {
return len(s.items) == 0
}


// Size returns the number of Items in the queue
func (s *ItemQueue) Size() int {
return len(s.items)
}

Pruebas

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

package queue

import (
“testing”
)


var s ItemQueue


func initQueue() *ItemQueue {
if s.items == nil {
s = ItemQueue{}
s.New()
}
return &s
}


func TestEnqueue(t *testing.T) {
s := initQueue()
s.Enqueue(1)
s.Enqueue(2)
s.Enqueue(3)


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

}


func TestDequeue(t *testing.T) {
s.Enqueue(1)
s.Enqueue(1)
s.Enqueue(1)
s.Dequeue()
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">Dequeue</span>()
<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Dequeue</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>)
}

<span style="color:#66d9ef">if</span> !<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">IsEmpty</span>() {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"IsEmpty should return true"</span>)
}

}

Crear una estructura de datos de cola concreta

Puede utilizar esta implementación genérica para generar colas de tipo específico, utilizando

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

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


Más tutoriales de go:


Tech Wiki en línea!