Massimo Caliman
Massimo Caliman
1 min read

Categories

  • Data Structures

Tags

  • Java
  • Code o Queue
  • Strutture Dati

Languages

  • Italian

Riprendiamo la trattazione delle strutture dati elementari. Nei post precedenti abbiamo visto le strutture indicizzate,quelle collegate e le Pile o Stack,uno altro dei tipo base più ricorrenti è la Coda o Queue, una specifica in pseudolinguaggio è riportata sotto.

tipo Coda
dati
una sequenza S di n elementi
operazioni
isEmpty()->result, restituisce true se S è vuota, false altrimenti
enqueue(elem e), aggiunge e come ultimo elemento di S
dequeue()->elem, toglie da S il primo elemento e lo restituisce
first()->elem, restituisce il primo elemento di S (senza toglierlo da S)

Una naturale implementazione in Java della specifica è fornita da un interfaccia come quella seguente

public interface Coda<E> {
    public boolean isEmpty();
    public void enqueue(E e);
    public E dequeue();
    public E first();
}

Anche in questo caso possiamo realizzare un implementazione in vari modi, sia utilizzando strutture indicizzate che collegate.

Come per il gli Stack la via più naturale e veloce è quella di utilizzare le classi concrete derivanti dall’interfaccia Java Deque. Anche in questo caso possiamo utilizzare i metodi di Deque relativi al suo comportamento come Queue.

addLast(e)
offerLast(e)
removeFirst()
pollFirst()
getFirst()
peekFirst()

Un classe wrapper che renda più facile l’utilizzo è la seguente (utilizza LinkedList in luogo di ArrayDeque)

public class QueueImpl<E> {

    private LinkedList<E> list = new LinkedList<>();

    public void enqueue(E item) {
        list.addLast(item);
    }
    public E dequeue() {
        return list.poll();
    }
    public boolean isEmpty() {
        return !list.isEmpty();
    }
    public int size() {
        return list.size();
    }
}