Il y'a un an lorsque j'étais un super débutant en programmation, je m'attardais sur l'apprentissage du langage de programmation au lieu d'étudier l'algorithmique. C'est d'ailleurs l'erreur que comettent tous les débutants. Mais au fur et à mesure que j'avancais, je me rendais compte qu'il fallait que je comprenne impérativement l'algorithmique avant de me lancer à fond dans la programmation et c'est ce que j'ai fait. Attention, je ne dis pas que je suis un expert mais en tant que junior, j'ai décidé de vous aider à mieux appréhender certains concepts de l'algorithmique concernant les structures de données. Ainsi, je vous présenterai dans cet article la notion de piles. Puis à la fin de cet article, vous trouverez quelques lignes de codes écris en langage Python qui est mon langage de programmation favoris! Je commencerai d'abord par définir ce que c'est qu'un algorithme.
Alors, un algorithme est la description précise et simple de la manière dont on peut résoudre un problème. Pour cela, on doit analyser, manipuler et stocker l’information. La manière dont on organise cette information stockée peut avoir des conséquences très importantes sur leur manipulation. Concrètement, avec un dictionnaire qui est un ensemble de mots et leur définition, pourrait-on l’utiliser correctement si ses mots sont placés dans le désordre ? Certainement pas, parce qu'il serait très difficile de trouver la définition d'un mot que l'on cherche. L'ordre alphabétique est clairement une solution très efficace pour pouvoir retrouver rapidement le mot que l'on cherche. Ainsi, il y a des liens forts entre les algorithmes qui décrivent des méthodes et les structures de données comme les piles qui décrivent une organisation.
On sait que les tableaux représentent des suites d'éléments que l'on peut agrandir ou rétrécir selon ses besoins. Alors, si l'on manipule un tableau qui évolue au cours du temps, on peut en ajouter et en retirer des éléments. Bien sûr, en langage Python on ne parle pas de tableaux comme en C ou en Java, donc je m'atarderai sur les listes qui sont des structures proches des tableaux.
Supposons que l'on ajoute toujours les éléments au début du tableau. Pour retirer ces éléments, il y a deux possibilités: le cas où on retire toujours les éléments au début du tableau et le cas où on retire toujours les éléments à la fin du tableau. Dans le premier cas, on dit qu'on utilise une structure de pile et dans le deuxième, une structure de file.
De ce fait, on peut imaginer une pile comme une boite dans laquelle on place des objets et de laquelle on les retire dans un ordre inverse de celui dans lequel on les a mis. Les objets sont les uns sur les autres dans la boite et on ne peut accéder qu’à l’objet situé au sommet. Ainsi, une pile, comme un tableau, est une structure de donnée linéaire dans le sens où elle stocke les données les unes à la suite des autres.
Imaginons que Mr Tatang donne un exercice à des étudiants et qu’il décide de corriger leurs copies. Lorsque chacun finira, il ira remettre sa copie à l’enseignant qui les empilera comme indiqué ci-dessous:
Vanessa 4
Orline 3
Doui 2
Kenzo 1
Nasser 0
Alors, si Nasser fini le premier, sa copie sera tout en bas (idice 0), puis suivra les copies de Kenzo(1), Doui(2), Orline(3) et enfin celle de Vanessa(4). Lors des corrections, la feuille de qui Mr Tatang corrigera-t-il en premier ? Bien sûr celle de Vanessa. Et puis, au même moment, il pourra aussi ajouter celle de Moxy au dessus de celle de Vanessa ou bien déchirer la copie d’un tricheur parmi les copies qu'il a devant lui! Cet exercice traduit très bien la structure des piles et on en déduit qu’une pile peut être vide, et qu’on peut y ajouter ou retirer des éléments, d’où les algorithmes suivants.
Cette définition de pile nous pousse à avoir trois procédures ou fonctions: vider() pour supprimer toute la liste, ajouter() pour insérer un élément dans la liste et retirer() pour omettre un élément de la liste.
# -*- coding: utf-8 -*-
def vider(pile=[]):
"""vider() est la fonction qui permet de vider la liste."""
pile[:] = [] # remplacer la liste précédente par une liste vide
return pile
def ajouter(pile=[]):
"""ajouter() est la procédure qui ajoute un élément à la liste."""
a = input("que voulez-vous ajouter ? ")
pile.append(a)
return pile
def retirer(pile=[]):
"""retirer() permet d'enlever un élément de la liste."""
a = input("que voulez-vous retirer ? ")
pile.remove(a)
return pile