What is the fastest way to implement a list and queue in c?

Question

Which one stack and queue realization will be faster and more optimal and why? Based on array (dynamic or static) or list?

For example, I have these ways:

Dynamic array based:

typedef struct Stack {
    char* values;
    int avl_el;
    int now_el;
    int top;
}Stack;

void push(Stack* stack, char data) {
    if (stack->now_el >= stack->avl_el) {
        stack->avl_el += INCR;
        stack->values = (char*)malloc(stack->avl_el * sizeof(char));
    }
    if (stack->top == -1) {
        stack->top++;
        stack->values[stack->top] = data;
        stack->now_el++;
    }else {
        stack->top++;
        stack->values[stack->top] = data;
        stack->now_el++;
    }
}

char pop(Stack* stack) {
    char tmp = stack->values[stack->top];
    stack->values[stack->top] = 0;
    stack->top--;
    stack->now_el--;
    return tmp;
}

List based:

typedef struct Node {
    char data;  // in this case we save char symb
    struct Node *next;
}Node;

typedef struct Stack {
    struct Node* topElem;
}Stack;

void push(Stack* stack, char data) {
    Node* tmp = (Node*)malloc(1 * sizeof(Node));
    if(!tmp) {
        printf("Can't push!\n");
        return;
    }
    tmp->data = data;
    tmp->next = stack->topElem;
    stack->topElem = tmp;  // making new top element
}

char pop(Stack* stack) {
    Node* tmp = stack->topElem;
    char del_data = stack->topElem->data;
    stack->topElem = stack->topElem->next;
    free(tmp);
    return del_data;
}

Will be any different with stack based on dynamic and stack based on static arrays?

Considering that your first implementation is wrong (you throw away all elements when increasing the size) and leaks memory I think you should first worry about fixing that before worrying about performance — UnholySheep, Mar 21 '19 at 19:09
@JohnColeman, I need an answer акщь the part of the algorithm, not just the running time. How to justify this theoretically? — po4yka, Mar 21 '19 at 19:10
@UnholySheep, Yes, I understand it and that's hastily realization just for example and to express more clearly my question. Also, with my test, it works normally. — po4yka, Mar 21 '19 at 19:13

Michael Veksler · Accepted Answer · 2019-03-21T20:30:17.007

Assuming you fix your bugs, let's discuss the principles. The biggest performance bug is incrementing size with a constant INC. With this bug, the complexity for inserting n elements is O(n²). For better complexity, reallocate in multiples of 2 or 1.5, after the fix the complexity of inserting n elements becomes O(n), or amortized O(1) for a single insertion.

The two approaches have been tested extensively with C++: what is faster std:: vector (similar to your stack) or std::list (a doubly linked list). Here is a list of resources:

Bjarne Stroustrup, the creator of c++, compared lists and vectors.
stack overflow: Relative performance of std::vector vs. std::list vs. std::slist?

Lists are easier to implement, and have a better predictability (no resizing), but vectors are faster in the stack scenario on average, and more memory efficient.

Vectors (the stack in the question):

Size: No need to store pointers to the next element. So it's more efficient.

Speed: consecutive elements are near each other, resulting in better memory predictability, and higher cache efficiency.

lists:

Size: no need to find one big block of memory (works better in a fragmented memory).

Speed: predictable - no need to copy big chunks of memory once in a while.

What is the fastest way to implement a list and queue in c?

1 Answers1