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: