데이터 구조의 창고 면접 문제: 최소 창고 의 실현

앞의 몇 개의 블 로그 에서 순서 표를 이용 하여 링크 를 제거 하 는 방식 으로 각각 대기 행렬 과 스 택 의 기본 적 인 조작 을 실현 했다.이 블 로그 에서 우 리 는 흔히 볼 수 있 는 창고, 대열 의 면접 문 제 를 총 결 하 였 다.
가장 작은 창고 의 실현
가장 작은 스 택 이 무엇 인지, 가장 작은 스 택 은 스 택 에 들 어 가 는 순 서 를 파괴 하지 않 는 전제 에서 스 택 꼭대기 에 스 택 내 요소 의 최소 값 을 영원히 저장 한 다 는 뜻 이다.우리 의 사고방식 은 매번 창고 에 들 어 갈 때마다 두 개의 창고 에 들 어 가 는 것 이다. 첫 번 째 는 창고 에 들 어가 야 할 요소 이 고 두 번 째 는 창고 에 들 어 갈 때 가장 작은 원소 이다.

//  
#include 
#include "seqstack.h"

typedef struct Min_SeqStack {
  SeqStack stack; 
}Min_SeqStack;

void Min_SeqStackPrint(Min_SeqStack* s)
{
  if(s == NULL) {
    return;
  }

  size_t i = 0;
  for(; i < s->stack.size; i++) {
    printf("%c ", s->stack.data[i]);
  }
  printf("
");
}

void Min_SeqStackInit(Min_SeqStack* s)
{
  if(s == NULL) {
    return;
  }
  SeqStackInit(&s->stack);
  return;
}

void Min_SeqStackPush(Min_SeqStack* s, SeqStackType value)
{
  if(s == NULL) {
    return;
  }

  SeqStackType top;
  SeqStackType min;


  if(s->stack.size == 0) {
    SeqStackPush(&s->stack, value);   
    SeqStackPush(&s->stack, value);   
  } else {
    SeqStackGetFront(&s->stack, &top);
    min = top < value ? top : value;
    SeqStackPush(&s->stack, value);
    SeqStackPush(&s->stack, min);
  }
  return;
}

void Min_SeqStackPop(Min_SeqStack* s)
{
  if(s == NULL) {
    return;
  }
  if(s->stack.size == 0) {
    return;
  }
  SeqStackPop(&s->stack);
  SeqStackPop(&s->stack);
}

int Min_SeqStackTop(Min_SeqStack* s, SeqStackType* value)
{
  if(s == NULL) {
    return -1;
  }
  if(s->stack.size == 0) {
    return -1;
  }
  return SeqStackGetFront(&s->stack, value);
}

여기 서 우 리 는 이전의 순서 창고 의 일부 함 수 를 빌려 서 우리 가 실현 하 는 것 을 도 왔 다.테스트 코드 는 다음 과 같 습 니 다:

int main()
{
  Min_SeqStack s;
  Min_SeqStackInit(&s); 
  Min_SeqStackPush(&s, 'a');
  Min_SeqStackPush(&s, 'c');
  Min_SeqStackPush(&s, 'd');
  Min_SeqStackPush(&s, 's');
  Min_SeqStackPrint(&s);
  SeqStackType value;
  Min_SeqStackTop(&s, &value);
  Min_SeqStackPrint(&s);
  printf("%c
", value);

  Min_SeqStackPop(&s);
  Min_SeqStackPrint(&s);
  Min_SeqStackTop(&s, &value);
  printf("%c
", value);

  Min_SeqStackPop(&s);
  Min_SeqStackPrint(&s);
  Min_SeqStackTop(&s, &value);
  printf("%c
", value);

  Min_SeqStackPop(&s);
  Min_SeqStackPrint(&s);
  Min_SeqStackTop(&s, &value);
  printf("%c
", value);

  return 0;
}

여러분 이 공동으로 토론 하 는 것 을 환영 합 니 다. 만약 잘못 이 있 으 면 즉시 작가 에 게 연락 하여 지적 하고 고치 세 요.감사합니다!