哪个堆栈和队列实现更快、更优化?为什么?基于数组(动态或静态)或列表?
例如,我有以下方法:
基于动态数组:
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?
列表更容易实现,并且具有更好的可预测性(无需调整大小),但是向量在堆栈场景中平均更快,而且内存效率更高。
向量(问题中的堆栈):
大小:不需要存储指向下一个元素的指针。所以效率更高。
速度:连续的元素彼此接近,从而产生更好的内存可预测性和更高的缓存效率。
列表:
大小:不需要找到一大块内存(在碎片内存中效果更好)。
速度:可预测-不需要偶尔复制大块内存。