3.2. Pilas

A) Concepto

Una pila es una estructura de datos dinámica formada por un grupo ordenado de elementos homogéneos (todos del mismo tipo) en la que los elementos sólo pueden ser añadidos o eliminados por un extremo llamado cabecera o cima (top) de la pila.

De esta forma, los elementos se extraen en orden inverso al seguido en el proceso de inserción. Por ello, una pila es considerada una estructura de datos LIFO (Last In First Out), esto es, que el último elemento que entra es el primero que sale.

	↑Sacar (Pop) ↓Meter (Push)
+
E	→ Cima (Top)
D
C
B
A	→ Fondo (Bottom)

Recibe su nombre por su similitud con una pila de objetos; si tenemos una pila de 5 libros, siempre cogemos el de arriba, que es el último que se dejó. Si queremos leer un libro que está en cuarto lugar debemos coger primero el quinto libro y a continuación el cuarto.

B) Operaciones sobre una pila

Las operaciones básicas que podemos realizar sobre una pila son dos: almacenamiento (push) y recuperación (pop). Para manejar una estructura de datos tipo pila, un programador debe definir un conjunto de operaciones que permitan al usuario acceder y manipular los elementos en ella almacenados. Más adelante se detallará cómo en PHP existen una gran cantidad de funciones predefinidas que permiten gestionar esta estructura de datos de forma eficiente.

Generalmente, cada una de estas operaciones suele recibir un nombre fijo e identificativo de la operación que realiza, siendo la terminología utilizada más común la mostrada a continuación:

Meter o Apilar: se denomina así a la operación que añade un elemento a una pila.
Sacar o Desapilar: operación que saca un elemento de la pila.
InicializarPila: una vez creada la pila y antes de usarla, esta debe quedar inicialmente vacía.
PilaVacia: operación que devuelve un valor de tipo lógico para comprobar si la pila se encuentra vacía antes de sacar un elemento.
PilaLlena: la usaremos en aquellos casos en que sea necesario saber si la pila se encuentra llena antes de añadir un nuevo elemento.
Cima: útil para obtener el último elemento que fue añadido a la pila, este es, el primero en salir de ella.

C) Implementación en PHP

El tipo de dato array en PHP dispone de una gran cantidad de funciones para hacer la implementación más fácil al programador, concretamente podemos usar las funciones array_pop(), array_push(), count(). Vemos algunos ejemplos.

Ejemplo de array_push()

 <?php
$pila = array("naranja", "plátano");
array_push($pila, "manzana", "arándano");
print_r($pila);
?>

El resultado del ejemplo sería:

Array
(
    [0] => naranja
    [1] => plátano
    [2] => manzana
    [3] => arándano
)

Ejemplo de array_pop()

 <?php
$pila= array("naranja", "plátano", "manzana", "frambuesa");
$pila= array_pop($pila);
print_r($pila);
?>

Después de hacer esto, $pila sólo tendrá 3 elementos:

Array
(
    [0] => naranja
    [1] => plátano
    [2] => manzana
)

Ejemplo de count()

 <?php
$pila = array("naranja");
$pila= array_pop($pila);
print_r($pila); // Devuelve null

$resultado = count(pila);
// $resultado = 0 será el caso de pila vacía
?>

Para saber más

Una pila puede ser implementada de dos formas diferentes:

Usando una tabla unidimensional (estructura de datos estática).
Mediante el uso de punteros (estructura de datos dinámica).

El primer caso, tabla, es más sencillo de implementar, sin embargo, y dado que una pila es una estructura de datos dinámica, el uso de punteros es más lógico. Gráficamente la implementación de una pila usando punteros sería:

Pila		Cima						Fondo
	→	dir_mem1		→			→	dir_memN		→	NULO

Cuando se crea la pila el puntero tiene valor Nulo, esto es:

Pila vacía
	→	NULO