queues

fifo.c

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

struct Node {
    struct Node* next;
    int val;
};

typedef struct Lifo {
    struct Node* head;
    struct Node* tail;
};

void push(int e, struct Lifo* q) {
    struct Node* node = (struct Node*) malloc(sizeof (struct Node));
    node->val = e;
    node->next = 0;
    if (!q->head)
        q->head = node;
    else
        q->tail->next = node;
    q->tail = node;
}

int pop(struct Lifo* q) {
    int ret = 0;
    if (!q->head)
        return 0;
    ret = q->head->val;
    struct Node* first = q->head;
    q->head = q->head->next;
    if (!q->head) q->tail = 0;
    free(first);
    return ret;
}

int main() {
    struct Lifo* lifo = (struct Lifo*) malloc(sizeof (struct Lifo*));
    lifo->tail = 0;
    lifo->head = 0;
    push(1, lifo);
    push(2, lifo);
    push(3, lifo);
    printf("%d\n", pop(lifo));
    printf("%d\n", pop(lifo));
    printf("%d\n", pop(lifo));
    printf("%d\n", pop(lifo));
    //scanf("%*c");
    return 0;

}

lifo.c

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

struct Node {
    struct Node* next;
    int val;
};

typedef struct Lifo {
    struct Node* head;
};

void print(struct Lifo * q) {
    struct Node * curr = q->head;
    printf("[");
    while (curr) {
        printf("%d,", curr->val);
        curr = curr->next;
    }
    printf("]\n");
}

void push(int e, struct Lifo* q) {
    struct Node* node = (struct Node*) malloc(sizeof (struct Node));
    node->val = e;
    node->next = q->head;
    q->head = node;
}

int pop(struct Lifo* q) {
    int ret = 0;
    struct Node* first = 0;
    if (!q->head)
        return 0;
    ret = q->head->val;
    first = q->head;
    q->head = q->head->next;
    free(first);
    return ret;
}

int main() {
    struct Lifo* lifo = (struct Lifo*) malloc(sizeof (struct Lifo*));
    lifo->head = (struct Node *) malloc(sizeof (struct Node*));
    lifo->head = 0;
    char op = '+';
    int el;
    while (~scanf("%*[ \n\t]%c", &op)) {
        switch (op) {
            case '+':
                scanf("%d", &el);
                push(el, lifo);
                break;
            case '-':
                pop(lifo);
                break;
        }
        print(lifo);
    }
    return 0;

}
 

list.c

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

struct Node {
    struct Node* next;
    struct Node* prev;
    int val;
};

typedef struct List {
    struct Node* head;
    struct Node* tail;
};

void print(struct List * q) {
    struct Node * curr = q->head;
    printf("[");
    while(curr) {
        printf("%d,",curr->val);
        curr = curr->next;
    }
    printf("]\n");
}

void push(struct List* q, int e) {
    struct Node* node = (struct Node*) malloc(sizeof (struct Node));
    struct Node* curr;
    node->val = e;
    node->next = 0;
    node->prev = 0;
    // If empty
    if (!q->head) {
        q->head = node;
        q->tail = node;
        // Else If first
    } else if (q->head->val >= node->val) {
        node->next = q->head;
        q->head->prev = node;
        q->head = node;
    } else {
        curr = q->head;
        while (curr->next && curr->next->val < e)
            curr = curr->next;
        // Insert after current
        node->next = curr->next;
        node->prev = curr;

        // If not last
        if (curr->next)
            curr->next->prev = node;
        else
            q->tail = node;
        curr->next = node;
    }
}

int pop(struct List* q, int val) {

    int i;
    struct Node* e = 0;

    // If empty return -1
    if (!q->head)
        return -1;

    // find element
    e = q->head;
    while (e->next && e->next->val <= val)
        e = e->next;

    // if element has been found - delete it
    if (e->val == val) {
        if (q->head == q->tail && q->tail->val == val) {
            q->head = 0;
            q->tail = 0;
            free(e);
            return 1;
        }
        // if it's not first
        if (e->prev)
            e->prev->next = e->next;
        else
            q->head = e->next;
        
        // if it's not last
        if (e->next)
            e->next->prev = e->prev;
        else
            q->tail = e->prev;
        free(e);
        return 1;
    }// otherwise return -1
    else {
        return -1;
    }
}

int main() {
    struct List* list = (struct List*) malloc(sizeof (struct List*));
    list->tail = 0;
    list->head = 0;
    char op;
    int el;
    while (~scanf("%c", &op)) {
        switch (op) {
            case '+':
                scanf("%d", &el);
                push(list, el);
                break;
            case '-':
                scanf("%d", &el);
                pop(list, el);
                break;
        }
        print(list);
    }
    //canf("%*c");
    return 0;

}