/**
* Interface décrivant des piles LIFO simples.
*/
public interface Stack {
/**
* Retourne vrai si la pile est vide, faux sinon.
*/
public boolean isEmpty();
/**
* Ajoute l'objet o au sommet de la pile.
*/
public void push(Object o);
/**
* Retire l'objet au sommet de la pile et le retourne.
*/
public Object pop();
}
La classe ArrayStack doit fournir une définition pour toutes les méthodes déclarées par l'interface Stack qu'elle implémente. De plus, elle doit permettre de créer une pile. Nous avons choisi dans un premier temps de ne pas se soucier du problème de la taille du tableau qui stocke les éléments de la pile. Lorsque le tableau est plein, l'accès en dehors de ses indices fera lever une exception qui sera propagée. Nous verons bientôt comment gérer ces problèmes.
public class ArrayStack implements Stack {
protected Object[] tab;
private int index;
/**
* Construit une pile de capacité donnée initialement vide.
*/
public ArrayStack(int capacity) {
tab = new Object[capacity];
index = -1;
}
/**
* Retourne vrai si la pile est vide, faux sinon.
*/
public boolean isEmpty() {
return index < 0;
}
/**
* Ajoute l'objet o au sommet de la pile.
*/
public void push(Object o) {
tab[++index] = o;
}
/**
* Retire l'objet au sommet de la pile et le retourne.
*/
public Object pop() {
return tab[index--];
}
public static void main(String[] args) {
Stack s = new ArrayStack(5);
s.push("a");
s.push("b");
s.push("c");
s.push("d");
System.out.println(s.pop());
s.push("d");
s.push("e");
// s.push("f"); // lève une ArrayIndexOutOfBoundsException
}
}
Rien d'extra-ordinaire: c'est encore plus simple avec un Vector.
import java.util.Vector;
public class VectorStack implements Stack {
protected Vector v;
/**
* Construit une pile par défaut. Aucune capacité initiale, aucune limite
* au nombre d'éléments stockables n'est requise.
*/
public VectorStack() {
v = new Vector();
}
/**
* Retourne vrai si la pile est vide, faux sinon.
*/
public boolean isEmpty() {
return v.isEmpty();
}
/**
* Ajoute l'objet o au sommet de la pile.
*/
public void push(Object o) {
// par défaut, l'ajout dans un vecteur se fait à la fin
v.add(o);
}
/**
* Retire l'objet au sommet de la pile et le retourne.
*/
public Object pop() {
// pour retirer le dernier inséré, il faut accéder à la fin du vecteur
return v.remove(v.size()-1);
}
public static void main(String[] args) {
Stack s = new VectorStack();
s.push("a");
s.push("b");
s.push("c");
s.push("d");
System.out.println(s.pop());
s.push("d");
s.push("e");
s.push("f");
}
}
LA première chose que l'on puisse faire, c'est d'étendre l'interface Stack de sorte à ce qu'elle déclare la nouvelle fonctionnalité.
/**
* Interface étendue de Stack, qui fournit en plus la méthode pushAll.
*/
public interface StackableStack extends Stack {
/**
* Empile dans la pile courante tous les éléments de la pile s.
*/
public void pushAll(Stack s);
}
Ensuite, une manière de réutiliser les codes déjà écrits de ArrayStack et de VectorStack consiste à en hériter et à "ajouter" la nouvelle méthode pour pouvoir implémenter StackableStack. Noter ici que l'on utilise dans ArrayStackableStack la variable tab déclarée dans ArrayStack. C'est pour cela que cette dernière à été déclarée protégée (protected) dans ArrayStack.
public class ArrayStackableStack extends ArrayStack implements StackableStack {
/**
* Construit une pile empilable de capacité donnée initialement vide.
*/
public ArrayStackableStack(int capacity) {
super(capacity);
}
/**
* Empile dans la pile courante tous les éléments de la pile s.
*/
public void pushAll(Stack s) {
// Attention au sens dans lequel les éléments doivent être empilés.
Stack temp = new ArrayStack(tab.length); // Création de pile intermédiaire
while(!(s.isEmpty())) {
temp.push(s.pop()); // Dépiler s
}
while(!(temp.isEmpty())) { // Ré-empiler dans this
push(temp.pop());
}
}
public static void main(String[] args) {
Stack s = new ArrayStack(5);
s.push("d");
s.push("e");
s.push("f");
StackableStack ss = new ArrayStackableStack(10);
ss.push("a");
ss.push("b");
ss.push("c");
ss.pushAll(s);
ss.push("g");
for(;!ss.isEmpty();) {
System.out.println(ss.pop());
}
}
}
Même chose pour la variable v déclarée protected dans VectorStack pour être utilisée dans VectorStackableStack.
public class VectorStackableStack extends VectorStack implements StackableStack {
/**
* Empile dans la pile courante tous les éléments de la pile s.
*/
public void pushAll(Stack s) {
Stack temp = new VectorStack();
while(!(s.isEmpty())) {
temp.push(s.pop()); // Dépiler s
}
while(!(temp.isEmpty())) { // Ré-empiler dans this
push(temp.pop());
}
}
public static void main(String[] args) {
Stack s = new VectorStack();
s.push("d");
s.push("e");
s.push("f");
StackableStack ss = new VectorStackableStack();
ss.push("a");
ss.push("b");
ss.push("c");
ss.pushAll(s);
ss.push("g");
for(;!ss.isEmpty();) {
System.out.println(ss.pop());
}
}
}
On peut alors se rendre compte que le code pour les deux méthodes est quasiment identique. Il pourrait être factorisé entre les deux classes en le plaçant, par exemple, dans une classe abstraite.
/**
* Classe abstraite implémentant la méthode pushAll de
* StackableStack. Cette classe est abstraite car elle ne fournit pas
* les implémentations des autres méthodes (celles de Stack).
*/
public abstract class AbstractStackableStack implements StackableStack {
/**
* Empile dans la pile courante tous les éléments de la pile s.
*/
public void pushAll(Stack s) {
// Un appel récursif "non terminal" permet de remettre les élémnts
// dans l'ordre (c'est la pile des appels récursifs qui joue le rôle
// de la pile temporaire).
while(!s.isEmpty()) {
Object o = s.pop();
pushAll(s);
push(o);
}
}
Le problème est alors de récupérer les codes des classes ArrayStack et de VectorStack. Une classe ne pouvant pas hériter de plus d'une classe, on est un peu coincé (on aimerait par exemple que ArrayStackableStack puis être définit simplement par héritage de ArrayStack et de AbstractStackableStack, mais c'est impossible).
Il existe une solution, sur laquelle nous reviendrons, qui permet de s'en sortir grâce à de la délégation. La classe DefaultStackableStack ci-dessous délègue toutes ses actions relatives aux piles à la pile qu'elle contient, qui lui est passée en argument lors de la construction (quelle que soit l'implémentation de cette pile). Comme cette classe hérite de AbstractStackableStack, elle en hérite la méthode pushAll.
/**
* Par héritage de AbstractStackableStack, cette classe implémente les
* interfaces StackableStack et donc Stack.
*/
public class DefaultStackableStack extends AbstractStackableStack {
Stack s;
public DefaultStackableStack(Stack s) {
this.s = s;
}
public boolean isEmpty() {
return s.isEmpty();
}
public void push(Object o) {
s.push(o);
}
public Object pop() {
return s.pop();
}
public static void main(String[] args) {
Stack s1 = new ArrayStack(10);
s1.push("a");
s1.push("b");
s1.push("c");
Stack s2 = new VectorStack();
s2.push("d");
s2.push("e");
s2.push("f");
StackableStack ss = new DefaultStackableStack(s1);
ss.pushAll(s2);
ss.push("g"); // équivalent de s1.push("g");
for(;!ss.isEmpty();) {
System.out.println(ss.pop());
}
}
}