batata/aed/3_Trabsons/Trab2/Parte_B/ex10/deque.c

#include "deque.h"

struct no {
    struct no *ant, *prox;
    int info;
};

struct deque {
    struct no *inicio, *final;
    int qtd;
};

Deque cria_deque()
{
    Deque dq = (Deque) malloc(sizeof(struct deque));
    if(dq != NULL) {
        dq->final  = NULL;
        dq->inicio = NULL;
        dq->qtd    = 0;
    }
    return dq;
}

int deque_vazio(Deque dq)
{
    if(dq == NULL || dq->inicio == NULL)
        return 1;
    return 0;
}

int insere_inicio(Deque dq, int elem)
{
    if(dq == NULL)
        return 0;

    Elem no = (Elem) malloc(sizeof(struct no));
    if(no == NULL)
        return 0;

    no->info = elem;
    no->prox = dq->inicio;
    no->ant = NULL;

    /* Caso Deque vazio */
    if(dq->inicio == NULL)
        dq->final = no;
    else
        dq->inicio->ant = no;

    dq->inicio = no;
    dq->qtd++;
    return 1;
}

int insere_final(Deque d, int n)
{
    if(d == NULL ) return 0;
    struct no *no = (struct no*)malloc(sizeof(struct no));
    if(no == NULL) return 0;

    no->info = n;
    no->prox = NULL;

    if(d->final == NULL){ //! deque vazio
        no->ant = NULL;
        d->inicio = no;
    }
    else{
        no->ant = d->final; //! no ant eh o novo final para que se insira o novo no final
        d->final->prox = no; //! o proximo no passa a ser o novo
    }
    d->final = no;
    d->qtd++;
    return 1;
}

int remove_inicio(Deque dq)
{
    if(dq == NULL || deque_vazio(dq))
        return 0;

    Elem no = dq->inicio;
    dq->inicio = dq->inicio->prox;
    if(dq->inicio == NULL)
        dq->final = NULL;
    else
        dq->final->ant = NULL;
    free(no);
    dq->qtd--;
    return 1;
}

int remove_final(Deque d)
{
    if(deque_vazio(d)==1) return 0;

    Elem no = d->final;
    if(no == d->inicio){ //! so tem um elemento
        d->inicio = NULL;
        d->final = NULL;
    }else{
        no->ant->prox = NULL;
        d->final = no->ant;
    }
    free(no);
    d->qtd--;
    return 1;
}

int imprime_deque(Deque dq)
{
    Elem no = dq->inicio;
    printf("Deque:\n\t{ ");
    while(no != NULL) {
        printf("%d ", no->info);
        no = no->prox;
    }
    printf("}\n");
    return 1;
}