4. Pilas y Colas

#estructuraDeDatos #universidad

a. Concepto de Pila

Una pila 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. Imagina una pila de platos: solo puedes añadir o quitar platos del tope de la pila.

Características de una Pila:

• LIFO: Último en entrar, primero en salir.
• Operaciones Principales:
  • Push: Agregar un elemento al tope de la pila.
  • Pop: Remover el elemento del tope de la pila.
  • Peek/Top: Obtener el elemento del tope sin removerlo.
  • IsEmpty: Verificar si la pila está vacía.

b. Representación Gráfica de Pila

| 5 | ← Tope (Top)
| 4 |
| 3 |
| 2 |
| 1 | ← Base (Bottom)

c. Operaciones de la Pila

1. Push: Añade un elemento al tope.
2. Pop: Remueve y retorna el elemento del tope.
3. Peek/Top: Retorna el elemento del tope sin removerlo.
4. IsEmpty: Retorna verdadero si la pila está vacía.

d. Implementación de una Pila en Lenguaje C

Implementación Usando un Arreglo (Estructura Estática)

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

typedef struct {
    int datos[MAX];
    int cima;
} Pila;

// Inicializar la pila
void inicializarPila(Pila *p) {
    p->cima = -1;
}

// Verificar si la pila está vacía
int estaVacia(Pila *p) {
    return p->cima == -1;
}

// Verificar si la pila está llena
int estaLlena(Pila *p) {
    return p->cima == MAX - 1;
}

// Push: Agregar un elemento al tope
void push(Pila *p, int elemento) {
    if (estaLlena(p)) {
        printf("Error: Pila llena.\n");
    } else {
        p->datos[++(p->cima)] = elemento;
    }
}

// Pop: Remover y retornar el elemento del tope
int pop(Pila *p) {
    if (estaVacia(p)) {
        printf("Error: Pila vacía.\n");
        return -1; // Indicador de error
    } else {
        return p->datos[(p->cima)--];
    }
}

// Peek: Obtener el elemento del tope sin removerlo
int peek(Pila *p) {
    if (estaVacia(p)) {
        printf("Error: Pila vacía.\n");
        return -1; // Indicador de error
    } else {
        return p->datos[p->cima];
    }
}

// Ejemplo de uso
int main() {
    Pila p;
    inicializarPila(&p);
    
    push(&p, 10);
    push(&p, 20);
    push(&p, 30);
    
    printf("Elemento en el tope: %d\n", peek(&p)); // Imprime 30
    
    printf("Elemento removido: %d\n", pop(&p)); // Remueve 30
    printf("Nuevo elemento en el tope: %d\n", peek(&p)); // Imprime 20
    
    return 0;
}

Implementación Usando una Lista Enlazada (Estructura Dinámica)

#include <stdio.h>
#include <stdlib.h>

// Definición del nodo de la pila
typedef struct Nodo {
    int dato;
    struct Nodo *siguiente;
} Nodo;

// Inicializar la pila (apunta al tope)
Nodo* inicializarPila() {
    return NULL;
}

// Verificar si la pila está vacía
int estaVacia(Nodo *tope) {
    return tope == NULL;
}

// Push: Agregar un elemento al tope
Nodo* push(Nodo *tope, int elemento) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    if (!nuevo) {
        printf("Error en la asignación de memoria.\n");
        exit(1);
    }
    nuevo->dato = elemento;
    nuevo->siguiente = tope;
    return nuevo;
}

// Pop: Remover y retornar el elemento del tope
Nodo* pop(Nodo **tope, int *elemento) {
    if (estaVacia(*tope)) {
        printf("Error: Pila vacía.\n");
        return NULL;
    }
    Nodo *temp = *tope;
    *elemento = temp->dato;
    *tope = temp->siguiente;
    free(temp);
    return *tope;
}

// Peek: Obtener el elemento del tope sin removerlo
int peek(Nodo *tope) {
    if (estaVacia(tope)) {
        printf("Error: Pila vacía.\n");
        return -1; // Indicador de error
    }
    return tope->dato;
}

// Ejemplo de uso
int main() {
    Nodo *tope = inicializarPila();
    
    tope = push(tope, 10);
    tope = push(tope, 20);
    tope = push(tope, 30);
    
    printf("Elemento en el tope: %d\n", peek(tope)); // Imprime 30
    
    int elemento;
    tope = pop(&tope, &elemento);
    printf("Elemento removido: %d\n", elemento); // Remueve 30
    printf("Nuevo elemento en el tope: %d\n", peek(tope)); // Imprime 20
    
    return 0;
}

e. Concepto de Cola

Una cola es una estructura de datos lineal que sigue el principio FIFO (First In, First Out), es decir, el primer elemento en entrar es el primero en salir. Imagina una fila en un banco: el primero que llega es el primero en ser atendido.

Características de una Cola:

• FIFO: Primero en entrar, primero en salir.
• Operaciones Principales:
  • Enqueue: Agregar un elemento al final de la cola.
  • Dequeue: Remover el elemento al frente de la cola.
  • Front/Peek: Obtener el elemento al frente sin removerlo.
  • IsEmpty: Verificar si la cola está vacía.

f. Representación Gráfica de Cola

Frente (Front) → | 1 | ← Final (Rear)
| 2 |
| 3 |
| 4 |
| 5 |

