Implementación de Pilas mediante Listas

En el ámbito de la informática, las estructuras de datos son componentes fundamentales que permiten organizar y gestionar información de manera eficiente. Entre estas estructuras, las pilas (stacks) juegan un papel crucial en diversas aplicaciones, desde la gestión de llamadas en sistemas operativos hasta la evaluación de expresiones matemáticas. Una pila se caracteriza por su comportamiento LIFO (Last-In, First-Out), donde el último elemento añadido es el primero en ser eliminado. En este artículo, exploraremos la creación de pilas utilizando listas, una estructura de datos lineal que permite almacenar una secuencia de elementos.

Conceptos Fundamentales

Pilas⁚ Estructura de Datos LIFO

Una pila es una estructura de datos lineal que sigue el principio LIFO (Last-In, First-Out). Esto significa que el último elemento agregado a la pila es el primero en ser eliminado. Visualmente, se puede imaginar una pila como una pila de platos donde el último plato colocado encima es el primero en ser retirado.

Listas⁚ Estructura de Datos Lineal

Una lista es una estructura de datos lineal que permite almacenar una secuencia de elementos en un orden específico. Cada elemento de la lista tiene un predecesor (excepto el primero) y un sucesor (excepto el último). Las listas pueden ser implementadas de diversas maneras, como listas enlazadas o listas basadas en arreglos.

Implementación de Pilas mediante Listas

Para crear una pila utilizando listas, se pueden emplear dos enfoques principales⁚ listas enlazadas y listas basadas en arreglos.

Pilas con Listas Enlazadas

Las listas enlazadas son una estructura de datos dinámica que permite la inserción y eliminación de elementos en cualquier posición de la lista. En el contexto de las pilas, se utiliza un nodo especial llamado “cabeza” (head) que apunta al primer elemento de la lista. Cada nodo de la lista contiene un valor de datos y un puntero al siguiente nodo.

Para implementar una pila con una lista enlazada, se requieren las siguientes operaciones⁚

• Push (Agregar elemento)⁚ Se crea un nuevo nodo con el valor de datos a agregar. Este nuevo nodo se coloca en la parte superior de la pila, es decir, se conecta al nodo actual de la cabeza. El puntero de la cabeza se actualiza para apuntar al nuevo nodo.
• Pop (Eliminar elemento)⁚ Se elimina el elemento de la parte superior de la pila. El puntero de la cabeza se actualiza para apuntar al siguiente nodo.
• Peek (Ver elemento superior)⁚ Se devuelve el valor del elemento en la parte superior de la pila sin eliminarlo.
• IsEmpty (Verificar si está vacía)⁚ Se devuelve un valor booleano que indica si la pila está vacía.

Ejemplo de Implementación en Python

python class Node⁚ def __init__(self, data)⁚ self.data = data self.next = None class Stack⁚ def __init__(self)⁚ self.head = None def push(self, data)⁚ new_node = Node(data) new_node.next = self.head self.head = new_node def pop(self)⁚ if self.is_empty⁚ return None else⁚ popped_data = self.head.data self.head = self.head.next return popped_data def peek(self)⁚ if self.is_empty⁚ return None else⁚ return self.head.data def is_empty(self)⁚ return self.head is None # Ejemplo de uso stack = Stack stack.push(10) stack.push(20) stack.push(30) print(stack.pop) # Salida⁚ 30 print(stack.peek) # Salida⁚ 20 print(stack.is_empty) # Salida⁚ False

Pilas con Listas Basadas en Arreglos

Las listas basadas en arreglos son estructuras de datos estáticas que almacenan elementos en una secuencia contigua de memoria. En el contexto de las pilas, se utiliza un índice para rastrear la posición del elemento superior de la pila. El índice se inicializa en -1, lo que indica que la pila está vacía.

Para implementar una pila con una lista basada en arreglos, se requieren las siguientes operaciones⁚

• Push (Agregar elemento)⁚ Se incrementa el índice y se coloca el nuevo elemento en la posición del índice actualizado.
• Pop (Eliminar elemento)⁚ Se devuelve el elemento en la posición del índice actual y se decrementa el índice.
• Peek (Ver elemento superior)⁚ Se devuelve el elemento en la posición del índice actual.
• IsEmpty (Verificar si está vacía)⁚ Se devuelve un valor booleano que indica si el índice es igual a -1.

Ejemplo de Implementación en Python

python class Stack⁚ def __init__(self, capacity)⁚ self.capacity = capacity self.array = [None] * capacity self.top = -1 def push(self, data)⁚ if self.is_full⁚ print(“Stack Overflow”) return else⁚ self.top += 1 self.array[self.top] = data def pop(self)⁚ if self.is_empty⁚ print(“Stack Underflow”) return None else⁚ popped_data = self;array[self.top] self.top -= 1 return popped_data def peek(self)⁚ if self.is_empty⁚ return None else⁚ return self.array[self.top] def is_empty(self)⁚ return self.top == -1 def is_full(self)⁚ return self.top == self.capacity ─ 1 # Ejemplo de uso stack = Stack(5) stack.push(10) stack.push(20) stack.push(30) print(stack.pop) # Salida⁚ 30 print(stack;peek) # Salida⁚ 20 print(stack.is_empty) # Salida⁚ False

Aplicaciones de las Pilas

Las pilas son estructuras de datos esenciales que encuentran aplicaciones en diversos campos de la informática, incluyendo⁚

Gestión de Llamadas en Sistemas Operativos

Los sistemas operativos utilizan pilas para gestionar las llamadas a funciones. Cuando una función se llama, su dirección de retorno y los valores de los parámetros se colocan en la pila. Cuando la función termina, se recupera la información de la pila y se continúa la ejecución en el punto de llamada original.

Evaluación de Expresiones Matemáticas

Las pilas se utilizan para evaluar expresiones matemáticas, particularmente expresiones que incluyen operadores de precedencia como paréntesis. Las expresiones se analizan de izquierda a derecha, y los operadores y operandos se colocan en una pila. Los operadores se aplican a los operandos de la pila según su precedencia, y el resultado se coloca de nuevo en la pila.

Algoritmos de Recorrido de Grafos

Los algoritmos de recorrido de grafos, como el algoritmo de profundidad primero (DFS), utilizan pilas para mantener un seguimiento de los nodos visitados. Cuando un nodo se visita, se coloca en la pila. El algoritmo luego explora los nodos adyacentes del nodo actual, y así sucesivamente. La pila se utiliza para volver atrás y explorar otros caminos cuando se encuentran callejones sin salida.

Gestión de Deshacer/Rehacer

En aplicaciones que permiten deshacer/rehacer acciones, las pilas se utilizan para almacenar el historial de acciones realizadas. Cuando se realiza una acción, se coloca en la pila. La acción “deshacer” elimina el último elemento de la pila, mientras que la acción “rehacer” coloca el elemento eliminado de nuevo en la pila.

Conclusión

La creación de pilas mediante listas es una técnica fundamental en la programación. Las listas enlazadas y las listas basadas en arreglos proporcionan dos enfoques distintos para implementar pilas. Las pilas son estructuras de datos versátiles que encuentran aplicaciones en diversos campos de la informática, desde la gestión de llamadas en sistemas operativos hasta la evaluación de expresiones matemáticas. Comprender la implementación de pilas es esencial para cualquier programador que desee desarrollar software eficiente y robusto.