<5> Q5. 자료구조와 함께 배우는 알고리즘 입문 (C언어)

 

스택 구조

 

a에는 n값

b에는 구분값을 넣어서

첫번째 항 값이였는지 두번째 항 값이였는지 구분해줌

 

 

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int max;
    int prt;
    int *stk;
} IntStack;

int Initialize(IntStack *s, int max)
{
    s->prt = 0;
    if ((s->stk = (int *)calloc(max, sizeof(int))) == NULL)
    {
        s->max = 0;
        return -1;
    }
    s->max = max;
    return 0;
}

int Push(IntStack *s, int x)
{
    if (s->prt >= s->max)
        return -1;
    s->stk[s->prt++] = x;
    return 0;
}

int Pop(IntStack *s, int *x)
{
    if (s->prt <= 0)
        return -1;
    *x = s->stk[--s->prt];
    return 0;
}

int IsEmpty(const IntStack *s)
{
    return s->prt <= 0;
}

void recur3(int n)
{
    IntStack a, b;
    Initialize(&a, 100); //n값 저장
    Initialize(&b, 100); //재귀 구분
    int chk = 0;

    while (1)
    {
        if (n > 0 && chk == 0)
        {
            Push(&a, n);
            Push(&b, 0);
            n = n - 1;
            continue;
        }
        while (!IsEmpty(&a))
        {
            Pop(&a, &n);
            Pop(&b, &chk);
            if (chk == 1)
            {
                printf("%d\n", n);
                if (IsEmpty(&a))
                    break;
                continue;
            }
            if (n > 2)
            {
                Push(&a, n);
                Push(&b, 1);
                n = n - 2;
                break;
            }
            printf("%d\n", n);
        }
        if (IsEmpty(&a))
            break;
    }
}
int main(void)
{
    int i;
    printf("Input Number : ");
    scanf("%d", &i);
    recur3(i);
}