Pilas (Stacks)
Las pilas (stacks) son una estructura de datos donde tenemos una colección de elementos, y sólo podemos hacer dos cosas:
- añadir un elemento al final de la pila
- sacar el último elemento de la pila
Una manera común de visualizar una pila es imaginando una torre de panqueques, donde una vez que ponemos un panqueque encima de otro, no podemos sacar el anterior hasta que se hayan sacado todos los que están encima.
A pesar de su simplicidad, las pilas son estructuras relativamente comunes en ciertas áreas de la computación, en especial para implementar o simular evaluación de expresiones, recursión, scope, …
Stacks are used extensively in programming language implementations for everything from expression evaluation to handling function calls.
Fuente: Michael McMillan, Data Structures and Algorithms with JavaScript, O’Reilly Media, 2014.
LIFO (Last In First Out)
Las pilas son estructuras de tipo LIFO, lo cual quiere decir que el último elemento añadido es siempre el primero en salir.
De alguna forma, podemos decir que una pila es como si fuera una lista o array, en el sentido que es una colección, pero a diferencia de los arrays y otras colecciones, en las pilas solo accedemos al elemento que esté “encima de la pila”, el último elemento. Nunca manipulamos ni accedemos a valores por debajo del último elemento.
API
Para implementar una pila, nuestra abstracción debe implementar solamente dos métodos (push() y pop()), pero normalmente vamos a querer otros métodos como peek() o length() que nos ayuden a usar nuestros stacks en el mundo real.
Igual que cuando vimos Set, empezamos declarando una función, un constructor, que usaremos para crear objetos de tipo Stack en este caso.
function Stack() { this.data = [];
this.top = 0;
}
En esta implementación vamos a usar internamente un array para almacenar los elementos de la pila, y un contador donde vamos a almacenar la posición del último elemento (top). Ahora que ya podemos crear pilas usando new Stack(), empecemos a añadir los métodos correspondientes.
Stack.prototype.push = function (element) { this.data[this.top++] = element;
};
Nuestro método push hace dos cosas en la misma línea. Primero almacena element en nuestro array en la última posición (usando el valor actual de this.top) y después incrementa this.top (usando el operador ++). Continuemos viendo ahora el método pop():
Stack.prototype.pop = function () { return this.data[--this.top];
};
La implementación de pop() puede parecer un poco confusa, pero en realidad es muy sencilla. Nuestro código simplemente retorna el último elemento de la pila y “decrementa” this.top, de tal manera que si hacemos pop() otra vez retornaría el elemento anterior, y a sí sucesivamente. En nuestra implementación pop() no altera el array donde guardamos la data, simplemente movemos el contador (this.top).
Stack.prototype.peek = function () { return this.data[this.top - 1];
};
El método peek() nos permite ver el valor del último elemento, pero a diferencia de pop(), no borramos el elemento del stack.
Stack.prototype.length = function () { return this.top;
};
Para poder ver el tamaño (o longitud) de nuestro stack implementamos el método length(), que simplemente retorna this.top. Finalmente, si quisiéramos poder “resetear” nuestro stack, podríamos añadir un método clear():
Stack.prototype.clear = function () { this.top = 0;
};
Ejemplos
Ahora que ya tenemos una implementación de Stack, veamos algunos ejemplos y veamos a los stacks en acción!
Conversiones de base
Imaginemos que nos piden escribir una función que convierta cualquier número (en notación decimal) en su representación en otra base. Por ejemplo, si nos dan el número 3 y nos piden convertirlo a base 2 (binario), el resultado debería de ser 11.
Podemos resolver el problema usando un Stack, donde vamos a ir almacenando cada dígito de la descomposición, que va a ser el “resto” (módulo) que queda al dividir número por la base. Y así para cada dígito. Una vez completada la descomposición podemos construir el resultado simplemente sacando los elementos del stack en orden inverso a como se añadieron (el último sale el primero), que es el comportamiento de un stack.
function convertirBase(num, base) { var s = new Stack(); do {
s.push(num % base);
num = Math.floor(num /= base);
} while (num > 0); var converted = "";
while (s.length() > 0) {
converted += s.pop();
} return converted;
}
Palíndromos
Para insistir en la naturaleza LIFO de los stacks, hemos visto como podemos usar un stack para invertir el orden de los elementos de una colección. Usando esta misma técnica (si nos olvidamos por un momento de que los arrays en JavaScript ya tienen un método reverse()) podemos resolver el ya clásico problema donde nos piden averiguar si una palabra es “palíndroma”.
function isPalindrome(word) { var s = new Stack(); for (var i = 0; i < word.length; ++i) {
s.push(word[i]);
} var rword = ""; while (s.length() > 0) {
rword += s.pop();
} return word === rword;
}
Recursion
Como último ejemplo, vamos a ver como podemos usar stacks para simular recursión. Hemos visto anteriormente que algunos problemas se pueden solucionar usando algoritmos recursivos, donde desde el cuerpo de una función invocamos a la misma. Funciones que se ejecutan a si mismas… Uno de los ejemplos más típicos de función recursiva es la siguiente implementación de factorial(), que calcula el factorial de un número (el producto de todos los enteros positivos hasta n).
function factorial(n) { if (n === 0) {
return 1;
} return n * factorial(n - 1);
}
Ahora veamos como podemos “simular” la recursión usando una pila. Para ello:
- Creamos un stack y añadimos todos los enteros positivos desde
nhasta1en orden decreciente - Retiramos elementos del stack uno a uno y los vamos multiplicando al producto, donde vamos a ir almacenando el resultado agregado.
function fact(n) { var s = new Stack();
var product = 1; while (n > 1) {
s.push(n--);
} while (s.length() > 0) {
product *= s.pop();
} return product;
}
De esta forma hemos visto como un algoritmo recursivo puede implementarse en estilo iterativo usando pilas.
