Una suave introducción a las estructuras de datos: cómo funcionan las pilas

Cualquiera que haya solicitado un trabajo de desarrollador en una gran empresa de tecnología, y haya pasado días practicando preguntas de entrevistas de algoritmos comunes, probablemente haya concluido:

"Guau. Realmente tengo que conocer las estructuras de datos en frío ".

¿Qué son las estructuras de datos? ¿Y por qué son tan importantes? Wikipedia proporciona una respuesta sucinta y precisa:

Una estructura de datos es una forma particular de organizar datos en una computadora para que se puedan usar de manera eficiente.

La palabra clave aquí es eficiencia, una palabra que escuchará temprano y con frecuencia a medida que analiza diferentes estructuras de datos.

Estas estructuras proporcionan un andamiaje para que los datos se almacenen de manera que permitan que las búsquedas, inserciones, eliminaciones y actualizaciones se realicen de forma rápida y dinámica.

Tan poderosas como son las computadoras, siguen siendo solo máquinas que requieren dirección para realizar cualquier tarea útil (al menos hasta que aparezca la IA general). Hasta entonces, debes darles los comandos más claros y eficientes que puedas.

Ahora, de la misma manera que puede construir una casa de 50 formas diferentes, puede estructurar los datos de 50 formas diferentes. Por suerte para ti, muchas personas realmente inteligentes han construido andamios fantásticos que han resistido la prueba del tiempo. Todo lo que tiene que hacer es aprender qué son, cómo funcionan y cómo utilizarlos mejor.

La siguiente es una lista de algunas de las estructuras de datos más comunes. Cubriré cada uno de estos individualmente en artículos futuros; este se centra al 100% en las pilas. Aunque a menudo se superponen, cada una de estas estructuras tiene matices que las hacen más adecuadas para determinadas situaciones:

Pilas
Colas
Listas vinculadas
Conjuntos
Árboles
Gráficos
Tablas hash

También encontrará variaciones en estas estructuras de datos, como listas doblemente enlazadas, árboles b y colas de prioridad. Pero una vez que comprenda estas implementaciones centrales, comprender estas variaciones debería ser mucho más fácil.

¡Así que comencemos la parte uno de nuestro análisis de estructuras de datos con un análisis de Stacks!

Pilas

Literalmente una pila de datos (como una pila de panqueques)
Adiciones (push): siempre agregue a la parte superior de la pila
Eliminaciones (pop): retire siempre de la parte superior de la pila
Tipo de patrón: L artículo ast I n es la F elemento rimero O ut (LIFO)

Ejemplo de caso de uso : uso de los botones de avance y retroceso en su navegador

En muchos lenguajes de programación, las matrices tienen la funcionalidad de una pila incorporada. Pero en aras de ser minucioso, lo reconstruirá aquí usando un objeto JavaScript.

Lo primero que necesita es crear una pila para almacenar cada sitio que visita y un método en su pila para realizar un seguimiento de su posición actual:

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

let browserHistory = new Stack();

Tenga en cuenta que el subrayado antes de los nombres de las variables significa para otros desarrolladores que estas variables son privadas y no deben manipularse externamente, solo mediante los métodos de la clase. Por ejemplo, no debería ejecutar algo como:

browserHistory._position = 2.

Es por eso que creé el método top () para devolver la posición actual de la pila.

En este ejemplo, cada sitio que visite se almacenará en la pila de historial de su navegador. Para ayudarlo a realizar un seguimiento de dónde está en la pila, puede usar la posición como clave para cada sitio web y luego incrementarla en cada nueva adición. Haré esto a través del método 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

Una vez que se ejecuta el código anterior, su objeto de almacenamiento se verá así:

 0: “google.com”

 1: “medium.com”

 2: “freecodecamp.com”

 3: “netflix.com”

Así que imagina que estás actualmente en Netflix, pero te sientes culpable por no terminar ese difícil problema de recursividad en Free Code Camp. Decides presionar el botón Atrás para eliminarlo.

¿Cómo se representa esa acción en tu pila? Con 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:

Follow a Last In First Out (LIFO) pattern
Have a push (add) and pop (remove) method that manage the contents of the stack
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.

Pilas

Further reading