Discussion :

[adrian07]

Salut à tous,
J'aimerais bien savoir la différence entre l'implémentation(pile et file) selon une liste chainée et selon un tableau???
et comment modéliser la tête et la queue de la file dans le formalisme tableau??? est ce que ce sont des indices dans le tableau ou quoi???
j'ai cherché sur le web et j'ai trouvé des réponses diffrentes, je me sens confu...
si quelqu'un peut me l'expliquer d'une manière simple, je serai reconnaissant.
merci d'avance à tous

[LittleWhite]

Bonjour,

J'ai envie de dire, pour les implémentations, on peut faire ce que l'on veut tant que cela marche ( enfin tant que l'on suit les principes de bases )

Maintenant pour l'inmplémentation de la tête de la pile, dans un tableau, ce tableau aura une structure suivante ( normalement )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
typedef struct Pile
{
     int* data;
     unsigned int capacite;
     unsigned int taille;
}Pile;

Data, ce sont les données utilisateur. ( le tableau en lui même )
Capacité, c'est la capacité du tableau
taille, c'est le nombre d'éléments du tableau

Taille est toujours plus petit que capacité.

Donc lorsque l'on veut la tête du tableau, il faut juste faire:

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Pile p;
p.data[taille]; // Nous donne la tete

Car taille doit toujours être incrémenté à l'ajout d'un nouveau élément.

[Pouet_forever]

L'avantage de la liste chaînée, c'est que tu as une taille dynamique.
Une pile LIFO (last in first out) se fait de manière à enlever toujours le dernier élément, et ajouter toujours à la fin.
En utilisant un tableau, tu vas être limité à la taille de ton tableau, tandis que la liste chaînée, à la mémoire qui est disponible.
Avec un tableau, il suffit d'avoir un indicateur que tu incrémentes ou décrémentes en fonction des opérations que tu fais.
Grossomodo avec un tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
int tab[100]; /* Pile limitée à 100 valeurs */
int p; /* Indice de ta pile */
 
/* initialisation */
p = 0;
 
/* Ajout */
tab[p++] = valeur_a_ajouter;
 
/* Suppression */
return tab[--p]

Avec une liste chaînée tu as plusieurs manières de faire, moi j'aime bien avoir une structure qui gère ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
struct elm {
  int n;
  struct elm * suivant;
};
 
struct fifo {
  struct elm * debut;
  struct elm * fin;
};

Pour les listes FIFO (first in first out), c'est quasiment le même principe, sauf que tu enlèves les valeurs les plus anciennes au lieux des plus récentes. Ce qui implique, pour le cas d'un tableau, d'avoir 2 compteurs, un au début, et l'autre à la fin.
Pour les listes chaînées, ça ne change pas de ce que j'ai mis plus haut, c'est seulement les fonctions d'ajout et de suppression qui seront différentes.

Après, ce que je montre est simple, il y a plein d'autre manières de faire.

[adrian07]

merci pour ta réponse...
et pour l'implémentation des files à l'aide d'un tableau????en particulier la tête et la queue??

[Ubiquité]

Pouet_forever je crois que tu a confondu lifo et fifo. fifo c'est file et lifo c'est pile.

[Pouet_forever]

Effectivement, j'ai édité.
Merci de l'avoir signalé.

@ adrian07 : Comme je l'ai dit plus haut, il suffit d'avoir un indice de début et un indice de fin. Quand tu ajoutes, tu incrémentes ton indice de début, quand tu supprimes tu incrémentes ton indice de fin. Ensuite, il faut que tu joues avec tes indices histoire de pas saturer ta file (utilisation du modulo ?).