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

struct lifo
{
    struct lifo *next;
    int         value;
};

struct fifo
{
    struct lifo *head;
    struct lifo *tail;
};

void
push(struct lifo **head, struct lifo *e)
{
    assert(e);

    e->next = *head;
    *head = e;
}

struct lifo *
pop(struct lifo **head)
{
    assert(head);

    if (!*head)
        return NULL;
    struct lifo *e = *head;
    *head = e->next;
    return e;
}

void
print(struct lifo *head)
{
    for (; head; head = head->next)
        printf("%d ", head->value);
    printf("\n");
}


void
enqueue(struct fifo *queue, int value)
{
    struct lifo *new_head = calloc(1, sizeof(*new_head));
    new_head->value = value;
    push(&queue->head, new_head);

    struct lifo *new_tail = calloc(1, sizeof(*new_head));
    new_tail->value = value;
    if (!queue->tail) {
        push(&queue->tail, new_tail);
        return;
    }
    struct lifo *reversed = NULL;
    for (struct lifo *it = pop(&queue->tail); it; it = pop(&queue->tail))
        push(&reversed, it);
    push(&reversed, new_tail);
    for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
        push(&queue->tail, it);
}

int
dequeue(struct fifo *queue)
{
    assert(queue->tail);
    assert(queue->head);

    struct lifo *e;

    if (queue->head == queue->tail)  {
        e = queue->tail;
        queue->tail = NULL;
        free(queue->head);
        queue->head = NULL;
    } else {
        e = pop(&queue->tail);
        struct lifo *reversed = NULL;
        for (struct lifo *it = pop(&queue->head); it; it = pop(&queue->head))
            push(&reversed, it);
        free(pop(&reversed));
        for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
            push(&queue->head, it);
    }

    int ret = e->value;
    free(e);
    return ret;
}


int
main(void)
{
    struct fifo queue = { .head = NULL, .tail = NULL };

    for (int i = 0; i != 5; i++)
        enqueue(&queue, i);

    print(queue.head);
    print(queue.tail);

    printf("dequeue(&queue) = %d\n", dequeue(&queue));
    printf("dequeue(&queue) = %d\n", dequeue(&queue));
    printf("dequeue(&queue) = %d\n", dequeue(&queue));
    enqueue(&queue, 42);
    printf("dequeue(&queue) = %d\n", dequeue(&queue));
    printf("dequeue(&queue) = %d\n", dequeue(&queue));
    printf("dequeue(&queue) = %d\n", dequeue(&queue));

    return EXIT_SUCCESS;
}