데이터 구조 (1) - 스 택 의 특성 및 간단 한 응용

데이터 구조 - 스 택 정의: 스 택 은 선진 적 인 구조 (FIFO) 입 니 다.기본 적 인 개념 은 말 하지 않 겠 습 니 다. 인터넷 의 글 은 모두 베 꼈 습 니 다. 블 로 거들 은 오리지널 을 추구 합 니 다. 기본 적 인 개념 은 모두 데이터 구조의 책 을 참고 할 수 있 습 니 다. 저 는 입문 한 빅 데이터 구조 와 엄 울 민, 오 웨 이 밍 의 데이터 구조 c 언어 판 을 추천 합 니 다. 강력 히 추천 합 니 다.
스 택 의 두 가지 가장 중요 한 작업: push: 스 택 상단 포인터 가 위로 이동 하여 하나의 요 소 를 스 택 에 밀어 넣 습 니 다.pop: 스 택 상단 의 요 소 를 팝 업 하고 스 택 상단 지침 을 아래로 이동 합 니 다.포인터 의 이동 순 서 는 어 셈 블 리 언어 에서 이렇게 규정 되 어 있 기 때문에 가능 한 한 본성 을 유지 하 세 요. 물론 순 서 를 뒤 바 꿀 수도 있 습 니 다. 직접 해 보 세 요.
응용: 스 택 의 선진 적 인 후 출 특성 으로 인해 많은 목적 을 실현 할 수 있 습 니 다. 1. 진법 전환 은 먼저 계산 한 나머지 를 마지막 으로 보관 해 야 하기 때문에 스 택 을 이용 하여 실현 할 수 있 습 니 다.여기 에는 기본 적 인 사상 만 을 소개 한다

void main()
{
    int num;
    int x;
    printf("        10   :");
    scanf("%d", &num); //    10
    while (num)
    {
        push(num % 2);//    
        num /= 2;//   
    }
    while (!isempty())//    
    {
        printf("%d", pop());//     1010
    }
    system("pause");
}

2. 역 폴란드 (접미사) 표현 식 의 값 기본 사상 을 계산 합 니 다. 왼쪽 에서 오른쪽으로 문자열 을 순서대로 옮 겨 다 니 면 숫자 가 스 택 에 들 어 갑 니 다. 문자 라면 두 개의 요소 연산 을 순서대로 팝 업 하여 스 택 에 들 어 갑 니 다.

//         ，        ，      ,            
switch (c)
        {
        case '+':
            Pop(&s, &e);
            Pop(&s, &d);
            Push(&s, d + e);
            break;
        case '-':
            Pop(&s, &e);
            Pop(&s, &d);
            Push(&s, d - e);//            
            break;
        case '*':
            Pop(&s, &e);
            Pop(&s, &d);
            Push(&s, d*e);
            break;
        case '/':
            Pop(&s, &e);
            Pop(&s, &d);
            if (e != 0)//       0
            {
                Push(&s, d / e);//            
            }
            else
            {
                printf("
  ：    ！
");
                return -1;//  main  -1
            }
            break;
        }