# C programming - stack 을 사용하여 fibonacci 수열을 구현했습니다.

1 분 소요

## C programming - stack 을 사용하여 fibonacci 수열을 구현했습니다

• 보통 fibonacci는 recursion으로 많이 푸는데, stack을 사용해서 풀 수도 있죠.
• 아래에서 stack을 구현하여 fibonacci를 구현해봤습니다.
``````#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
int value;
struct NODE* next;
} NODE;

NODE* new_node(int value, NODE* next) {
NODE* temp_node = (NODE*) malloc(sizeof(NODE) * 1);
temp_node->value = value;
temp_node->next = next;
return temp_node;
}

typedef struct STACK {
NODE* prev_last;
NODE* last;
int size;
} STACK;

STACK* init_stack(STACK* stack) {
stack->size = 0;
return stack;
}

int get_size(STACK* stack) {
return stack->size;
}

STACK* push_node(STACK* stack, int value) {
stack->last->next = new_node(value, NULL);
stack->prev_last = stack->last;
stack->last = stack->last->next;
stack->size += 1;
return stack;
}

NODE* pop_node(STACK* stack) {
NODE* return_node = stack->last;
if (stack->size == 1) {
init_stack(stack);
} else {
stack->last = stack->prev_last;
stack->last->next = NULL;
while (1) {
if (pointer->next == stack->last) {
stack->prev_last = pointer;
break;
}
pointer = pointer->next;
}
stack->size -= 1;
}
return return_node;
}

void print_stack(STACK* stack) {
printf("stack size: %d \n", stack->size);
while (pointer != NULL) {
printf("%d ", pointer->value);
pointer = pointer->next;
}
printf("\n");
}

int fibonacci_by_stack(int n) {
STACK* stack = (STACK*) malloc(sizeof(STACK) * 1);
stack = init_stack(stack);
stack = push_node(stack, n);
int r = 0;
while(stack->size != 0) {
int v = pop_node(stack)->value;
if (v == 1 || v == 2) {
r += 1;
} else {
stack = push_node(stack, v - 1);
stack = push_node(stack, v - 2);
}
}
return r;
}

int main(void) {
for (int i=1; i < 10; i++) {
printf("i: %d, fibonacci: %3d \n", i, fibonacci_by_stack(i));
}
return 0;
}
``````

태그:

카테고리:

업데이트: