Une introduction douce aux structures de données: comment fonctionnent les piles

Quiconque a postulé pour un emploi de développeur dans une grande entreprise de technologie - et passé des jours à pratiquer des questions d'entrevue d'algorithme courantes - a probablement conclu:

"Sensationnel. Je dois vraiment connaître les structures de données à froid. »

Que sont les structures de données? Et pourquoi sont-ils si importants? Wikipedia fournit une réponse succincte et précise:

Une structure de données est une manière particulière d'organiser des données dans un ordinateur afin qu'elles puissent être utilisées efficacement.

Le mot clé ici est l' efficacité, un mot que vous entendrez tôt et souvent lorsque vous analysez différentes structures de données.

Ces structures fournissent un échafaudage pour les données à stocker de manière à permettre des recherches, des insertions, des suppressions et des mises à jour rapides et dynamiques.

Aussi puissants que soient les ordinateurs, ce ne sont encore que des machines qui nécessitent une direction pour accomplir toute tâche utile (du moins jusqu'à ce que l'IA générale arrive). Jusque-là, vous devez leur donner les commandes les plus claires et les plus efficaces possibles.

Désormais, de la même manière que vous pouvez construire une maison de 50 manières différentes, vous pouvez structurer les données de 50 manières différentes. Heureusement pour vous, beaucoup de gens vraiment intelligents ont construit de superbes échafaudages qui ont résisté à l'épreuve du temps. Tout ce que vous avez à faire est d'apprendre ce qu'ils sont, comment ils fonctionnent et comment les utiliser au mieux.

Voici une liste de quelques-unes des structures de données les plus courantes. Je couvrirai chacun de ces éléments individuellement dans les prochains articles - celui-ci se concentre à 100% sur les piles. Bien qu'il y ait souvent des chevauchements, chacune de ces structures présente des nuances qui les rendent les mieux adaptées à certaines situations:

  • Piles
  • Files d'attente
  • Listes liées
  • Ensembles
  • Des arbres
  • Graphiques
  • Tables de hachage

Vous rencontrerez également des variations sur ces structures de données, telles que des listes à double lien, des b-arbres et des files d'attente de priorité. Mais une fois que vous avez compris ces implémentations de base, comprendre ces variations devrait être beaucoup plus facile.

Commençons donc la première partie de nos structures de données avec une analyse des piles!

Piles

  • Littéralement une pile de données (comme une pile de crêpes)
  • Ajouts (push) - toujours ajouter en haut de la pile
  • Suppressions (pop) - retirez toujours du haut de la pile
  • Type de motif: L article ast I n est le F article irst O ut (LIFO)
  • Exemple de cas d'utilisation : utilisation des boutons Précédent et Suivant de votre navigateur

Dans de nombreux langages de programmation, les tableaux ont la fonctionnalité d'une pile intégrée. Mais dans un souci de rigueur, vous allez le reconstruire ici en utilisant un objet JavaScript.

La première chose dont vous avez besoin est de créer une pile pour stocker chaque site que vous visitez, et une méthode sur votre pile pour suivre votre position actuelle:

