Estructuras de Datos Abstractas en Lenguaje C

En este espacio, exploraremos algunos de los fundamentos de la programación en C, incluyendo cómo trabajar con estructuras de datos, colas y pilas, y cómo implementar un diccionario en C.

¿Alguna vez has querido organizar grandes cantidades de datos, pero no sabes por dónde empezar? ¡No te preocupes! Las estructuras de datos son una herramienta clave para almacenar y organizar datos de manera efectiva. En nuestra primera serie de publicaciones, discutiremos diferentes tipos de estructuras de datos, incluyendo matrices, listas enlazadas, colas y pilas, y te mostraremos cómo se pueden utilizar para solucionar problemas prácticos en tu vida cotidiana.

Pero, ¿qué son exactamente las colas y las pilas? Aprenderás cómo se pueden utilizar estas estructuras de datos en aplicaciones cotidianas, como la gestión de la lista de espera en un restaurante o el control de la historia de navegación en tu navegador web. También hablaremos sobre los conceptos de FIFO y LIFO, que son importantes para entender cómo se usan las colas y las pilas.

Finalmente, exploraremos cómo se puede implementar un diccionario en C. Si alguna vez has necesitado almacenar pares clave-valor, entonces un diccionario es una herramienta esencial para ti. Discutiremos cómo se puede utilizar un diccionario para buscar y agregar elementos de manera eficiente en tu programa.

¡Esperamos que te hayas emocionado por aprender más sobre programación en C! Si te gustaría seguir aprendiendo sobre estos temas y muchos más, asegúrate de seguir nuestro blog para más publicaciones emocionantes. ¡Te esperamos!

En esta clase, exploraremos algunos de los fundamentos de la programación en C, incluyendo cómo trabajar con estructuras de datos, como colas y pilas, y cómo implementar un diccionario en C.

En primer lugar, discutiremos las estructuras de datos, que son herramientas fundamentales para organizar y almacenar datos en programas de computadora. Hablaremos sobre las diferencias entre los diferentes tipos de estructuras de datos, incluyendo las matrices, las listas enlazadas, las colas y las pilas, y veremos algunos ejemplos de cómo se pueden usar estas estructuras de datos en aplicaciones cotidianas.

Luego, nos centraremos en dos tipos específicos de estructuras de datos: las colas y las pilas. Discutiremos cómo funcionan estas estructuras de datos, cómo se implementan en C y cómo se pueden utilizar para resolver problemas prácticos. También hablaremos sobre los conceptos de FIFO y LIFO, que son importantes para entender cómo se usan las colas y las pilas.

Finalmente, exploraremos la implementación de un diccionario en C. Un diccionario es una estructura de datos que permite almacenar y buscar pares clave-valor, y es una herramienta comúnmente utilizada en muchos programas de computadora. Discutiremos cómo se puede implementar un diccionario en C, incluyendo cómo manejar la inserción y búsqueda de elementos.

Al final de esta clase, los estudiantes tendrán una comprensión sólida de los conceptos fundamentales de la programación en C y estarán preparados para aplicarlos en la solución de problemas prácticos en el futuro.

Las colas son estructuras de datos útiles en una amplia variedad de aplicaciones del mundo real, especialmente en situaciones donde los procesos deben ser ordenados y atendidos de manera justa. A continuación, te doy algunos ejemplos de uso cotidiano de colas:

    Servicio al cliente: Las colas se utilizan comúnmente en los servicios de atención al cliente. Por ejemplo, cuando los clientes llegan a una ventanilla de servicio, se agregan a una cola y son atendidos en el orden en que llegaron a la cola.

    Procesamiento de tareas: Las colas se utilizan a menudo en sistemas informáticos para procesar tareas en un orden justo. Por ejemplo, un sistema de procesamiento de solicitudes de empleo puede usar una cola para asegurarse de que cada solicitud se procese en el orden en que se recibió.

    Procesamiento de mensajes: Las colas también se utilizan en sistemas de mensajería para garantizar que los mensajes se procesen en el orden correcto. Por ejemplo, en una aplicación de mensajería, los mensajes se pueden agregar a una cola y luego se envían en el orden en que llegaron a la cola.

    Impresión de documentos: Las colas se utilizan a menudo en las impresoras para procesar documentos en el orden en que se recibieron. Los documentos se agregan a una cola y se imprimen en el orden en que llegaron a la cola.

