Esercizi su Queue
public interface Queue<E>
{
/**
* Restituisce il numero di elementi presenti nella coda.
* @return un int da 0 alla lunghezza max della coda.
*/
public int size();
/**
* Controlla se la coda è vuota.
* @return true, se la coda è vuota, false altrimenti.
*/
public boolean isEmpty();
/**
* Accede all'elemento sul front della coda.
* @return l'elemento al front della coda.
* @throws EmptyQueueException se invocato su una coda vuota.
*/
public E front() throws EmptyQueueException;
/**
* Inserisce un elemento nel rear della coda.
* @param element l'elemento da inserire.
*/
public void enqueue (E element);
/**
* Rimuove l'elemento sul front della coda.
* @return l'elemento rimosso.
* @throws EmptyQueueException se invocato su una coda vuota.
*/
public E dequeue()throws EmptyQueueException;
}
Implementare l’interfaccia Queue (scrivere la classe ArrayQueue) usando un array di lunghezza fissata public static final int CAPACITY = 1024;
Implementare Queue in modo che la coda piena invece della FullQueueException causa un aumento della taglia della coda
public class ArrayQueue<E> implements Queue<E>
{
public static final int CAPACITY = 1024;
private int f,r,capacity,size;
private E coda[];
public ArrayQueue()
{
this(CAPACITY);
}
public ArrayQueue(int cap)
{
capacity = cap;
f=r=size=0;
coda = (E[])new Object[capacity];
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return (f==r);
}
@Override
public E front() throws EmptyQueueException
{
if (isEmpty())
throw new EmptyQueueException("Coda Vuota!");
return coda[f];
}
@Override
public void enqueue(E element)
{
if (size == capacity-1)
{
E nuovaCoda[] = (E[])new Object[capacity*2];
for(int i=0; i<size; i++)
{
nuovaCoda[i]=coda[(f+i)%capacity];
}
f=0;
r=size;
capacity *=2;
coda = null;
coda = nuovaCoda;
nuovaCoda = null;
}
coda[r] = element;
r = (r+1)%capacity;
size++;
}
@Override
public E dequeue() throws EmptyQueueException
{
if (isEmpty())
throw new EmptyQueueException("Coda Vuota!");
E tmp = coda[f];
coda[f] = null;
f = (f+1)%capacity;
size--;
return tmp;
}
public String toString()
{
String response = "ArrayQueue Elements:[ ";
for (int i = 0; i<size; i++)
{
response += ((i+1)+"°"+coda[(f+i)% capacity]+" ");
}
response+= "] size:"+size()+" capacity: "+capacity;
return response;
}
public E extract(int k) throws NotEnoughElements
{
if (size() < k+1)
throw new NotEnoughElements("La Coda non contiene abbastanza elementi!");
return coda[(f+k)%capacity];
}
}
Scrivere un programma che testi la vostra implementazione di Queue invocandone tutti i metodi
public class ArrayQueueTest
{
public static void main(String[] args)
{
ArrayQueue<String> coda = new ArrayQueue<String>(2);
//QueueWithDeque<String> coda = new QueueWithDeque<String>();
//LinkedQueue<String> coda = new LinkedQueue<String>();
coda.enqueue("Marco");
System.out.println(coda);
coda.enqueue("Rosaria");
System.out.println(coda);
coda.enqueue("Francesco");
System.out.println(coda);
coda.enqueue("Pippo");
System.out.println(coda);
coda.dequeue();
System.out.println(coda);
coda.enqueue("Giuseppe");
System.out.println(coda);
System.out.println("Front: "+coda.front());
//System.out.println("3° elem dal front: "+coda.extract(3));
coda.dequeue();
System.out.println(coda);
coda.dequeue();
System.out.println(coda);
coda.dequeue();
System.out.println(coda);
coda.dequeue();
System.out.println(coda);
}
}
Esercizi su Deque
public interface Deque<E>
{
/**
* Restituisce il numero di elementi contenuti.
* @return un valore intero >= 0
*/
public int size();
/**
* Verifica se il deque è vuoto.
* @return true se è vuoto, false altrimenti.
*/
public boolean isEmpty();
/**
* Restituisce il primo elemento del Deque.
* @throws EmptyDequeException se invocato su Deque vuoto.
*/
public E getFirst() throws EmptyDequeException;
/**
* Restituisce l'ultimo elemento del Deque.
* @throws EmptyDequeException se invocato su Deque vuoto.
*/
public E getLast() throws EmptyDequeException;
/**
* Aggiunge un nuovo elemento all'inizio del Deque.
* @param element il nuovo elemento da inserire.
*/
public void addFirst (E element);
/**
* Aggiunge un nuovo elemento alla fine del Deque.
* @param element il nuovo elemento da inserire.
*/
public void addLast (E element);
/**
* Rimuove e restituisce il primo elemento del Deque.
* @throws EmptyDequeException se invocato su Deque vuoto.
*/
public E removeFirst() throws EmptyDequeException;
/**
* Rimuove e restituisce l'ultimo elemento del Deque.
* @throws EmptyDequeException se invocato su Deque vuoto.
*/
public E removeLast() throws EmptyDequeException;
}
Per implementare il TDA Deque usiamo una lista doppiamente concatenata
public class DLNode<E>
{
private E element;
private DLNode<E> prev, next;
public DLNode()
{
this(null,null,null);
}
public DLNode(E e, DLNode<E> p, DLNode<E> n)
{
element = e;
prev = p;
next = n;
}
//metodi accessori
public E getElement()
{
return element;
}
public DLNode<E> getPrev()
{
return prev;
}
public DLNode<E> getNext()
{
return next;
}
//metodi modificatori
public void setElement(E e)
{
element = e;
}
public void setPrev(DLNode<E> p)
{
prev = p;
}
public void setNext(DLNode<E> n)
{
next = n;
}
}
Implementare il TDA Deque (class MyDeque) con lista doppiamente concatenata
public class MyDeque<E> implements Deque<E>
{
private int size;
private DLNode<E> header, trailer;
public MyDeque()
{
header = new DLNode<E>();
trailer = new DLNode<E>();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
}
@Override
public int size()
{
return size;
}
@Override
public boolean isEmpty()
{
return (size == 0);
}
@Override
public E getFirst() throws EmptyDequeException
{
if (isEmpty())
throw new EmptyDequeException("Deck Vuoto!");
return header.getNext().getElement();
}
@Override
public E getLast() throws EmptyDequeException
{
if (isEmpty())
throw new EmptyDequeException("Deck Vuoto!");
return trailer.getPrev().getElement();
}
@Override
public void addFirst(E element)
{
DLNode<E> newNode = new DLNode<E>(element,header,header.getNext());
header.getNext().setPrev(newNode);
header.setNext(newNode);
size++;
}
@Override
public void addLast(E element)
{
DLNode<E> newNode = new DLNode<E>(element,trailer.getPrev(),trailer);
trailer.getPrev().setNext(newNode);
trailer.setPrev(newNode);
size++;
}
@Override
public E removeFirst() throws EmptyDequeException
{
if (isEmpty())
throw new EmptyDequeException("Deck Vuoto! - Rimozione primo elem Impossibile");
E tmp = header.getNext().getElement();
header.setNext(header.getNext().getNext());
header.getNext().setPrev(header);
size--;
return tmp;
}
@Override
public E removeLast() throws EmptyDequeException
{
if (isEmpty())
throw new EmptyDequeException("Deck Vuoto! - Rimozione ultimo elem Impossibile");
E tmp = trailer.getPrev().getElement();
trailer.setPrev(trailer.getPrev().getPrev());
trailer.getPrev().setNext(trailer);
size--;
return tmp;
}
public String toString()
{
String risp = "Deque Elements: [ ";
DLNode<E> nodo = header.getNext();
for (int i=0; i<size; i++ )
{
risp+= (i+1)+"°"+nodo.getElement() + " ";
nodo = nodo.getNext();
}
risp+= "] size: "+size;
return risp;
}
}
Usare Deque per implementare Stack e Queue
public class StackWithDeque<E> implements Stack<E>
{
private MyDeque<E> contenitore;
public StackWithDeque()
{
contenitore = new MyDeque<E>();
}
@Override
public boolean isEmpty()
{
return contenitore.isEmpty();
}
@Override
public E top() throws EmptyStackException
{
E tmp = null;
try
{
tmp = contenitore.getLast();
}
catch (EmptyDequeException e)
{
throw new EmptyStackException();
}
return tmp;
}
@Override
public E pop() throws EmptyStackException
{
E tmp = null;
try
{
tmp = contenitore.removeLast();
}
catch (EmptyDequeException e)
{
throw new EmptyStackException();
}
return tmp;
}
@Override
public void push(E o) throws FullStackException
{
contenitore.addLast(o);
}
@Override
public int size()
{
return contenitore.size();
}
public String toString()
{
return(contenitore.toString());
}
}
public class QueueWithDeque<E> implements Queue<E>
{
private MyDeque<E> contenitore;
public QueueWithDeque()
{
contenitore = new MyDeque<E>();
}
@Override
public int size()
{
return contenitore.size();
}
@Override
public boolean isEmpty()
{
return contenitore.isEmpty();
}
@Override
public E front() throws EmptyQueueException
{
E tmp = null;
try
{
tmp = contenitore.getFirst();
}
catch(EmptyDequeException e)
{
throw new EmptyQueueException();
}
return tmp;
}
@Override
public void enqueue(E element)
{
contenitore.addLast(element);
}
@Override
public E dequeue() throws EmptyQueueException
{
E tmp = null;
try
{
tmp = contenitore.removeFirst();
}
catch(EmptyDequeException e)
{
throw new EmptyQueueException();
}
return tmp;
}
public String toString()
{
return "Queue with "+contenitore.toString();
}
}
Implementareilconcettodilistaconcatenatacome classe Java LinkedList
public class Node<E>
{
private E element;
private Node<E> next;
public Node()
{
this(null,null);
}
public Node(E e, Node<E> n)
{
element = e;
next = n;
}
public E getElement()
{
return element;
}
public Node<E> getNext()
{
return next;
}
public void setElement(E e)
{
element = e;
}
public void setNext(Node<E> n)
{
next = n;
}
}
public class LinkedList<E>
{
private Node<E> head, tail;
private int size;
public LinkedList()
{
tail = new Node<E>();
head = tail;
size = 0;
}
/**
* Restituisce il numero di elementi contenuti nella lista.
* @return un valore intero >= 0
*/
public int size()
{
return size;
}
/**
* Verifica se la lista è vuota.
* @return true se è vuota, false altrimenti.
*/
public boolean isEmpty()
{
return (size == 0);
}
/**
* Aggiunge un nuovo elemento all'inizio della lista.
* @param e il nuovo elemento da inserire.
*/
public void addFirst(E e)
{
if (size == 0)
head.setElement(e);
else
{
Node<E> newNode = new Node<E>(e,head);
head = newNode;
}
size++;
}
/**
* Aggiunge un nuovo elemento alla fine della lista.
* @param e il nuovo elemento da inserire.
*/
public void addLast(E e)
{
if (size == 0)
tail.setElement(e);
else
{
Node<E> newNode = new Node<E>(e,null);
tail.setNext(newNode);
tail = newNode;
}
size++;
}
/**
* Rimuove e restituisce il primo elemento dalla lista.
* @throws EmptyLinkedListException se invocato sulla lista vuota.
*/
public E removeFirst() throws EmptyLinkedListException
{
if (isEmpty())
throw new EmptyLinkedListException("Lista Vuota!");
E tmp = null;
if (size == 1)
{
tmp = head.getElement();
head.setElement(null);
}
else
{
tmp = head.getElement();
head = head.getNext();
}
size--;
return tmp;
}
/**
* Rimuove e restituisce l'ultimo elemento della lista.
* @throws EmptyLinkedListException se invocato su lista vuota.
*/
public E removeLast() throws EmptyLinkedListException
{
if (isEmpty())
throw new EmptyLinkedListException();
E tmp = null;
if(size == 1)
{
tmp = tail.getElement();
tail.setElement(null);
size--;
}
else
{
Node<E> nodo = head;
for(int i=0; i<size-1; i++)
{
if (nodo.getNext().getNext() == null)
{
tmp = nodo.getNext().getElement();
nodo.setNext(null);
tail = nodo;
size--;
}
else
{
nodo = nodo.getNext();
}
}
}
return tmp;
}
/**
* Restituisce il primo elemento della lista.
* @throws EmptyLinkedListException se invocato su lista vuota.
*/
public E getFirst() throws EmptyLinkedListException
{
if (isEmpty())
throw new EmptyLinkedListException();
return head.getElement();
}
/**
* Restituisce l'ultimo elemento della lista.
* @throws EmptyLinkedListException se invocato su lista vuota.
*/
public E getLast() throws EmptyLinkedListException
{
if (isEmpty())
throw new EmptyLinkedListException("Lista Vuota!");
return tail.getElement();
}
public String toString()
{
String stringa = "LinkedList Elements: [ ";
Node<E> nodo = head;
for(int i=0; i<size; i++)
{
stringa += nodo.getElement()+" ";
nodo = nodo.getNext();
}
stringa += "] size: "+size;
return stringa;
}
}
ImplementareilTDAStackconlistaconcatenata
Definire classe LinkedStack
public class LinkedStack<E> implements Stack<E>
{
private LinkedList<E> contenitore;
public LinkedStack()
{
contenitore = new LinkedList<E>();
}
@Override
public boolean isEmpty()
{
return contenitore.isEmpty();
}
@Override
public E top() throws EmptyStackException
{
E tmp = null;
try
{
tmp = contenitore.getLast();
}
catch (EmptyLinkedListException e)
{
throw new EmptyStackException();
}
return tmp;
}
@Override
public E pop() throws EmptyStackException
{
E tmp = null;
try
{
tmp = contenitore.removeLast();
}
catch (EmptyLinkedListException e)
{
throw new EmptyStackException();
}
return tmp;
}
@Override
public void push(E o) throws FullStackException
{
contenitore.addLast(o);
}
@Override
public int size()
{
return contenitore.size();
}
public String toString()
{
return contenitore.toString();
}
}
ImplementareilTDAQueueconlistaconcatenata
Definire classe LinkedQueue
public class LinkedQueue<E> implements Queue<E>
{
private LinkedList<E> contenitore;
public LinkedQueue()
{
contenitore = new LinkedList<E>();
}
@Override
public int size() {
return contenitore.size();
}
@Override
public boolean isEmpty() {
return contenitore.isEmpty();
}
@Override
public E front() throws EmptyQueueException
{
E tmp = null;
try
{
tmp = contenitore.getFirst();
}
catch(EmptyLinkedListException e)
{
throw new EmptyQueueException();
}
return tmp;
}
@Override
public void enqueue(E element) {
contenitore.addLast(element);
}
@Override
public E dequeue() throws EmptyQueueException
{
E tmp = null;
try
{
tmp = contenitore.removeFirst();
}
catch(EmptyLinkedListException e)
{
throw new EmptyQueueException();
}
return tmp;
}
public String toString()
{
return "QUEUE with "+contenitore.toString();
}
}
ImplementareilTDADequeconlisteconcatenate
public class LinkedDeque<E> implements Deque<E>
{
private LinkedList<E> lista;
@Override
public int size() {
return lista.size();
}
@Override
public boolean isEmpty() {
return lista.isEmpty();
}
@Override
public E getFirst() throws EmptyDequeException {
E tmp = null;
try
{
tmp = lista.getFirst();
}
catch (EmptyLinkedListException e)
{
throw new EmptyDequeException();
}
return tmp;
}
@Override
public E getLast() throws EmptyDequeException {
E tmp = null;
try
{
tmp = lista.getLast();
}
catch (EmptyLinkedListException e)
{
throw new EmptyDequeException();
}
return tmp; }
@Override
public void addFirst(E element) {
lista.addFirst(element);
}
@Override
public void addLast(E element) {
lista.addLast(element);
}
@Override
public E removeFirst() throws EmptyDequeException {
E tmp = null;
try
{
tmp = lista.removeFirst();
}
catch (EmptyLinkedListException e)
{
throw new EmptyDequeException();
}
return tmp;
}
@Override
public E removeLast() throws EmptyDequeException
{
E tmp = null;
try
{
tmp = lista.removeLast();
}
catch (EmptyLinkedListException e)
{
throw new EmptyDequeException();
}
return tmp;
}
}
Continua...
Post
