Pile - Liste chaînée

Version imprimable

Bonjour,
je me retrouve bloqué face à une méthode pourtant simple sur le papier.

Le but est de réaliser une pile d'objets en utilisant une liste chaînée. Voici l'interface :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
public interface PileI {
 
    public final static int CAPACITE_PAR_DEFAUT = 6;
 
    public void empiler(Object o) throws PilePleineException;
    public Object depiler() throws PileVideException;
 
    public Object sommet() throws PileVideException;
    public int capacite();
    public int taille();
    public boolean estVide();
    public boolean estPleine();
 
    public boolean equals(Object o);
    public int hashCode();
    public String toString();
}

Pour la liste chaînée, c'est sur la méthode estPleine() que je bloque.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
public class PileListe implements PileI, Cloneable {
	/** la liste des Maillons/Elements */
	private Maillon stk;
	/** la capacité de la pile */
	private int capacite;
	/** le nombre */
	private int nombre;
 
	/**
         * Classe interne "statique" contenant chaque élément de la chaine
         */
	private static class Maillon implements Cloneable {
		private Object element;
		private Maillon suivant;
 
		public Maillon(Object element, Maillon suivant) {
			this.element = element;
			this.suivant = suivant;
		}
 
		public Maillon suivant() {
			return this.suivant;
		}
 
		public Object element() {
			return this.element;
		}
 
		public Object clone() throws CloneNotSupportedException {
			Maillon m = (Maillon) super.clone();
			m.element = element;
			return m;
		}
	}
 
// code constructeur etc
 
public boolean estPleine() {
		return false ; // TODO
	}

Merci pour toute aide

04/10/2013, 11h15
Noctis

Pour ta methode estPleine(), je pense qu'il te suffit de comparer la taille de la liste avec ta constante CAPACITE_PAR_DEFAUT .
Si taille() >= CAPACITE_PAR_DEFAUT return true
sinon return false
04/10/2013, 11h48
Nico02

Salut,

Sinon tu peux aussi garder un int comme compteur dans ta structure de pile. Ça te permet d'avoir à tout moment la taille sans avoir a tout recalculer, et ainsi tu peux tester sa valeur pour savoir si tu as atteint la capacité max de ta pile.
04/10/2013, 12h01
Ceddoc

Citation:

Envoyé par Noctis

Pour ta methode estPleine(), je pense qu'il te suffit de comparer la taille de la liste avec ta constante CAPACITE_PAR_DEFAUT .
Si taille() >= CAPACITE_PAR_DEFAUT return true
sinon return false

Pourquoi prendre la capacité par défaut vu qu'il a capacite()?

J'ai procédé comme suit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
//....
   //constructeur
    public PileListe(int taille) {
		if (taille <= 0)
			taille = CAPACITE_PAR_DEFAUT;
		this.stk = null;
		this.capacite = taille;
	}
 
        //constsructeur par defaut
	public PileListe() {
		this(PileI.CAPACITE_PAR_DEFAUT);
	}
 
       public void empiler(Object o) throws PilePleineException {
		if (estPleine())
			throw new PilePleineException();
		stk = new Maillon (o,stk);
		nombre = nombre + 1 ;
		}
 
 
      // ....
 
 
      public int taille() {
		return nombre;
	}
 
       public boolean estVide() {
		return stk == null ;
	}
 
      public boolean estPleine() {
		return this.taille() >= capacite ; 
	}
 
  //...
 
   }

04/10/2013, 15h30
plawyx

juste une petite question: c'est un TP pour étudiant ?

Car sinon, une collection de type Queue (ou Dequeue) a toutes les fonctionnalités que tu souhaites.
07/10/2013, 14h03
Noctis

Citation:

Envoyé par Ceddoc

Pourquoi prendre la capacité par défaut vu qu'il a capacite()?

Oups j'avais pas cette méthode donc en effet, il serait mieu d'appeller celle-ci :)

Citation:

Envoyé par plawyx

juste une petite question: c'est un TP pour étudiant ?

Car sinon, une collection de type Queue (ou Dequeue) a toutes les fonctionnalités que tu souhaites.

Oui c'est un TP avec contraintes "forcées".

Je suis un peu coincé sur une dernière méthode pour cette classe. La méthode toString me gêne un peu car j'aimerais pouvoir avoir quelque chose de la forme "[4, 3, 2, 1]", donc pouvoir remonter la pile "à rebrousse-poil" si on a empilé 1 puis 2 puis 3 puis 4.

J'ai commencé à faire une Stack temporaire pour pouvoir stocker le sommet de la pile, puis dépiler et à la fin reconstruire, mais je n'y parviens pas.

Je redonne le code de la classe au quasi complet pour plus de clarté.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
public class PileListe implements PileI, Cloneable {
 
    private Maillon stk;
 
    private int capacite;
 
    private int nombre;
 
       private static class Maillon implements Cloneable {
        private Object element;
        private Maillon suivant;
 
        public Maillon(Object element, Maillon suivant) {
            this.element = element;
            this.suivant = suivant;
        }
 
        public Maillon suivant() {
            return this.suivant;
        }
 
        public Object element() {
            return this.element;
        }
 
        public Object clone() throws CloneNotSupportedException {
            Maillon m = (Maillon) super.clone();
            m.element = element;
            return m;
        }
    }
 
 
    public PileListe(int taille) {
        if (taille <= 0)
            taille = CAPACITE_PAR_DEFAUT;
        this.stk = null;
        this.capacite = taille;
    }
 
    public PileListe() {
        this(PileI.CAPACITE_PAR_DEFAUT);
    }
 
    public void empiler(Object o) throws PilePleineException {
        if (estPleine())
            throw new PilePleineException();
        stk = new Maillon (o,stk);
        nombre = nombre + 1 ;
        }
 
    public Object depiler() throws PileVideException {
        if (estVide())
            throw new PileVideException();
        if (stk != null) {
          Object o = stk.element();
          stk = stk.suivant();
          return o;
          }
          else return null;
 
    }
 
    public Object sommet() throws PileVideException {
        if (estVide())
            throw new PileVideException();
        return stk.element ; 
    }
 
     public boolean estVide() {
        return stk == null ;
    }
 
    public boolean estPleine() {
        return this.taille() >= capacite ; 
    }
 
      // ici je coince un peu
        public String toString() {
 
        String s = "[";
         Stack temp = new Stack();
       while (!this.estVide()) {
             temp.push(stk.element);
              s = s + stk.element;
            }
        return s + "]";
    }
 
    //...
 
    public int capacite() {
        return this.capacite;
    }
 
   //...
    public int taille() {
        return nombre;
    }
}

Merci d'avance

08/10/2013, 15h43
thelvin

Hum. Ce "Stack" ne me semble pas une bonne idée.
La solution la plus simple que je vois, c'est une approche récursive.

Vu qu'on est en section "débutant" je vais en dire plus :

- tu devrais définir une méthode private String buildString(Maillon maillon) qui prend, donc, un Maillon en paramètre.
Et elle renvoie une String qui montre tous les éléments dans l'ordre où ce maillon et ses suivants ont été empilés.
- je rappelle que cette méthode buildString() a le droit de s'appeler elle-même...