哪个堆栈和队列实现更快、更优化?为什么?基于数组(动态或静态)或列表?
例如,我有以下方法:
基于动态数组:

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

基于动态的堆栈和基于静态数组的堆栈有什么不同吗?

最佳答案

假设您修复了错误,让我们来讨论一下原则最大的性能缺陷是用一个常数Inc.用这个bug来增加大小,插入n个元素的复杂性是O(n2)。为了获得更好的复杂性,在将N元素插入的复杂性固定为O(n)之后,在2或1.5的倍数中重新分配,或者对单个插入进行摊销O(1)。
这两种方法已经用C++进行了广泛的测试:什么是更快的std:: vector(类似于您的堆栈)或std::list(双链表)。以下是资源列表:
Bjarne Stroustrup,c++的创建者,比较了列表和向量。
stack overflow: Relative performance of std::vector vs. std::list vs. std::slist?
列表更容易实现,并且具有更好的可预测性(无需调整大小),但是向量在堆栈场景中平均更快,而且内存效率更高。
向量(问题中的堆栈):
大小:不需要存储指向下一个元素的指针。所以效率更高。
速度:连续的元素彼此接近,从而产生更好的内存可预测性和更高的缓存效率。
列表:
大小:不需要找到一大块内存(在碎片内存中效果更好)。
速度:可预测-不需要偶尔复制大块内存。

10-06 04:51
查看更多