Stack (Pilas): LIFO, implementación con arrays y listas enlazadas
Una pila (Stack) es una estructura de datos lineal que sigue el principio LIFO (Last In, First Out), es decir, el último elemento en entrar es el primero en salir.
Características
- Solo permite inserciones y eliminaciones por un extremo, llamado tope (top).
- Operaciones fundamentales:
- push: Inserta un elemento en el tope de la pila.
- pop: Elimina y devuelve el elemento del tope de la pila.
- peek (o top): Devuelve el elemento en el tope sin eliminarlo.
- isEmpty: Verifica si la pila está vacía.
Ejemplo de LIFO
Una pila de platos: el último plato en ponerse es el primero que se retira.
Implementación
Las pilas pueden implementarse de dos maneras:
- Usando arrays: Aprovecha los índices del arreglo para insertar o eliminar en el final.
- Usando listas enlazadas: Cada nodo contiene un dato y una referencia al siguiente nodo, y el tope se mueve dinámicamente.
Flujo de operaciones LIFO
Representación visual
Ejemplo Técnico
- Paradigma:
- Paradigma: Procedural
- Paradigma: Funcional
- Código Java Ejemplo
- Test Unitario
Implementación con arrays:
StackArray.java
public class StackArray<T> {
private Object[] elements;
private int top;
private int capacity;
public StackArray(int size) {
capacity = size;
elements = new Object[size];
top = -1;
}
public void push(T data) {
if (top == capacity - 1) throw new RuntimeException("Stack overflow");
elements[++top] = data;
}
public T pop() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
return (T) elements[top--];
}
public T peek() {
if (isEmpty()) throw new RuntimeException("Stack is empty");
return (T) elements[top];
}
public boolean isEmpty() {
return top == -1;
}
}
Implementación con listas enlazadas:
StackLinkedList.java
class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
public class StackLinkedList<T> {
private Node<T> top;
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
}
public T pop() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
T data = top.data;
top = top.next;
return data;
}
public T peek() {
if (isEmpty()) throw new RuntimeException("Stack is empty");
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
public class StackTest {
@Test
void testPushPopArray() {
StackArray<Integer> stack = new StackArray<>(3);
stack.push(10);
stack.push(20);
assertEquals(20, stack.pop());
assertEquals(10, stack.pop());
}
@Test
void testPushPopLinkedList() {
StackLinkedList<Integer> stack = new StackLinkedList<>();
stack.push(5);
stack.push(15);
assertEquals(15, stack.pop());
assertEquals(5, stack.pop());
}
}
- Código Python Ejemplo
- Test Unitario
Implementación con listas: (arrays dinámicos en Python)
def create_stack():
return []
def push(stack, data):
stack.append(data)
def pop(stack):
if is_empty(stack):
raise IndexError("Stack underflow")
return stack.pop()
def peek(stack):
if is_empty(stack):
raise IndexError("Stack is empty")
return stack[-1]
def is_empty(stack):
return len(stack) == 0
Implementación con listas enlazadas:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def create_linked_stack():
return None
def push_linked(top, data):
new_node = Node(data)
new_node.next = top
return new_node
def pop_linked(top):
if top is None:
raise IndexError("Stack underflow")
return top.next, top.data
def peek_linked(top):
if top is None:
raise IndexError("Stack is empty")
return top.data
def is_empty_linked(top):
return top is None
from stack import create_stack, push, pop, peek, is_empty
def test_stack_array():
stack = create_stack()
push(stack, 1)
push(stack, 2)
assert pop(stack) == 2
assert peek(stack) == 1
def test_stack_linked():
from stack import create_linked_stack, push_linked, pop_linked, peek_linked
top = create_linked_stack()
top = push_linked(top, 5)
top = push_linked(top, 10)
top, data = pop_linked(top)
assert data == 10
assert peek_linked(top) == 5
- Código TS Ejemplo
- Test Unitario
Implementación con arrays:
export const createStack = <T>(): T[] => [];
export const push = <T>(stack: T[], data: T): void => {
stack.push(data);
};
export const pop = <T>(stack: T[]): T => {
if (isEmpty(stack)) throw new Error("Stack underflow");
return stack.pop()!;
};
export const peek = <T>(stack: T[]): T => {
if (isEmpty(stack)) throw new Error("Stack is empty");
return stack[stack.length - 1];
};
export const isEmpty = <T>(stack: T[]): boolean => stack.length === 0;
Implementación con listas enlazadas:
export type Node<T> = {
data: T;
next: Node<T> | null;
};
export const pushLinked = <T>(top: Node<T> | null, data: T): Node<T> => {
return { data, next: top };
};
export const popLinked = <T>(top: Node<T> | null): { top: Node<T> | null; data: T } => {
if (!top) throw new Error("Stack underflow");
return { top: top.next, data: top.data };
};
export const peekLinked = <T>(top: Node<T> | null): T => {
if (!top) throw new Error("Stack is empty");
return top.data;
};
export const isEmptyLinked = <T>(top: Node<T> | null): boolean => !top;
import { createStack, push, pop, peek } from "./stack";
test("stack array push and pop", () => {
const stack = createStack<number>();
push(stack, 1);
push(stack, 2);
expect(pop(stack)).toBe(2);
expect(peek(stack)).toBe(1);
});
Aplicaciones Prácticas
- Navegadores web: Historial de páginas (ir atrás/adelante).
- Evaluadores de expresiones: Manejo de operadores y operandos.
- Recursión: La pila del sistema almacena llamadas a funciones.
- Deshacer/Rehacer: En editores de texto o gráficos.
Buenas prácticas
- SRP: La pila debe encargarse solo de almacenar y recuperar elementos.
- Nombres claros:
push,pop,peekindican exactamente su propósito. - Pruebas unitarias: Validar condiciones de desbordamiento y subdesbordamiento.
- Abstracción: Las implementaciones (array o lista) pueden cambiar sin afectar la interfaz.
Diagrama de secuencia
- El usuario solicita insertar el elemento 10.
- El Stack recibe la información y solicita crear un nodo con el valor enviado.
- Se crea un nodo con valor 10 y se le informa a la pila.
- Dentro de la pila asigna el nuevo nodo como top de la pila.
- El usuario solicita insertar el elemento 20.
- El Stack recibe la información y solicita crear un nodo con el valor enviado.
- Se crea un nodo con valor 20 y se le informa a la pila.
- En la pila, el nuevo nodo se enlaza con el nodo anterior mediante una referencia.
- Dentro de la pila asigna el nuevo nodo como top de la pila.
- El usuario solicita ver el elemento en el tope.
- La pila devuelve el valor 20 sin eliminarlo.
- El usuario solicita eliminar el elemento en el tope.
- Se verifica que la pila no esté vacía.
- Se obtiene el valor 20 y se guarda en una nueva variable.
- Se actualiza el top al nodo siguiente (10), en otras palabras, se elimina del stack.
- Se devuelve el valor eliminado.