Tipi di dati astratti: la coda (queue) e algoritmo in Java 5.0

Secondo capitolo della puntata algoritmi e strutture dati la coda.

coda-queue

Un coda una struttura dati molto semplice, segue il principio FIFO, First In First Out, il primo ad entrare il primo ad uscire.. o potremmo dire chi primo arriva meglio alloggia!:P

Oggi non posso spiegarvi tutto, come sempre confido nei vostri commenti e richieste di informazioni specifiche per contribuire al meglio al post. Vediamo subito quali metodi ha l’interfaccia Queue:

  • enqueue(e): accoda l’elemento e alla coda, in pratica posiziona dietro l’elemento;
  • dequeue(): prende il primo elemento della coda, ovvero il primo ad essere entrato, lancia un’eccezione se vuota;
  • front(): simile al pop dello stack, legge il primo elemento della coda senza per toglierlo da essa, lancia un’eccezione se vuota;
  • size(): un classico ormai, restituisce la dimensione;
  • isEmpty(): booleano per sapere se la coda vuota o occupata da elementi.

Vediamo quindi l’interfaccia:

package queue;

import exception.EmptyQueueException;

public interface Queue<E> {

 public int size();
 public boolean isEmpty();
 public E front() throws EmptyQueueException;
 public void enqueue(E element);
 public E dequeue()throws EmptyQueueException;
}

Questa la classe della nuova eccezione che abbiamo creato:

package exception;

public class EmptyQueueException extends RuntimeException{
 /**
  *
  */
 private static final long serialVersionUID = -6005613600247835251L;


 public EmptyQueueException(String errore) {
  super(errore);
 }

}

Classe ArrayQueue per implementare l’interfaccia con un array:

package queue;


import exception.EmptyQueueException;
import exception.FullQueueException;


public class ArrayQueue<E> implements Queue<E>{
 protected int capacity;
 public static final int CAPACITY = 1000;
 protected E[] Q;
 protected int f, r = 0;
 
 public ArrayQueue() {
  this(CAPACITY);
 }
 @SuppressWarnings("unchecked")
 public ArrayQueue(int capacity) {
  this.capacity=capacity;
  Q = (E[]) new Object[capacity];
 }
 public boolean isEmpty() {
  return (f==r);
 }
 public E dequeue() throws EmptyQueueException {
  if (isEmpty())
   throw new EmptyQueueException("Queue is empty");
  E element;
  element = Q[f];
  Q[f] = null;
  f = (f+1) % Q.length;
  return element;
 }
 public void enqueue(E element) throws FullQueueException{
  if (size() == Q.length-1)
   throw new FullQueueException("Queue is full");
  Q[r] = element;
  r = (r+1) % Q.length;
 }
 public int size() {
  return ((Q.length-f+r) % Q.length);
 }
 public E front() throws EmptyQueueException {
  if (isEmpty()) throw new EmptyQueueException("Queue is empty");
  return Q[f];
 }

}

Classe dell’altra eccezione:

package exception;

public class FullQueueException extends RuntimeException{
 /**
  *
  */
 private static final long serialVersionUID = -6005613600247835251L;


 public FullQueueException(String errore) {
  super(errore);
 }

}

E infine la classe di test:

package queue;


public class TestArrayQueue {
	public static void main(String[] args) {
		Queue A = new ArrayQueue();
		A.enqueue(5);
		System.out.println("Enqueue 5");
		A.enqueue(3);
		System.out.println("Enqueue 3");
		System.out.println("Dequeue "+A.dequeue());
		A.enqueue(7);
		System.out.println("Enqueue 7");
		System.out.println("Dequeue "+A.dequeue());
		System.out.println("Front "+A.front());
		System.out.println("Dequeue "+A.dequeue());
		if (!A.isEmpty()) A.dequeue();
		A.enqueue(9);
		System.out.println("Enqueue 9");
		A.enqueue(7);
		System.out.println("Enqueue 7");
		System.out.println("Size :"+A.size());
		A.enqueue(3);
		System.out.println("Enqueue 3");
		A.enqueue(5);
		System.out.println("Enqueue 5");
		System.out.println("Dequeue "+A.dequeue());

	}
}

Buonanotte rag! πŸ˜‰

Tag: ,

5 Commenti a “Tipi di dati astratti: la coda (queue) e algoritmo in Java 5.0”

  1. eyeonweb ha detto:

    Ehhh…quanti ricordi… sono curioso di leggere i post sugli “alberi”, “red-black”, e compagnia bella πŸ˜‰
    Li farai vero? πŸ™‚

  2. Traffyk ha detto:

    MMM non penso siano in programma questi qui, faremo tabelle hash, heap e altra roba, gli alberi sono stati fatti in Linguaggi di programmazione 1 (linguaggio c) ma soltanto accennati, forse verr trattato in algoritmi e strutture dati(in pratica il vecchio corso si pu dire) ma se ricordo bene al corso di laboratorio nada. Giusto una parte teorica pallosissima sui grafi e gli algoritmi di visita con creazione di alberi per tenere traccia dei vertici adiacenti e figli.. (oggi stato spiegato il breadht first search πŸ˜‰ ).

    Comunque non avendo il tempo di spiegare molto gli algoritmi non so se continuer questa rubrica perch pubblicare solo gli algoritmi per poi farli copiare onestamente non ha proprio senso πŸ˜‰ Mah poi si vedr πŸ˜›

  3. Alex2000 ha detto:

    io son qui che prendo appunti professore.
    grazie e buono studio.

  4. TheKaneB ha detto:

    eheheh, effettivamente un peccato non trattare gli alberi, sono una struttura secondo me “affascinante”! Cmq un giorno forse scriver delle dispense per i miei colleghi sugli algoritmi e le strutture basilari in Pascal e in C. Se e quando le scriver ovviamente troveranno spazio sul mio blog sotto Creative Commons πŸ™‚

  5. Traffyk ha detto:

    @Alex2000
    mi raccomando non ti addormentare sul banco πŸ˜‰ hihihi

    @TheKaneB
    Si in effetti hai ragione, ma come ho detto prima li abbiamo fatti in LP1 sommariamente nel linguaggio c, poi li ho studiati io a parte in Java sperando di prendere qualche voto in pi(vista la rovinosa prova che feci allo scritto) ma dopo un’ora e mezza che io ancora parlavo e praticamente dicevo per filo e per segno tutto il libro java mattone per mattone mi hanno fermato prima ancora di cominciare ad accennare le strutture dati, dissero che avevo detto gia troppo e 6 punti erano il massimo che avrei potuto avere visto il 18 dello scritto.. totale esame 24 (ma valla a implementare una schacchiera in java completamente funzionante in un’ora e 3 quarti… dai veramente da bastardi!).

    Riguardo ai tuoi appunti…sarebbero perfetti! Ps ricordati anche di mettere qualcosina di matematica eh πŸ˜‰

Lascia un Commento