Estructuras de Datos Abstractas en Lenguaje C

Una estructura de datos abstracta es un tipo de datos que se define mediante sus operaciones, sin especificar cómo se implementan esas operaciones. Por ejemplo, una cola es una estructura de datos abstracta que se define por sus operaciones de encolar y desencolar elementos, pero no se especifica cómo se implementan esas operaciones. La implementación de una cola puede ser basada en un array, una lista enlazada, o cualquier otra estructura de datos.

En C, una forma común de implementar una cola es utilizando una lista enlazada. Cada nodo en la lista contiene un elemento y un puntero al siguiente nodo en la lista. Para encolar un elemento, se crea un nuevo nodo con el elemento y se agrega al final de la lista. Para desencolar un elemento, se elimina el primer nodo de la lista y se devuelve su elemento.

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

struct node {
    int data;
    struct node *next;
};

struct queue {
    struct node *front;
    struct node *rear;
};

void enqueue(struct queue *q, int data) {
    struct node *new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = new_node;
        return;
    }
    q->rear->next = new_node;
    q->rear = new_node;
}

int dequeue(struct queue *q) {
    if (q->front == NULL) {
        printf("Queue is empty");
        return -1;
    }
    struct node *temp = q->front;
    int data = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return data;
}

int main() {
    struct queue q = {NULL, NULL};
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("%d dequeued from queue\n", dequeue(&q));
    return 0;
}

Este código define una cola utilizando una lista enlazada. La estructura node representa un nodo en la lista, con un campo data para almacenar el elemento y un puntero next al siguiente nodo en la lista. La estructura queue contiene punteros al primer y último nodos de la lista, lo que nos permite agregar y eliminar elementos en la cola eficientemente.

La función enqueue agrega un elemento al final de la cola. Primero se crea un nuevo nodo y se inicializa con el elemento. Si la cola está vacía, el nuevo nodo se convierte en el primer y último nodo de la cola. Si la cola ya tiene elementos, el nuevo nodo se agrega al final de la lista, y el puntero rear se actualiza para apuntar al nuevo último nodo.

La función dequeue elimina y devuelve el primer elemento de la cola. Si la cola está vacía, se imprime un mensaje de error y se devuelve un valor de sentinela (en este caso, -1). De lo contrario, se elimina el primer nodo de la lista y se devuelve su elemento. El puntero front se actualiza para apuntar al siguiente nodo en la lista, y si la cola queda vacía, el puntero rear se actualiza para reflejar ese estado.

El programa principal en el código que te di muestra cómo usar la cola que se ha implementado. En particular, el programa agrega tres elementos a la cola usando la función enqueue y luego los elimina y muestra en orden utilizando la función dequeue.

El output esperado del programa es:

10 dequeued from queue
20 dequeued from queue
30 dequeued from queue
Queue is empty
-1 dequeued from queue

Esto significa que los elementos 10, 20 y 30 se agregaron a la cola en ese orden, y luego se eliminaron de la cola en ese orden y se imprimieron en la pantalla. El mensaje "Queue is empty" se muestra cuando la cola ya está vacía y se intenta eliminar otro elemento. El valor -1 se devuelve en lugar del elemento porque no hay más elementos en la cola.

FIFO

FIFO es un acrónimo en inglés que significa "First In, First Out" (primero en entrar, primero en salir) y se refiere a la forma en que se manejan los elementos en una cola.

En una cola FIFO, los elementos se agregan al final de la cola y se eliminan del frente de la cola. Es decir, el primer elemento que se agregó a la cola es el primero en salir. Esto se conoce como el principio de FIFO.

Por ejemplo, si tenemos una cola con los elementos 1, 2, 3 en ese orden, y queremos eliminar elementos de la cola, primero se eliminará el elemento 1 (el primero en llegar), luego el elemento 2 y finalmente el elemento 3. Si agregamos un nuevo elemento 4 a la cola, este se agregará al final y se convertirá en el último elemento en la cola.

El principio de FIFO se utiliza comúnmente en la gestión de procesos, en la programación de sistemas informáticos y en muchas otras aplicaciones donde es importante atender los procesos en un orden justo y determinado.

Enqueue y Dequeue

