Какой самый быстрый способ реализовать список и очередь в c?

Question

Какая реализация стека и очереди будет быстрее и оптимальнее и почему?На основе массива (динамического или статического) или списка?

Например, у меня есть следующие способы:

На основе динамического массива:

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;
}

На основе списка:

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;
}

Будет ли что-нибудь отличаться от стека на основе динамического и стека на основе статических массивов?

Answer 1

Если вы исправите ошибки, давайте обсудим принципы. Самая большая ошибка производительности - увеличение размера с постоянным значением INC. С этой ошибкой сложность вставки n элементов равна O (n ² ). Для большей сложности, перераспределите с кратностью 2 или 1,5, после исправления сложность вставки n элементов становится O (n) или амортизированной O (1) для одной вставки.

Два подхода были тщательно протестированы на C ++: что быстрее std:: vector (аналогично вашему стеку) или std::list (двусвязный список). Вот список ресурсов:

• Бьярн Страуструп , создатель c ++, сравнил списки и векторы.
• переполнение стека: Относительная производительность std :: vector против std :: list против std :: slist?

Списки проще в реализации и имеют лучшую предсказуемость (без изменения размера), но векторы в среднем быстрее в стековом сценарии и более эффективны при использовании памяти.

Векторы (стек в вопросе):

Размер: нет необходимости хранить указатели на следующий элемент. Так что это более эффективно.

Скорость: последовательные элементы расположены рядом друг с другом, что обеспечивает лучшую предсказуемость памяти и более высокую эффективность кэширования.

списки:

Размер: не нужно находить один большой блок памяти (лучше работает во фрагментарной памяти).

Скорость: предсказуемая - не нужно время от времени копировать большие куски памяти.