Las pilas y las colas son dos estructuras de datos lineales esenciales, caracterizadas por restricciones específicas en las operaciones de inserción y eliminación.

Conceptos Generales

En una lista lineal, las operaciones de inserción y eliminación pueden ocurrir en cualquier posición:

Operación Insertar(Lista, Posición, Elemento)
Operación Eliminar(Lista, Posición)
 

Pilas (Stack)

Las pilas operan bajo el principio LIFO (Last In, First Out): el último elemento en entrar es el primero en salir.

Operaciones típicas:

• Push (Apilar): Inserta un elemento en la cima de la pila.
• Pop (Desapilar): Elimina el elemento de la cima de la pila.

Se pueden implementar mediante arrays (pilas secuenciales) o listas enlazadas (pilas enlazadas).

Implementación con Array (Pila Secuencial)

Se utiliza un array para almacenar los elementos y un índice para rastrear la cima.

#define MAX_SIZE 100

typedef struct {
   int datos[MAX_SIZE];
   int cima; // Índice del elemento superior
} PilaArray;

// Inicializa una pila vacía
PilaArray* inicializarPilaArray() {
   PilaArray* p = (PilaArray*)malloc(sizeof(PilaArray));
   if (p == NULL) {
       return NULL;
   }
   p->cima = -1; // Inicialmente, la pila está vacía
   return p;
}

// Añade un elemento a la cima de la pila
void apilar(PilaArray* p, int valor) {
   if (p->cima < MAX_SIZE - 1) {
       p->datos[++(p->cima)] = valor;
   }
   // Manejar error si la pila está llena
}

// Elimina el elemento de la cima de la pila
void desapilar(PilaArray* p) {
   if (p->cima != -1) {
       p->cima--;
   }
   // Manejar error si la pila está vacía
}

// Obtiene el elemento en la cima sin eliminarlo
int obtenerCima(PilaArray* p) {
   if (p->cima != -1) {
       return p->datos[p->cima];
   }
   // Manejar error si la pila está vacía
   return -1; // Valor de error o lanzar excepción
}

// Comprueba si la pila está vacía
bool estaVacia(PilaArray* p) {
   return p->cima == -1;
}

// Comprueba si la pila está llena
bool estaLlena(PilaArray* p) {
   return p->cima == MAX_SIZE - 1;
}
 

Implementación con Lista Enlazada (Pila Enlazada)

Cada nodo apunta al siguiente, y la cima es el primer nodo de la lista.

typedef struct NodoPila {
   int dato;
   struct NodoPila* siguiente;
} NodoPila;

// Inicializa una pila vacía (representada por el puntero a la cima)
NodoPila* inicializarPilaEnlazada() {
   return NULL; // La pila vacía es representada por NULL
}

// Comprueba si la pila está vacía
bool estaVaciaEnlazada(NodoPila* cima) {
   return cima == NULL;
}

// Añade un elemento a la cima de la pila
NodoPila* apilarEnlazada(NodoPila* cima, int valor) {
   NodoPila* nuevoNodo = (NodoPila*)malloc(sizeof(NodoPila));
   if (nuevoNodo == NULL) {
       // Manejar error de asignación de memoria
       return cima;
   }
   nuevoNodo->dato = valor;
   nuevoNodo->siguiente = cima; // El nuevo nodo apunta a la antigua cima
   return nuevoNodo; // El nuevo nodo se convierte en la nueva cima
}

// Elimina el elemento de la cima de la pila
NodoPila* desapilarEnlazada(NodoPila* cima) {
   if (cima == NULL) {
       // Manejar error: intentar desapilar de una pila vacía
       return NULL;
   }
   NodoPila* temp = cima;
   cima = cima->siguiente; // Avanza la cima al siguiente nodo
   free(temp); // Libera el nodo desapilado
   return cima;
}

// Obtiene el elemento en la cima sin eliminarlo
int obtenerCimaEnlazada(NodoPila* cima) {
   if (cima == NULL) {
       // Manejar error: pila vacía
       return -1; // Valor de error o lanzar excepción
   }
   return cima->dato;
}
 

Colas (Queue)

Las colas operan bajo el principio FIFO (First In, First Out): el primer elemento en entrar es el primero en salir.

Operaciones típicas:

• Enqueue (Encolar): Inserta un elemento al final (cola) de la cola.
• Dequeue (Desencolar): Elimina el elemento del frente (cabeza) de la cola.

Se pueden implementar mediante arrays (colas secuenciales, a menudo circulares) o listas enlazadas (colas enlazadas).

Implementación con Array (Cola Circular)

Una cola circular utiliza un array y dos índices (frente y fin) que se "envuelven" al llegar al final del array, optimizando el uso del espacio.

Los detalles de implementación de colas circulares se omiten aquí para brevedad, pero implican el uso del operador módulo (%) para manejar el desbordamiento de índices.

Implementación con Lista Enlazada (Cola Enlazada)

Se utilizan punteros tanto para la cabeza (frente) como para la cola (fin) de la lista enlazada para permitir operaciones eficientes en ambos extremos.

Los detalles de implementación de colas enlazadas también se omiten aquí.

Comparación de Implementaciones

Pilas

• Pila Enlazada: Ventajas - tamaño dinámico, no hay límite preedfinido. Desventajas - sobrecarga de memoria por punteros, acceso O(n) en teoría (aunque para pila es O(1)).
• Pila de Array: Ventajas - acceso O(1) a elementos (si se conoce el índice), buena localidad de caché. Desventajas - tamaño fijo (requiere redimensionamiento si se llena), inserciones/eliminaciones pueden ser O(n) si se requiere mover datos (no es el caso típico de pila).

Colas

Similarmente, las colas enlazadas ofrecen flexibilidad de tamaño, mientras que las colas de array (especialmente circulares) pueden ser más eficientes en uso de memoria y acceso si el tamaño es conocido y se maneja correctamente el desbordamiento.