class Stack { constructor(){ this._storage = {}; this._position = -1; // 0 indexed when we add items! } top(){ return this._position; }}
let browserHistory = new Stack();

Notez que le trait de soulignement avant les noms des variables signifie pour les autres développeurs que ces variables sont privées et ne doivent pas être manipulées de manière externe - uniquement par les méthodes de la classe. Par exemple, je ne devrais pas exécuter quelque chose comme:

browserHistory._position = 2.

C'est pourquoi j'ai créé la méthode top () pour renvoyer la position actuelle de la pile.

Dans cet exemple, chaque site que vous visitez sera stocké dans votre pile browserHistory. Pour vous aider à garder une trace de son emplacement dans la pile, vous pouvez utiliser la position comme clé pour chaque site Web, puis l'incrémenter à chaque nouvel ajout. Je vais le faire via la méthode push:

class Stack {
 constructor(){ this._storage = {}; this._position = -1; }
 push(value){ this._position++; this._storage[this._position] = value }
 top(){ return this._position; }
}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to MediumbrowserHistory.push("medium.com"); // navigating to Free Code CampbrowserHistory.push("freecodecamp.com"); // navigating to NetflixbrowserHistory.push("netflix.com"); // current site

Une fois le code ci-dessus exécuté, votre objet de stockage ressemblera à ceci:

{
 0: “google.com”
 1: “medium.com”
 2: “freecodecamp.com”
 3: “netflix.com”
}

Alors imaginez que vous êtes actuellement sur Netflix, mais que vous vous sentez coupable de ne pas avoir résolu ce difficile problème de récursivité sur Free Code Camp. Vous décidez d'appuyer sur le bouton retour pour l'assommer.

Comment cette action est-elle représentée dans votre pile? Avec pop:

class Stack { constructor(){ this._storage = {}; this._position = -1; } push(value){ this._position++; this._storage[this._position] = value; } pop(){ if(this._position > -1){ let val = this._storage[this._position]; delete this._storage[this._position]; this._position--; return val; } }
 top(){ return this._position; }}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to MediumbrowserHistory.push("medium.com"); // navigating to Free Code CampbrowserHistory.push("freecodecamp.com"); // navigating to NetflixbrowserHistory.push("netflix.com"); //current site
browserHistory.pop(); //Returns netflix.com
//Free Code Camp is now our current site

By hitting the back button, you remove the most recent site added to your browser History and view the one on top of your stack. You also decrement the position variable so you have an accurate representation of where in the history you are. All of this should only occur if there’s actually something in your stack of course.

This looks good so far, but what’s the last piece that’s missing?

When you finish crushing the problem, you decide to reward yourself by going back to Netflix, by hitting the forward button. But where’s Netflix in your stack? You technically deleted it to save space, so you don’t have access to it anymore in your browserHistory.

Luckily, the pop function did return it, so maybe you can store it somewhere for later when you need it. How about in another stack!

You can create a “forward” stack to store each site that’s popped off of your browserHistory. So when you want to return to them, you just pop them off the forward stack, and push them back onto your browserHistory stack:

class Stack { constructor(){ this._storage = {}; this._position = -1; } push(value){ this._position++; this._storage[this._position] = value; } pop(){ if(this._position > -1){ let val = this._storage[this._position]; delete this._storage[this._position]; this._position--; return val; } }
top(){ return this._position; }}
let browserHistory = new Stack();let forward = new Stack() //Our new forward stack!
browserHistory.push("google.com");browserHistory.push("medium.com");browserHistory.push("freecodecamp.com");browserHistory.push("netflix.com");
//hit the back button
forward.push(browserHistory.pop()); // forward stack holds Netflix
// ...We crush the Free Code Camp problem here, then hit forward!
 browserHistory.push(forward.pop());
//Netflix is now our current site

And there you go! You’ve used a data structure to re-implement basic browser back and forward navigation!

Now to be completely thorough, let’s say you went to a completely new site from Free Code Camp, like LeetCode to get more practice. You technically would still have Netflix in your forward stack, which really doesn’t make sense.

Luckily, you can implement a simple while loop to get rid of Netflix and any other sites quickly:

//When I manually navigate to a new site, make forward stack empty
while(forward.top() > -1){ forward.pop();}

Great! Now your navigation should work the way it’s supposed to.

Time for a quick recap. Stacks:

  1. Follow a Last In First Out (LIFO) pattern
  2. Have a push (add) and pop (remove) method that manage the contents of the stack
  3. Have a top property that allows us to track how large your stack is and the current top position.

At the end of each post in this series, I’ll do a brief time complexity analysis on the methods of each data structure to get some extra practice.

Here’s the code again:

push(value){ this._position++; this._storage[this._position] = value; } pop(){ if(this._position > -1){ let val = this._storage[this._position]; delete this._storage[this._position]; this._position--; return val; } } top(){ return this._position; }

Push (addition) is O(1). Since you’ll always know the current position (thanks to your position variable), you don’t have to iterate to add an item.

Pop (removal) is O(1). No iteration is necessary for removal since you always have the current top position.

Top is O(1). The current position is always known.

There isn’t a native search method on stacks, but if you were to add one, what time complexity do you think it would be?

Find (search) would be O(n). You would technically have to iterate over your storage until you found the value you were looking for. This is essentially the indexOf method on Arrays.

Further reading

Wikipedia has an in-depth list of abstract data types.

I didn’t get a chance to get into the topic of a stack overflow, but if you’ve read my post on recursion you might have a good idea on why they occur. To beef up that knowledge, there is a great post about it on StackOverflow (see what I did there?)

In my next post, I’ll jump right into queues.