6.1 Definición de pila y sus propiedades
Pila — es una estructura de datos abstracta que es una colección de elementos organizados según el principio de "último en entrar, primero en salir" (Last In, First Out, LIFO). Una pila se puede imaginar como una pila de libros: el último libro añadido está en la cima de la pila y será el primero en ser removido/sacado.
Propiedades de la pila:
- LIFO (Last In, First Out): El último elemento añadido se extrae primero.
- Operaciones limitadas: En la pila solo se soportan las operaciones de añadir (push), quitar (pop) y visualizar (peek) el elemento de la cima.
- Acceso unidireccional: El acceso a los elementos solo es posible desde la cima de la pila.
- Simplicidad de implementación: Una pila se puede implementar fácilmente con un array o una lista enlazada.
- Gestión de memoria: Los datos o estados temporales se pueden almacenar y recuperar en el orden inverso al de su adición.
Principio de funcionamiento LIFO:
- Añadir un elemento (push): Un nuevo elemento se añade a la cima de la pila.
- Eliminar un elemento (pop): El último elemento añadido se elimina de la cima de la pila.
- Visualizar la cima (peek): Permite ver el elemento en la cima de la pila sin eliminarlo.
Los elementos de la pila se añaden y eliminan desde un solo lado, llamado la cima (top). De esta manera, el último elemento añadido siempre estará en la cima y será eliminado primero.
6.2 Operaciones principales
Operaciones principales: push, pop, peek
Operación push: Añade un nuevo elemento a la cima de la pila.
Complejidad temporal: O(1).
Ejemplo de emulación de una pila en Python usando una clase list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Salida: [10, 20]
Operación pop: Elimina y devuelve el elemento de la cima de la pila.
Complejidad temporal: O(1).
Ejemplo de emulación de una pila en Python usando una clase list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Salida: 20
print(stack) # Salida: [10]
Operación peek: Devuelve el elemento en la cima de la pila sin eliminarlo.
Complejidad temporal: O(1).
Ejemplo de implementación:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Salida: 10
6.3 Ejemplos de uso de la pila
Vamos a ver algunos ejemplos de uso de la pila:
Gestión de llamadas a funciones
En Python, la pila se utiliza para rastrear las funciones durante la ejecución del programa. Cada vez que se llama a una función, su dirección de retorno y variables locales se colocan en la pila. Cuando la función termina su ejecución, el control vuelve a la función que la llamó, y los datos se extraen de la pila.
Ejemplo de uso de la pila de llamadas:
En este ejemplo, las llamadas recursivas a la función factorial usan la pila de llamadas para almacenar el estado de cada llamada hasta que se alcanza la condición base (n == 1).
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Salida: 120
Deshacer operaciones (Undo)
La pila se utiliza para implementar la función de deshacer acciones en editores de texto y otras aplicaciones. Cuando el usuario realiza una acción, esta se guarda en la pila. Al realizar la operación Undo, la última acción se extrae de la pila y se deshace.
Ejemplo de uso de la pila para deshacer operaciones:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Ejemplo de uso:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Salida: "Hello World"
editor.undo()
print(editor.text) # Salida: "Hello"
editor.undo()
print(editor.text) # Salida: ""
GO TO FULL VERSION