g. Operaciones de la Cola

1. Enqueue: Añade un elemento al final de la cola.
2. Dequeue: Remueve y retorna el elemento al frente de la cola.
3. Peek/Front: Retorna el elemento al frente sin removerlo.
4. IsEmpty: Retorna verdadero si la cola está vacía.

h. Implementación de una Cola en Lenguaje C

Implementación Usando un Arreglo (Estructura Estática)

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

typedef struct {
    int datos[MAX];
    int frente;
    int final;
} Cola;

// Inicializar la cola
void inicializarCola(Cola *c) {
    c->frente = -1;
    c->final = -1;
}

// Verificar si la cola está vacía
int estaVacia(Cola *c) {
    return c->frente == -1;
}

// Verificar si la cola está llena
int estaLlena(Cola *c) {
    return c->final == MAX - 1;
}

// Enqueue: Agregar un elemento al final
void enqueue(Cola *c, int elemento) {
    if (estaLlena(c)) {
        printf("Error: Cola llena.\n");
    } else {
        if (estaVacia(c)) {
            c->frente = 0;
        }
        c->datos[++(c->final)] = elemento;
    }
}

// Dequeue: Remover y retornar el elemento al frente
int dequeue(Cola *c) {
    if (estaVacia(c)) {
        printf("Error: Cola vacía.\n");
        return -1; // Indicador de error
    } else {
        int elemento = c->datos[c->frente];
        if (c->frente >= c->final) {
            c->frente = -1;
            c->final = -1;
        } else {
            c->frente++;
        }
        return elemento;
    }
}

// Peek: Obtener el elemento al frente sin removerlo
int peek(Cola *c) {
    if (estaVacia(c)) {
        printf("Error: Cola vacía.\n");
        return -1; // Indicador de error
    } else {
        return c->datos[c->frente];
    }
}

// Ejemplo de uso
int main() {
    Cola c;
    inicializarCola(&c);
    
    enqueue(&c, 10);
    enqueue(&c, 20);
    enqueue(&c, 30);
    
    printf("Elemento al frente: %d\n", peek(&c)); // Imprime 10
    
    printf("Elemento removido: %d\n", dequeue(&c)); // Remueve 10
    printf("Nuevo elemento al frente: %d\n", peek(&c)); // Imprime 20
    
    return 0;
}

Implementación Usando una Lista Enlazada (Estructura Dinámica)

#include <stdio.h>
#include <stdlib.h>

// Definición del nodo de la cola
typedef struct Nodo {
    int dato;
    struct Nodo *siguiente;
} Nodo;

// Definición de la cola con frente y final
typedef struct {
    Nodo *frente;
    Nodo *final;
} Cola;

// Inicializar la cola
void inicializarCola(Cola *c) {
    c->frente = NULL;
    c->final = NULL;
}

// Verificar si la cola está vacía
int estaVacia(Cola *c) {
    return c->frente == NULL;
}

// Enqueue: Agregar un elemento al final
void enqueue(Cola *c, int elemento) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    if (!nuevo) {
        printf("Error en la asignación de memoria.\n");
        exit(1);
    }
    nuevo->dato = elemento;
    nuevo->siguiente = NULL;
    
    if (estaVacia(c)) {
        c->frente = nuevo;
        c->final = nuevo;
    } else {
        c->final->siguiente = nuevo;
        c->final = nuevo;
    }
}

// Dequeue: Remover y retornar el elemento al frente
int dequeue(Cola *c) {
    if (estaVacia(c)) {
        printf("Error: Cola vacía.\n");
        return -1; // Indicador de error
    }
    Nodo *temp = c->frente;
    int elemento = temp->dato;
    c->frente = c->frente->siguiente;
    if (c->frente == NULL) {
        c->final = NULL;
    }
    free(temp);
    return elemento;
}

// Peek: Obtener el elemento al frente sin removerlo
int peek(Cola *c) {
    if (estaVacia(c)) {
        printf("Error: Cola vacía.\n");
        return -1; // Indicador de error
    }
    return c->frente->dato;
}

// Ejemplo de uso
int main() {
    Cola c;
    inicializarCola(&c);
    
    enqueue(&c, 10);
    enqueue(&c, 20);
    enqueue(&c, 30);
    
    printf("Elemento al frente: %d\n", peek(&c)); // Imprime 10
    
    printf("Elemento removido: %d\n", dequeue(&c)); // Remueve 10
    printf("Nuevo elemento al frente: %d\n", peek(&c)); // Imprime 20
    
    return 0;
}

i. Resumen de Pilas y Colas

• Pila: LIFO, operaciones principales son Push y Pop.
• Cola: FIFO, operaciones principales son Enqueue y Dequeue.
• Implementaciones: Pueden ser estáticas (arreglos) o dinámicas (listas enlazadas).

Ejercicios

1. Implementación de una Cola Circular:

   • Implementa una cola circular utilizando un arreglo en C. Asegúrate de manejar correctamente los casos de desbordamiento y subdesbordamiento.

2. Aplicación de Pilas:

   • Escribe un programa en C que verifique si una expresión matemática tiene paréntesis balanceados utilizando una pila.

   Ejemplo:

   • ((a+b)*c) → Balanceado.
   • ((a+b) → No balanceado.