enqueue y dequeue son operaciones básicas que se utilizan en las estructuras de datos que siguen el principio de FIFO, como las colas.

    enqueue: es la operación que se utiliza para agregar un elemento al final de la cola. Es decir, se inserta un nuevo elemento al final de la cola, después de todos los demás elementos.

    dequeue: es la operación que se utiliza para eliminar el primer elemento de la cola, es decir, el elemento que ha estado en la cola por más tiempo. Al eliminar el primer elemento, el segundo elemento se convierte en el nuevo primer elemento de la cola.

En otras palabras, enqueue agrega un nuevo elemento a la cola mientras que dequeue elimina el primer elemento de la cola.

Cada vez que se agrega un elemento a la cola, este se convierte en el último elemento y cada vez que se elimina un elemento, el siguiente elemento se convierte en el primer elemento de la cola. Por lo tanto, enqueue y dequeue se utilizan en conjunto para administrar los elementos en una cola FIFO.

Las operaciones de enqueue y dequeue son fundamentales para las estructuras de datos basadas en colas, ya que proporcionan la capacidad de agregar y eliminar elementos en un orden determinado y justo. Estas operaciones son utilizadas en muchas aplicaciones del mundo real, como sistemas de procesamiento de tareas, servicios al cliente, sistemas de mensajería, etc.

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

#define MAX_SIZE 100

// Estructura de la cola
struct Queue {
   int items[MAX_SIZE];
   int front;
   int rear;
};

// Función para crear una cola vacía
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

// Función para verificar si la cola está vacía
int isEmpty(struct Queue* queue) {
    if(queue->rear == -1)
        return 1;
    else
        return 0;
}

// Función para agregar un elemento a la cola
void enqueue(struct Queue* queue, int value) {
    if(queue->rear == MAX_SIZE-1)
        printf("La cola está llena \n");
    else {
        if(queue->front == -1)
            queue->front = 0;
        queue->rear++;
        queue->items[queue->rear] = value;
        printf("Elemento encolado: %d\n", value);
    }
}

// Función para eliminar un elemento de la cola
int dequeue(struct Queue* queue) {
    int item;
    if(isEmpty(queue)) {
        printf("La cola está vacía\n");
        return -1;
    }
    else {
        item = queue->items[queue->front];
        queue->front++;
        if(queue->front > queue->rear) {
            queue->front = -1;
            queue->rear = -1;
        }
        printf("Elemento desencolado: %d\n", item);
        return item;
    }
}

int main() {
    struct Queue* queue = createQueue();

    // Agregamos elementos a la cola
    enqueue(queue, 1);
    enqueue(queue, 2);
    enqueue(queue, 3);

    // Eliminamos elementos de la cola
    dequeue(queue);
    dequeue(queue);
    dequeue(queue);

    return 0;
}

En la función principal, se crean una cola y se agregan elementos usando enqueue(). Luego, se eliminan los elementos de la cola usando dequeue(). En este ejemplo, el resultado en la consola será:

Elemento encolado: 1
Elemento encolado: 2
Elemento encolado: 3
Elemento desencolado: 1
Elemento desencolado: 2
Elemento desencolado: 3

LIFO

En programación, una pila (stack en inglés) es una estructura de datos lineal que sigue una política de LIFO (Last In, First Out) o último en entrar, primero en salir.

En una pila, los elementos se insertan y se eliminan desde un extremo, que se llama la cima o el tope de la pila. El último elemento que se insertó en la pila se encuentra en la cima, y los elementos más antiguos se encuentran debajo de él.

La operación de inserción se llama "push" y la operación de eliminación se llama "pop". También es común tener una operación adicional llamada "peek" que devuelve el elemento en la cima de la pila sin eliminarlo.

 

Pilas en Lenguaje C

Las pilas se utilizan comúnmente en programación para implementar operaciones que requieren una reversión de orden de procesamiento. Por ejemplo, las pilas se utilizan en la implementación de funciones recursivas, para evaluar expresiones matemáticas en notación polaca inversa, en navegadores web para implementar el historial de navegación hacia atrás y en muchos otros casos.

Aquí hay un ejemplo de código simple en C que implementa una pila:

c

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

#define MAX_SIZE 100

// Estructura de la pila
struct Stack {
   int items[MAX_SIZE];
   int top;
};

// Función para crear una pila vacía
struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    return stack;
}

// Función para verificar si la pila está vacía
int isEmpty(struct Stack* stack) {
    if(stack->top == -1)
        return 1;
    else
        return 0;
}

