Pilas

• Su nombre se deriva de la metáfora de una pila de platos en una cocina.

•  La inserción y extracción de elementos de la pila siguen el principio LIFO (last-in-first-out). 

•  El último elemento en entrar es el único accesible en cada momento. 

Definición del ADT Pila

Una pila (del inglés stack) es un Tipo Abstracto de Dato (ADT) de tipo LIFO (Last In, First Out), en el que el último elemento insertado es el primero en salir.

En otras palabras es una colecciona ordenada de elementos en la cual los datos se insertan o se retiran por el mismo extremo llamado “parte superior” de la pila. 

Joyanes Aguilar (2003) define la pila como una estructura que simula el comportamiento de una pila real: los elementos se apilan uno sobre otro, y solo se puede acceder al elemento en la cima.

Operaciones básicas

• Push(apilar): Inserta un elemento en la cima.
  
  

• Pop(desapilar): Elimina el elemento de la cima.
  
  

• Peek: Muestra el elemento en la cima sin eliminarlo.
  
  

• IsEmpty(pila vacía): Verifica si la pila está vacía.

Representación para el ADT Pila

Aplicaciones para el ADT Pila

Las pilas son especialmente útiles cuando se requiere revertir el orden de los datos o controlar el flujo de ejecución de un programa.

Ejemplos de aplicación:

• Evaluación de expresiones aritméticas (notación postfija).
  
  

• Control de llamadas recursivas en la pila de ejecución.
  
  

• Deshacer/rehacer en editores de texto.
  
  

• Validación de estructuras anidadas (paréntesis, etiquetas HTML).

• Navegador Web 

– Se almacenan los sitios previamente visitados 

– Cuando el usuario quiere regresar (presiona el botón de retroceso), simplemente se extrae la última dirección (pop) de la pila de sitios visitados. 

• Editores de texto 

– Los cambios efectuados se almacenan en una pila 

– Usualmente implementada como arreglo 

– Usuario puede deshacer los cambios mediante la operación “undo”, la cual extraer el estado del texto antes del último cambio realizado. 

Tratamiento de expresiones aritméticas

Colas

En una cola hay dos extremos, uno es llamado la parte delantera y el otro extremo se llama la parte trasera de la cola. En una cola, los elementos se retiran por la parte delantera y se agregan por la parte trasera. 

Existen numerosos casos de la vida real en los cuales se usa este concepto. Por ejemplo:

• La cola de los bancos en las que los clientes esperan para ser atendidos. La primera persona de la cola será la primera en recibir el servicio.

• La cola de los niños que esperan a veces pacientemente para subir a un juego mecánico.

• Las colas de vehículos esperando la luz verde del semáforo.

• las colas para entrar a un cine, teatro, estadio de fútbol, etcétera.

Definición del ADT Cola

Una cola (del inglés queue) es un Tipo Abstracto de Dato (ADT) de tipo FIFO (First In, First Out), en el que el primer elemento insertado es el primero en salir.

Cairó y Guardatti (2002) explican que la cola es útil para representar procesos que se atienden en orden cronológico, como turnos o solicitudes en espera.

Representación para el ADT Cola

Aplicaciones para el ADT Cola

Las colas son fundamentales en sistemas que gestionan tareas, mensajes o eventos en secuencia.

Ejemplos de aplicación:

• Gestión de trabajos en una impresora.
  
  

• Planificación de procesos en sistemas operativos.
  
  

• Modelado de líneas de espera (bancos, supermercados).
  
  

• Algoritmos de recorrido como BFS en estructuras no lineales.
  
  

• operaciones en redes de computadoras. 

– Trabajos enviados a una impresora 

– Solicitudes a un servidor. 

• Clientes solicitando ser atendidos por una telefonista.