Traffyk – I’m driving crazy

Secondo capitolo della puntata algoritmi e strutture dati la coda.

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: Java, programmazione

Questo articolo è stato pubblicato il mercoledì, 3 ottobre 2007 alle 22:39 e classificato in Programming, School. È possibile seguire tutte le repliche a questo articolo tramite il feed RSS 2.0. Puoi lasciare un commento, oppure fare il trackback dal tuo sito.