Styjun

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?

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.