Uno dei tipo base più ricorrente è la Pila o Stack, una specifica in pseudolinguaggio è riportata sotto.
tipo: Pila
dati: una sequenza S di n elementi
operazioni
isEmpty() -> result , result=true sse S=O, false altrimenti
push(elem e) aggiunge e come ultimo elemento di S
pop()-> elem , toglie da S l’ultimo elemento e lo restituisce
top()->elem restituisce l’ultimo elemento di S (senza toglierlo da S)In Java potremmo rendere la specifica come un interfaccia
public interface Pila<E> {
public boolean isEmpty();
public void push(E e);
public E pop();
public E top();
}L’uso dei generics mi permette di non definire l’interfaccia per un tipo specifico.
Anche in questo caso possiamo realizzare un implementazione in vari modi, sia utilizzando strutture indicizzate che collegate..
Il JDK fornisce comunque un implementazione di tutto rispetto sia per risolvere il problema degli Stack che delle Queue e lo fa con un unica interfaccia Deque<E> da cui derivano le classi concrete ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList
Deque definisce metodi sia per realizzare uno Stack che una Queue, vi rimando al javadoc per una trattazione più esauriente e mi limito a riportarne la lista.
- Per il metodo
push(e)abbiamoaddFirst(e) - Per il
pop()abbiamoremoveFirst() - Per il
peek()otop()invecepeekFirst()
Deque<E> implementa l’interfaccia Queue<E> , interfaccia implementata anche dalle classi
AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue,SynchronousQueue.
La via più facile è utilizzare la vecchia classe Stack di java.util, ma non ne avremo grandi vantaggi, deriva dalla classe Vector ed è disponibile dalla versione 1.0 del JDK
Stack<Integer> lifo = new Stack<>();
for (int i = 1; i <= 10; i++) {
lifo.push(i);
}
while (!lifo.isEmpty()) {
System.out.print(lifo.pop());
System.out.print(',');
}La classe consigliata è ArrayDeque<E> un semplice caso d’uso è il seguente
Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(1);
Integer value = stack.pop();
boolean isEmpty = stack.isEmpty();
value = stack.peek();