Estructuras de datos en C: listas, colas y pilas estáticas y dinámicas

Estructuras de datos: implementaciones en C

1. Lista estática

Lista estática: los elementos se almacenan en un array de tamaño fijo MAX, y la posición del último elemento se controla mediante lastPos.

void createEmptyList(tList *L) {
    L->lastPos = LNULL;
}

bool isEmptyList(tList L) {
    return L.lastPos == LNULL;
}

bool insertItem(tItemL d, tPosL p, tList *L) {
    tPosL i;
    bool out = false;
    if (L->lastPos == MAX - 1) {
        return false;
    } else {
        L->lastPos++;

        if (p == LNULL) {
            L->data[L->lastPos] = d;
        } else {
            for (i = L->lastPos; i > p; i--) {
                L->data[i] = L->data[i - 1];
            }
            L->data[p] = d;
        }
        out = true;
    }
    return out;
}

void deleteAtPosition(tPosL p, tList *L) {
    for (tPosL i = p; i < L->lastPos; i++) {
        L->data[i] = L->data[i + 1];
    }
    L->lastPos--;
}

tItemL getItem(tPosL p, tList L) {
    return L.data[p];
}

void updateItem(tItemL d, tPosL p, tList *L) {
    L->data[p] = d;
}

tPosL findItem(tConsoleId id, tList L) {
    tPosL out = LNULL; // valor nulo por defecto
    tPosL p;
    for (p = 0; p <= L.lastPos && out == LNULL; p++) {
        if (strcmp(L.data[p].consoleId, id) == 0) {
            out = p;
        }
    }
    return out;
}

tPosL first(tList L) {
    return isEmptyList(L) ? LNULL : 0;
}

tPosL last(tList L) {
    return L.lastPos;
}

tPosL previous(tPosL p, tList L) {
    return !(isEmptyList(L) || p <= 0) ? p - 1 : LNULL;
}

tPosL next(tPosL p, tList L) {
    return (p >= 0 && p < L.lastPos) ? p + 1 : LNULL;
}

2. Cola estática circular

En una cola circular, el índice avanza de forma cíclica mediante la función addOne, aprovechando el espacio liberado al extraer elementos.

void createEmptyQueue(tQueue *Q) {
    Q->front = 0;
    Q->rear = QMAX - 1;
}

int addOne(int i) {
    return (i + 1) % QMAX;
}

bool isEmptyQueue(tQueue Q) {
    return Q.front == addOne(Q.rear);
}

bool enqueue(tItemQ item, tQueue *Q) {
    if (Q->front == addOne(addOne(Q->rear))) return false;
    Q->rear = addOne(Q->rear);
    Q->data[Q->rear] = item;
    return true;
}

void dequeue(tQueue *Q) {
    Q->front = addOne(Q->front);
}

tItemQ front(tQueue Q) {
    return Q.data[Q.front];
}

3. Cola estática

void createEmptyQueue(tQueue *Q) {
    Q->front = 0;
    Q->rear = QNULL;
}

bool isEmptyQueue(tQueue Q) {
    return Q.rear < Q.front;
}

bool enqueue(tItemQ item, tQueue *Q) {
    if (Q->rear < QMAX - 1) {
        Q->rear++;
        Q->data[Q->rear] = item;
        return true;
    }
    return false;
}

void dequeue(tQueue *Q) {
    if (!isEmptyQueue(*Q)) {
        Q->front++;
    }
}

tItemQ front(tQueue Q) {
    return Q.data[Q.front];
}

4. Cola dinámica

En la cola dinámica, cada elemento se almacena en un nodo reservado con malloc y liberado con free.

void createEmptyQueue(tQueue *Q) {
    Q->front = QNULL;
    Q->rear = QNULL;
}

bool isEmptyQueue(tQueue Q) {
    return Q.front == QNULL;
}

bool enqueue(tItemQ item, tQueue *Q) {
    tPosQ newNode = malloc(sizeof(struct tNodeQ));
    if (newNode == NULL) return false;
    newNode->item = item;
    newNode->next = QNULL;
    if (isEmptyQueue(*Q)) {
        Q->front = newNode;
    } else {
        Q->rear->next = newNode;
    }
    Q->rear = newNode;
    return true;
}

