Estructuras de datos: Pilas y Colas – Designveloper

¿Por qué pilas y colas?

A diferencia de un array, en las pilas y colas, no existe una operación de acceso aleatorio (no podemos acceder a un elemento directamente con un ‘índice’). Normalmente tenemos menos métodos/acciones que podemos realizar como push(), pop(), peek(), enqueue(), dequeue() todos ellos tratan exclusivamente con el elemento al principio o al final de la estructura de Datos.

Pero…

Pregunta: Esto suena tan limitante ya que sólo podemos acceder al primer o último elemento de la estructura de datos. ¿Por qué querríamos usar algo así? ¿Por qué no usamos arrays para tener más flexibilidad?

Respuesta: Las pilas y las colas suelen ser «estructuras de datos de nivel superior» construidas sobre otras de nivel inferior (arrays o listas enlazadas) para limitar las operaciones que podemos hacer sobre ellas. Esto es una ventaja si queremos un acceso restringido.

Tener esta capacidad limitada en una estructura de datos es una ventaja porque podemos controlar a quien utiliza esta estructura de datos que realiza sólo operaciones correctas que son eficientes. Por ejemplo, no tendremos que preguntarnos si alguien inserta al azar un elemento en medio de nuestra lista, estropeando algunos invariantes. Eso nos salvó de muchos problemas. Echemos un vistazo más de cerca a ellos.

¿Qué es una pila?

Una pila es una estructura de datos lineal de un solo extremo que modela una pila del mundo real por tener dos operaciones primarias, a saber, push y pop.

En esta imagen de abajo, podríamos ver que un miembro de datos que se salta de la parte superior de la pila y otro que se añade a ella. Hay un puntero superior que apunta al bloque en la parte superior de la pila. Esto se debe a que los elementos de una pila siempre se quitan y se añaden a la parte superior de la pila. Este comportamiento se conoce comúnmente como LIFO (Last In First Out).

Operaciones en la pila

Las siguientes son las 2 operaciones básicas que se pueden realizar en una pila.

• Función Push: Añadir un elemento en la parte superior de la pila
• Función Pop: Eliminar el elemento superior (y podría devolverlo)

Visualización de las operaciones básicas de la pila

Además, se proporcionan las siguientes funciones adicionales para una pila con el fin de comprobar su estado.

• Función Peek: Devuelve el elemento superior de la pila sin quitarlo ni borrarlo
• Función isEmpty: Comprueba si la pila está vacía o no
• Función isFull: Comprueba si la pila está llena o no

Todo opera en la parte superior de la pila. No tenemos acceso a nada más que a la parte superior. Esto es fundamental para entender su funcionamiento.

Análisis de complejidad

La siguiente tabla de complejidad supone que has implementado una pila utilizando una lista enlazada

Aplicaciones de las pilas

¿Cuándo y dónde se utiliza una pila? usamos la Pila mucho en la programación sin siquiera notarlo, aquí hay algunos ejemplos:

• Puede usarse para la evaluación de expresiones (por ejemplo: un algoritmo de shunting para analizar y evaluar expresiones matemáticas).
• Puede usarse para implementar llamadas a funciones en la programación de recursión.

• Se utiliza mediante mecanismos de deshacer en los editores de texto para deshacer el texto que hemos escrito (Cmd + Z en Mac OS y Ctrl + Z en Windows)
• Se utiliza en el navegador para navegar hacia atrás y hacia delante
• Se puede utilizar para hacer una búsqueda profunda (DFS) en un gráfico
• Se utiliza entre bastidores para soportar la recursividad manteniendo un registro de las llamadas a funciones anteriores

¿Qué es una cola?

Una cola es también una estructura de datos lineal que modela las colas del mundo real al tener dos operaciones principales, a saber, enqueue (podemos pensar en eso como «entrar en la cola») y dequeue (también podemos pensar en eso como «eliminar de la cola»). Esta estructura se llama «cola» por el hecho de que se asemeja a una cola del mundo real – (donde la gente está esperando en una cola).

Toda cola tiene un extremo delantero y otro trasero (a veces llamado «trasero»). Insertamos elementos a través de la parte trasera y los eliminamos a través de la parte delantera.

Una cola es una estructura FIFO (First In First Out – el elemento colocado en primer lugar puede ser accedido en primer lugar) que se puede encontrar comúnmente en muchos lenguajes de programación.

Operaciones de cola

Las siguientes son las 3 operaciones básicas que se pueden realizar en una cola.

• Función Enqueue: Añadir un elemento al final de la cola
• Función Dequeue: Quitar el elemento del principio de la cola
• Función Peeking: Mirar el valor del principio de la cola sin eliminarlo

Análisis de complejidad

Como podemos ver en la imagen, las operaciones de enqueuing y dequeuing tardan un tiempo constante O(1). Sin embargo, comprobar si un elemento está contenido dentro de la cola es tiempo lineal O(n) ya que potencialmente necesitaríamos escanear todos los elementos.

También hay eliminación de elementos (no dequeuing) internamente. Requiere tiempo lineal ya que tenemos que escanear a través de todos los elementos en el peor de los casos.

Aplicaciones de las colas

• Se utiliza para gestionar hilos en multithreading.
• Puede ser utilizado para mantener eficientemente la pista de los x elementos añadidos más recientemente
• Gestión de peticiones del servidor web donde queremos que el primero en llegar sea el primero en servir. Por ejemplo: En un momento dado, nuestro servidor web sólo puede servir hasta un máximo de 50 personas simultáneamente.

Si entran 70 peticiones en un periodo corto de tiempo, no podremos procesarlas todas. Por lo tanto, el servidor web sólo saca 50 peticiones de la cola y pone las 20 restantes en espera. Cuando el servidor web termina de procesar una petición, retira de la cola la siguiente para servirla y sigue haciéndolo hasta que la cola esté vacía.

• Breadth-first search (BFS) graph traversal
• Se utiliza para implementar sistemas de colas (por ejemplo: colas de prioridad)
• Se utiliza en la impresora de red: La impresora sólo puede servir una única petición a la vez. Así que si llegan otras peticiones cuando la impresora está ocupada, el programa que gestiona la impresora no rechazará esas peticiones sino que las pondrá en una cola a la espera de ser ejecutadas. La primera petición se servirá primero (FIFO).

Esperamos que este artículo te haya servido para hacerte una idea de las pilas y las colas. No olvides suscribirte a nuestro blog y seguir a Designveloper en Facebook, Twitter y LinkedIn.

Y estos son otros artículos que te pueden gustar:

• ¿Qué es la arquitectura de aplicaciones web?
• Estructuras de datos y sus aplicaciones
• ¿Qué es la notación Big O?