스택 전환 및 스택 정렬

1. 문제 설명

(1) 귀속으로 창고를 뒤집는다.예를 들어 입력 창고 {1, 2, 3, 4, 5}, 1은 창고 꼭대기에 있습니다.뒤바뀐 창고는 {5,4,3,2,1}이고 5는 창고 꼭대기에 있습니다.
(2) 창고를 귀속 방법으로 정렬한다.

2. 솔루션

이 두 가지 문제는 주로 지원자의 귀속에 대한 이해를 고찰하는 것이다.귀속 프로그램에는 두 가지 관건적인 요소가 있는데 그것이 바로 귀속 정의와 귀속 중지 조건이다.
(1) 질문 1
분석을 거친 후 이 문제의 귀속 정의와 귀속 종지 조건을 쉽게 얻을 수 있다.귀속 정의: 현재 창고의 맨 아래 요소를 창고 꼭대기로 옮기고 다른 요소를 한 계단 아래로 옮긴 다음 이 창고 꼭대기 요소를 포함하지 않는 하위 창고를 계속합니다.종지 조건: 창고가 비어 있을 때까지 귀속합니다.코드는 다음과 같습니다.

// 
void move_bottom_to_top(stack& s)  {
  if(s.empty()) return;
  int top1 = s.top();
  s.pop();
  if(!s.empty()) {
    move_bottom_to_top(s);
    int top2 = s.top();
    s.pop();
    s.push(top1);// 
    s.push(top2);  
    return;        
  } 
  s.push(top1);
}
  
// 
void reverse_stack(stack& s) {
  if(s.empty()) return;
  move_bottom_to_top(s);// 
  int top = s.top();
  s.pop();
  reverse_stack(s);// 
  s.push(top);
}

 
(2) 문제2
창고 정렬과 창고 뒤집기 사상은 기본적으로 일치하기 때문에 위의 코드를 조금만 수정하면 창고 위치 정렬 코드를 얻을 수 있다.

void move_min_to_top(stack& s)  {
  if(s.empty()) return;
  int top1 = s.top();
  s.pop();
  if(!s.empty()) {
    move_min_to_top(s);
    int top2 = s.top();
    if(top1 > top2) {
      s.pop();
      s.push(top1);
      s.push(top2);  
      return; 
    }      
  } 
  s.push(top1);
}
  
void sort_stack(stack& s) {
  if(s.empty()) return;
  move_min_to_top(s);
  int top = s.top();
  s.pop();
  sort_stack(s);
  s.push(top);
}

 
새 책'프로그래머 면접 필기시험 보전'홈페이지에 전재하다
본문 링크 주소: 창고 전환과 창고 정렬