Implémentation pile dans tableau

Résolu/Fermé
dx3d Messages postés 68 Date d'inscription dimanche 6 septembre 2009 Statut Membre Dernière intervention 19 juillet 2017 - Modifié par dx3d le 20/05/2014 à 13:58
fiddy Messages postés 11067 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 20 mai 2014 à 22:54
Bonjour, je me demandais si quelqu'un aurait la gentillesse de m'expliqué comment implémenter deux piles dans un tableau T[0...n] de telle manière qu'aucune pile ne déborde à moins que le nombre total d'éléments dans les deux piles ne vaille n + 1. Toutes les opérations doivent s'exécuter en temps O(1). Le pseudo code de chaque primitive est suffisant.

3 réponses

dx3d Messages postés 68 Date d'inscription dimanche 6 septembre 2009 Statut Membre Dernière intervention 19 juillet 2017
20 mai 2014 à 20:56
S'il vous plait, j'ai eu beau chercher sur le net, je n'arrive pas à trouver une réponse à cette question, si quelqu'un aurait une idée, merci de la partagé !
Normalement pour implémenter une pile normal avec un tableau, j'ajoute un tableau dans la structure de la pile, mais vu que les deux piles doivent partager le même tableau, dois je faire une structure qui utilise deux piles en même temps ?
0
fiddy Messages postés 11067 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 813
20 mai 2014 à 22:17
Bonjour,

Je te donne un indice :
1ère pile : de T[0] à T[i]
2ème pile : de T[n] à T[j].
Bien sûr, i<j<n.

Pas besoin de structure donc. Une simple fonction suffit.
Par exemple : void ajouterValeur(int *pile);

Je te laisse déjà avancer en tenant compte de l'aide ;-).
N'hésite pas si tu as des questions.
Cdlt,
0
dx3d Messages postés 68 Date d'inscription dimanche 6 septembre 2009 Statut Membre Dernière intervention 19 juillet 2017
20 mai 2014 à 22:43
Merci beaucoup, j'ai posé deux sommets de pile dans la structure, chacun pointant à un endroit où commence l'une des piles et quand j'empile si la taille de la pile arrive à la moitié de la taille du tableau le programme indique que la pile est pleine, etc ... :D
0
fiddy Messages postés 11067 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 813
20 mai 2014 à 22:54
quand j'empile si la taille de la pile arrive à la moitié de la taille du tableau
La condition d'arrêt est fausse. Il faut que ça s'arrête lorsque les 2 piles se rencontrent. Ce n'est pas forcément à la moitié.
0