// Función para agregar un elemento a la pila
void push(struct Stack* stack, int value) {
    if(stack->top == MAX_SIZE-1)
        printf("La pila está llena \n");
    else {
        stack->top++;
        stack->items[stack->top] = value;
        printf("Elemento apilado: %d\n", value);
    }
}

// Función para eliminar un elemento de la pila
int pop(struct Stack* stack) {
    int item;
    if(isEmpty(stack)) {
        printf("La pila está vacía\n");
        return -1;
    }
    else {
        item = stack->items[stack->top];
        stack->top--;
        printf("Elemento desapilado: %d\n", item);
        return item;
    }
}

int main() {
    struct Stack* stack = createStack();

    // Agregamos elementos a la pila
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);

    // Eliminamos elementos de la pila
    pop(stack);
    pop(stack);
    pop(stack);

    return 0;
}

En este ejemplo, se define una estructura Stack que contiene una matriz de elementos y un puntero top. La pila se implementa como una matriz, donde top se utiliza para realizar un seguimiento del elemento en la cima de la pila.

En la función createStack(), se crea una pila vacía con top inicializado a -1. La función isEmpty() verifica si la pila está vacía o no.

La función push() agrega un elemento a la pila si la pila no está llena. Primero, se verifica si la pila está llena. Si la pila no está llena, top se incrementa y el elemento se agrega a la matriz en la posición correspondiente a la cima de la pila.

La función pop() elimina y devuelve el elemento en la cima de la pila si la pila no está vacía. Primero, se verifica si la pila está vacía. Si la pila no está vacía, el elemento en la cima de la pila se elimina de la matriz y se devuelve.

En el main(), se crea una pila y se agregan algunos elementos a la pila utilizando la función push(). Luego, algunos elementos se eliminan de la pila utilizando la función pop().

Cabe destacar que esta implementación es muy básica y no es la única manera de implementar una pila en C. En aplicaciones reales, es posible que se requieran implementaciones más sofisticadas para cumplir con requisitos específicos.

Diccionarios en C

En C, no existe una estructura de datos llamada "diccionario" como en otros lenguajes de programación de alto nivel, pero se pueden implementar usando estructuras y punteros. En general, un diccionario en programación es una estructura de datos que permite almacenar y recuperar pares clave-valor.

Por ejemplo, en C, podrías implementar un diccionario como una estructura que contiene dos matrices, una para almacenar las claves y otra para almacenar los valores. Luego, podrías usar funciones para insertar, buscar y eliminar elementos en el diccionario utilizando las claves como referencia.

Aquí hay un ejemplo de cómo podrías implementar un diccionario en C usando una estructura y punteros:

c

#include <stdio.h>
#include <string.h>

#define MAX_KEYS 100

struct dict {
    char *keys[MAX_KEYS];
    int values[MAX_KEYS];
    int size;
};

void init(struct dict *d) {
    d->size = 0;
}

int get(struct dict *d, char *key) {
    for (int i = 0; i < d->size; i++) {
        if (strcmp(d->keys[i], key) == 0) {
            return d->values[i];
        }
    }
    return -1;
}

void put(struct dict *d, char *key, int value) {
    for (int i = 0; i < d->size; i++) {
        if (strcmp(d->keys[i], key) == 0) {
            d->values[i] = value;
            return;
        }
    }
    d->keys[d->size] = key;
    d->values[d->size] = value;
    d->size++;
}

int main() {
    struct dict d;
    init(&d);

    put(&d, "one", 1);
    put(&d, "two", 2);
    put(&d, "three", 3);

    printf("Value for key 'one': %d\n", get(&d, "one"));
    printf("Value for key 'two': %d\n", get(&d, "two"));
    printf("Value for key 'three': %d\n", get(&d, "three"));

    return 0;
}

En este ejemplo, la estructura dict contiene dos matrices, una para almacenar las claves (keys) y otra para almacenar los valores (values). La función init() se utiliza para inicializar un diccionario vacío y la función get() se utiliza para buscar el valor de una clave. La función put() se utiliza para agregar un par clave-valor al diccionario o actualizar el valor existente para una clave existente.

En el main(), se crea un diccionario vacío, se agregan algunos pares clave-valor al diccionario y se busca el valor de algunas claves.

Cabe destacar que esta implementación es muy básica y no es la única manera de implementar un diccionario en C. En aplicaciones reales, es posible que se requieran implementaciones más sofisticadas para cumplir con requisitos específicos.