/*
 •	*Создать очередь на основе двусвязного списка.
 •	**Создать стек на основе двусвязного списка.
 */


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

#define T int
#define QMAX 100


typedef struct Node {
    T payload;
    struct Node *prev;
    struct Node *next;
    
} Node;

Node *newNode() {
    Node *n = (Node*)malloc(sizeof(Node));
    if (n == NULL) {
        puts("Out of memory!");
        return n;
    }
    n->prev = NULL;
    n->next = NULL;
    
    return n;
}


typedef struct Queue {
    Node *recent;
    Node *oldest;
    int size;
    
} Queue;

Queue newQueue() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL) {
        puts("Out of memory!");
        return *q;
    }
    q->recent = NULL;
    q->oldest = NULL;
    q->size = 0;
    return *q;
}

void qPush(T val, Queue *q){
    if (q->size >= QMAX){
        puts("Queue is full! Do some cleanup first!");
        return;
    }
    Node *tmp = newNode();
    tmp->payload = val;
    
    if (q->oldest == NULL)
         q->oldest = tmp;
    else if (q->recent == NULL) {
        tmp->prev = q->oldest;
        q->oldest->next = tmp;
        q->recent = tmp;
    } else {
        tmp->prev = q->recent;
        q->recent->next = tmp;
        q->recent = tmp;
       
    }
    q->size++;
}
T qPop(Queue *q){
    if (q->oldest == NULL) {
        puts("Queue is empty");
        return 0;
    }
    
    Node *tmp = q->oldest;
    T val = tmp->payload;
    if (&q->oldest == &q->recent || q->recent == NULL) {
        free(q->recent);
        free(q->oldest);
    } else {
        q->oldest = q->oldest->next;
    }
    
    q->size--;
    free(tmp);
    return val;
};

int bilen(long n) { //calculates length of a binary representation of a dec number
    return (int)(log(n)/0.693147 + 1);  //0.693147 == log(2);
}

void goida(Node *n) {
    if(!n){
        puts("It's empty!");
        return;
    }
    printf("Paylod is %2d! GOIDA!\n", n->payload);
    if (n->next != NULL) goida(n->next);
        
}


void l7(){
    printf("binary representation of 512 have length of %d\n", bilen(512));
    printf("binary representation of 511 have length of %d\n", bilen(511));
    Queue q = newQueue();
    int i =0;
    for(i = 0; i < 105; i++) qPush(i, &q);
    Queue q2 = newQueue();
    goida(q2.oldest);
    goida(q.oldest);
    for (i = 0; i < 101; i++ ) printf("Goida! %d!\n", qPop(&q));
    
    goida(q.oldest);

    printf("size of q: %d\n", q.size);
    printf("size of q: %d\n", q.size);

}

int main(int argc, const char * argv[]) {
    
    l7();
    
    puts("");
    return 0;
}