Эффективная реализация стеков в C

Question

https://www.hackerrank.com/challenges/equal-stacks
Для этой проблемы я попытался реализовать структуру данных стека в c. Но я получаю тайм-аут для некоторых случаев, используя следующий код:

#include <math.h> 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <limits.h> 
#include <stdbool.h> 
struct Stack{ 
    int top; 
    int size; 
    int sum; 
    int* arr; 
}; 
struct Stack* createStack(int size){ 
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); 
    stack->size=size; 
    stack->top=-1; 
    stack->sum=0; 
    stack->arr = (int*)malloc(sizeof(int)*size); 
    return stack; 
} 
int isempty(struct Stack* stack){ 
    if(stack->top==-1) 
     return 1; 
    return 0; 
} 
void push(struct Stack* stack,int term){ 
    stack->top++; 
    stack->arr[stack->top]=term; 
    stack->sum+=term; 
} 
void pop(struct Stack* stack){ 
    if(isempty(stack)==0){ 
     stack->sum-=stack->arr[stack->top]; 
     stack->top--; 
    } 
} 
int main(){ 
    int size1,size2,size3; 
    scanf("%d %d %d",&size1,&size2,&size3); 
    int arr1[size1]; 
    for(int i=0;i<size1;i++) 
     scanf("%d",&arr1[i]); 
    struct Stack* stack1 = createStack(size1); 
    for(int i=size1-1;i>=0;i--) 
     push(stack1,arr1[i]); 
    int arr2[size2]; 
    for(int i=0;i<size2;i++) 
     scanf("%d",&arr2[i]); 
    struct Stack* stack2 = createStack(size2); 
    for(int i=size2-1;i>=0;i--) 
     push(stack2,arr2[i]); 
    int arr3[size3]; 
    for(int i=0;i<size3;i++) 
     scanf("%d",&arr3[i]); 
    struct Stack* stack3 = createStack(size3); 
    for(int i=size3-1;i>=0;i--) 
     push(stack3,arr3[i]); 
    while(stack1->sum!=stack2->sum || stack2->sum!=stack3->sum){ 
     if(stack1->sum > stack2->sum && stack1->sum > stack3->sum) 
      pop(stack1); 
     if(stack2->sum > stack1->sum && stack2->sum > stack3->sum) 
      pop(stack2); 
     if(stack3->sum > stack2->sum && stack3->sum > stack1->sum) 
      pop(stack3); 
    } 
    printf("%d\n",stack1->sum); 
} 

Может кто-нибудь предложить лучший подход, используя только структуру данных стеки (предпочтительно в C)?

Answer 1

Причина вы могли бы получать превышение времени превысило, потому что ваш цикл while никогда не заканчивается, если

a) Любой стек становится пустым. Вы должны добавить, что проверяете условие цикла while, что ни один из стеков не пуст, а затем выводит минимальную сумму всех трех стеков.

b) Может быть, если высота 20, 10, 10, в этом случае, как будет работать ваш код?

Answer 2

Вы можете ускорить процесс, указав, какой стек имеет наибольшую сумму, а затем выскочить из этого стека, пока его сумма не будет равна или меньше самой низкой суммы.

код, чтобы найти стеки с высокими и самыми низкими суммами может выглядеть следующим образом

struct Stack *high = (stack1->sum > stack2->sum) ? stack1 : stack2; 
struct Stack *low = (high == stack1) ? stack2 : stack1; 

if (stack3->sum > high->sum) 
    high = stack3; 
else if (stack3->sum < low->sum) 
    low = stack3; 

Затем код, чтобы уменьшить высокий сумма выглядит эта

while (high->sum > low->sum) 
    pop(high);