- Concepto de Pila
Una pila es una estructura de datos lineal que restringe las operaciones de inserción y eliminación a un solo extremo, denominado la cima. El extremo opuesto se conoce como la base. Este principio de funcionamiento se denomina LIFO (Last In, First Out) o, en español, Último en Entrar, Primero en Salir. Insertar un elemento en la cima se denomina operación push, mientras que eliminar un elemento de la cima se denomina operación pop.
- Implementación con Arreglo (Pila Secuencial)
Esta implementación utiliza un bloque contiguo de memoria. La base de la pila se fija en el extremo de menor dirección, y la cima se desplaza conforme se realizan operaciones push y pop.
2.1 Definición del Tipo
#define MAX_CAPACITY 100
typedef char Element;
typedef struct {
Element *base_pointer;
Element *top_pointer;
int capacity;
} ArrayStack;
2.2 Inicialización
Se asigna memoria dinámica para el arreglo. Al principio, los punteros base y top apuntan a la misma posición, indicando que la pila está vacía.
int initializeStack(ArrayStack *stack) {
stack->base_pointer = (Element *)malloc(sizeof(Element) * MAX_CAPACITY);
if (!stack->base_pointer) {
return 0; // Error de asignación
}
stack->top_pointer = stack->base_pointer;
stack->capacity = MAX_CAPACITY;
return 1; // Éxito
}
2.3 Operación Push (Apilar)
Se verifica si la pila está llena comparando la distancia entre los punteros top y base con la capacidad. Si hay espacio, el elemento se escribe en la posición actual de top y el puntero se incrementa.
int push(ArrayStack *stack, Element value) {
if (stack->top_pointer - stack->base_pointer == stack->capacity) {
return 0; // Pila llena
}
*(stack->top_pointer) = value;
stack->top_pointer++;
return 1; // Éxito
}
2.4 Operación Pop (Desapilar)
Se verifica si la pila está vacía (base == top). Si no lo está, el puntero top se decrementa y el elemento en la nueva posición de top se devuelve a través del puntero de salida.
int pop(ArrayStack *stack, Element *output) {
if (stack->base_pointer == stack->top_pointer) {
return 0; // Pila vacía
}
stack->top_pointer--;
*output = *(stack->top_pointer);
return 1; // Éxito
}
2.5 Otras Operaciones
Operaciones auxiliares como verificar si la pila está vacía, llena o consultar el elemento en la cima sin retirarlo.
int isStackEmpty(const ArrayStack *stack) {
return stack->base_pointer == stack->top_pointer;
}
int isStackFull(const ArrayStack *stack) {
return (stack->top_pointer - stack->base_pointer) == stack->capacity;
}
Element peekTop(const ArrayStack *stack) {
if (!isStackEmpty(stack)) {
return *(stack->top_pointer - 1);
}
// Manejo de error o valor centinela omitido por brevedad
}
2.6 Ejemplo de Uso
El siguiente fragmento de código demuestra la creación de una pila, la inserción de varios caracteres y su extracción en ordan LIFO.
#include <stdio.h>
#include <stdlib.h>
// ... (Incluir las definiciones y funciones anteriores)
int main() {
ArrayStack myStack;
initializeStack(&myStack);
push(&myStack, 'X');
push(&myStack, 'Y');
push(&myStack, 'Z');
Element retrieved;
printf("Desapilando: ");
while (!isStackEmpty(&myStack)) {
pop(&myStack, &retrieved);
printf("%c ", retrieved);
}
printf("\n");
return 0;
}
La salida del programa sería: Z Y X.
- Implementación con Lista Enlazada (Pila Enlazada)
Esta implementación utiliza nodos dinámicos enlazados. La cima de la pila es el puntero al primer nodo de la lista. No se requiere un nodo cabeza. Las operaciones se realizan únicamente en la cima (cabeza de la lista).
3.1 Definición del Tipo
typedef int StackItem;
typedef struct Node {
StackItem data;
struct Node *next;
} Node;
typedef Node *LinkedStack;
3.2 Inicialización
Inicializar la pila simplemente implica establecer el puntero de la cima a NULL.
void initLinkedStack(LinkedStack *stack) {
*stack = NULL;
}
3.3 Operación Push (Apilar)
Se crea un nuevo nodo, se asigna el dato, su campo next apunta al nodo que actualmente es la cima, y luego el puntero de la pila se actualiza para apuntar al nuevo nodo.
int pushLinked(LinkedStack *stack, StackItem value) {
Node *new_node = (Node *)malloc(sizeof(Node));
if (!new_node) {
return 0; // Fallo en asignación de memoria
}
new_node->data = value;
new_node->next = *stack;
*stack = new_node;
return 1; // Éxito
}
3.4 Operación Pop (Desapilar)
Se guarda temporalmente el nodo de la cima, se extrae su dato, el puntero de la pila se avanza al siguiente nodo y finalmente se libera la memoria del nodo retirado.
int popLinked(LinkedStack *stack, StackItem *output) {
if (*stack == NULL) {
return 0; // Pila vacía
}
Node *temp = *stack;
*output = temp->data;
*stack = temp->next;
free(temp);
return 1; // Éxito
}
3.5 Otras Operaciones
int isLinkedStackEmpty(LinkedStack *stack) {
return *stack == NULL;
}
StackItem peekLinkedTop(LinkedStack *stack) {
if (*stack != NULL) {
return (*stack)->data;
}
// Manejo de error omitido
}
3.6 Ejemplo de Uso
int main() {
LinkedStack stack;
initLinkedStack(&stack);
pushLinked(&stack, 10);
pushLinked(&stack, 20);
pushLinked(&stack, 30);
StackItem value;
printf("Desapilando: ");
while (!isLinkedStackEmpty(&stack)) {
popLinked(&stack, &value);
printf("%d ", value);
}
printf("\n");
return 0;
}
La salida sería: 30 20 10.
- Relación con la Recursión
La recursión es un caso especial de subprograma que se invoca a sí mismo. La ejecución de funciones recursivas se gestiona mediante una pila interna mantenida por el sistema (la pila de llamadas). Cada invocación recursiva apila un nuevo marco de activación que contiene los parámetros, variables locales y la dirección de retorno. Cuando se alcanza el caso base, los marcos se van desapilando progresivamente, combinando los resultados parciales hasta obtener la solución final.
Un algoritmo clásico que ilustra este principio es el cálculo del factorial:
long factorial(int n) {
if (n <= 1) { // Caso base
return 1;
} else { // Paso recursivo
return n * factorial(n - 1);
}
}
La evaluación de factorial(4) genera una secuencia de llamadas que se apilan: factorial(4) -> factorial(3) -> factorial(2) -> factorial(1). Al retornar factorial(1), los resultados se propagan hacia abajo a través de la pila de llamadas.