void dequeue(tQueue *Q) {
    if (!isEmptyQueue(*Q)) {
        tPosQ temp = Q->front;
        Q->front = Q->front->next;
        if (Q->front == QNULL) Q->rear = QNULL;
        free(temp);
    }
}

tItemQ front(tQueue Q) {
    return Q.front->item;
}

5. Pila estática

void createEmptyStack(tStack *S) {
    S->top = SNULL;
}

bool isEmptyStack(tStack S) {
    return S.top == SNULL;
}

bool push(tItemS d, tStack *S) {
    bool out = false;
    if (S->top >= SMAX - 1)
        out = false;
    else {
        S->top++;
        S->data[S->top] = d;
        out = true;
    }
    return out;
}

void pop(tStack *S) {
    S->top--;
}

tItemS peek(tStack S) {
    return S.data[S.top];
}

6. Pila dinámica

void createEmptyStack(tStack *S) {
    *S = SNULL;
}

bool allocateNode(tPosS *p) {
    *p = malloc(sizeof(struct tNodeS));
    return (*p != SNULL);
}

bool push(tItemS d, tStack *S) {
    tPosS node;
    if (!(allocateNode(&node)))
        return false;
    else {
        node->data = d;
        node->down = *S;
        *S = node;
        return true;
    }
}

void pop(tStack *S) {
    tPosS node;
    node = *S;
    *S = (*S)->down;
    free(node);
}

tItemS peek(tStack S) {
    return S->data;
}

bool isEmptyStack(tStack S) {
    return (S == SNULL);
}

7. Lista dinámica

La lista dinámica enlaza sus nodos mediante punteros next, lo que permite crecer sin un límite fijo de tamaño.

void createEmptyList(tList *L) {
    *L = LNULL;
}

bool allocateNode(tPosL *p) {
    *p = malloc(sizeof(struct tNode));
    return *p != LNULL;
}

bool isEmptyList(const tList L) {
    return L == LNULL;
}

bool insertItem(tItemL d, tPosL p, tList *L) {
    tPosL newNode;
    bool out = false;
    if (allocateNode(&newNode)) {
        newNode->data = d;
        newNode->next = LNULL;
        if (isEmptyList(*L)) {
            *L = newNode;
            out = true;
        } else {
            *newNode = *p;
            p->data = d;
            p->next = newNode;
            out = true;
        }
    }
    return out;
}

void deleteAtPosition(tPosL p, tList *L) {
    tPosL pos;
    if (!isEmptyList(*L) && p != LNULL) {
        if (p == *L) {
            *L = (*L)->next;
            free(p);
        } else if (p->next == LNULL) {
            pos = *L;
            while (pos->next != LNULL && pos->next != p) {
                pos = pos->next;
            }
            if (pos->next == p) {
                pos->next = LNULL;
                free(p);
            }
        } else {
            pos = p->next;
            p->data = pos->data;
            p->next = pos->next;
            free(pos);
        }
    }
}

tItemL getItem(tPosL p, tList L) {
    return p->data;
}

void updateItem(tItemL d, tPosL p, tList *L) {
    p->data = d;
}

tPosL findItem(tItemL item, tList L) {
    tPosL p;
    // recorremos hasta encontrar una coincidencia
    for (p = L; p != LNULL; p = p->next) {
        if (p->data == item) return p;
    }
    return LNULL;
}

tPosL first(tList L) {
    return L;
}

tPosL last(tList L) {
    while (L->next != LNULL) {
        L = L->next;
    }
    return L;
}

tPosL previous(tPosL p, tList L) {
    tPosL out = LNULL;
    tList prev;
    if (p != L) {
        prev = L;
        while (prev->next != LNULL && prev->next != p) {
            prev = prev->next;
        }
        out = prev->next == p ? prev : LNULL;
    }
    return out;
}

tPosL next(tPosL p, tList L) {
    return p->next;
}