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! 😉

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

  1. @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 😉

  2. 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 🙂

  3. 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 😛

  4. Ehhh…quanti ricordi… sono curioso di leggere i post sugli “alberi”, “red-black”, e compagnia bella 😉
    Li farai vero? 🙂

I commenti sono chiusi.