스택의 최소값

-1

StackMin, Pop 및 Push가 모두 Θ(1) 인 스택에서 최소값을 가져 오려고합니다. 당신은이 작업을 수행하는 두 스택이 필요스택의 최소값

typedef struct{ 
    int top; 
    int entry[1000]; 
    int small; 
} Stack; 

void Pop(int *e,Stack *ps){ 
    *e=ps->entry[--ps->top]; 
} 

void Push(int e,Stack *ps){ 
    ps->entry[ps->top++]=e; 
} 

int StackMin(Stack *ps){ 
    ps->small=ps->entry[ps->top]; 
    while(!StackEmpty(ps)){ 
     int *e; 
     *e=ps->entry[--ps->top]; 
     if(ps->small >= *e){ 
      ps->small = *e; 
     } 
    } 
    return ps->small; 
}

출처

2012-10-24 mike memo

작동하지 않는 기능은 무엇입니까? 컴파일러에서 오류를 줄 수 있습니까? 이보다 더 많은 정보를 제공해야합니다. –

"small"은 초기화되지 않은 메모리에 액세스합니다. –

푸시, 팝, 그리고 분은 역사적인 분에 대해서 이야기하지 않는 한 모두'Theta (1)'이 될 수 없습니다. min 값을 저장하면 push와 StackMin에서'O (1)'을 얻을 수 있지만, min과 같은 값을 pop하면 min - linear 연산을 다시 계산해야합니다. 당신은 정렬 된 배열을 저장할 수 있었고, Min 계산법은'O (1)'을 만들었지 만 push와 pop은'O (n)'- 배열을 저장할 수 있었지만 배열 값에 대한 참조를 가진 스택을 가지고 push, pop 와 min은 모두'O (1)'로 보이지만 push와 pop은 정렬 된 저장 공간을 위반하기 때문에 피해를 복구 할 때 실제로'O (n) '이됩니다. – FrankieTheKneeMan

: 내 코드가 작동하지 않습니다 ... 여기 내 시도입니다. 하나의 스택은 순서대로 min 값을 가질 수 있으며 min 값을 호출 할 때마다이 스택을 업데이트합니다. 알고리즘을 직접 알아 내려고 노력하십시오.

출처

2012-10-24 21:39:39 noMAD

당신은이 라인의 포인터 필요가 없습니다에

int *e; 
*e=ps->entry[--ps->top]; 
if(ps->small >= *e){ 
    ps->small = *e; 
}

변경을 :

이

int e = ps->entry[--ps->top]; 
if(ps->small >= e){ 
    ps->small = e; 
}

출처

2012-10-24 21:41:52 user1610015

1000에 도달했습니다. !!!! 사람들이 날 투표, 2000 나를 잡아 :) – user1610015

"작동하지 않는다"는 그 도움이 설명되지 않습니다 ...하지만 어떤 경우에도이 문제가 같습니다

는

int *e; 
*e=ps->entry[--ps->top]; 
if(ps->small >= *e){ 
    ps->small = *e; 
}

, 당신은 아무것도를 가리키는 포인터를 (선언되는 것은 - 그것이 않은 것입니다 초기화 된), 그 값이 가리키는 (무효 인) 위치에 값을 씁니다.

우연히 코드가 충돌하지 않고 질문에 대한 알고리즘이 있다면 다른 사용자가 그에 대한 답변을 게시했습니다.

출처

2012-10-24 21:42:46 paddy

스택의 최소값

답변

관련 문제