[C언어로 쉽게 풀어 쓴 자료구조] 연습문제 5장 - 큐(소스코드 9~11)

9번

스택인 s1,s2를 담은 구조체 QueueType을 이용하여 s1에 1,2,3 이들어왔을때 s2가 비었다면 s1의 모든 원소를 s2에 넣어줌

s2에 3,2,1순으로 쌓이게됨

s2를 차례대로 pop하면 Queue의 역할 

typedef struct QueueType{
	StackType s1;
	StackType s2;
};
void Queue_init(QueueType *q){
	q->s1.top = -1;
	q->s2.top = -1;
}
void Queue_enqueue(QueueType *q,int data){
	push(&(q->s1),data);
	return;
}
int Queue_dequeue(QueueType *q){
	if(is_empty(&(q->s2))){
		while(!is_empty(&(q->s1))){
			push(&(q->s2),pop(&(q->s1)));
		}
	}
	return pop(&(q->s2));
}
int main(void) {
	QueueType q;
	Queue_init(&q);
	Queue_enqueue(&q,1);
	Queue_enqueue(&q,2);
	Queue_enqueue(&q,3);
	printf("%d",Queue_dequeue(&q));
	printf("%d",Queue_dequeue(&q));
	printf("%d",Queue_dequeue(&q));
	
	return 0;
	

}

10번

피보나치 수열의 n번째를 구하기 위해 큐에 미리 0 , 1 을 넣어놓음

0과 1을 더하여 나온 값인 1을 큐에 추가하고 0은 제거 -> 큐에는 1, 1이 남음

1과 1을 더하여 나온 값이 2를 큐에 추가하고 맨 앞 1은 제거 -> 큐에는 1,2가 남음

이런식으로 반복해주면 결과적으로 n번째에 해당하는 피보나치 수를 구할 수 있음

int fibo(int n){
	Queue q;
	init_queue(&q);
	enqueue(&q,0);
	enqueue(&q,1);
	int tmp = 0;
	int cnt = 0;
	while (cnt<n){
		int popnum = dequeue(&q);
		tmp = peek(&q)+popnum;
		enqueue(&q,tmp);
		cnt++;
	}
	return dequeue(&q);
	
}
int main(){
	printf("%d",fibo(5)); // answer= 5
	return 0;
}

11번

"madam" 은 회문임

맨 앞의 한글자와 맨뒤에 한글자씩 빼서 비교

-> 같으면 다음으로 넘어감

-> 다르면 회문이 아님

덱에 남은 문자가 1글자이하일때까지 반복

int pelindrome(char exp[]){
	Deque q;
	init_queue(&q);
	int i;
	int cnt = 0; //넣은 문자수를 세기위한 변수 cnt
	char ch;
	char back;
	int len = strlen(exp);
	for (i=0;i<len;i++){
		ch = exp[i];
		if (isalpha(ch)){
			add_rear(&q,tolower(ch));
			cnt += 1; //넣은 문자수를 세기위한 변수 cnt
		}
		
	}
	while (!(cnt<=1)){
		back = delete_rear(&q);
		if(back == get_front(&q)){
			delete_front(&q);
		}
		else{
			return 0;
		}
		cnt -= 2;// 두글자씩 빠졌으므로 -2
	}
	return 1;
	
}

int main(){
	
	char *exp = "madam";
	if (pelindrome(exp)){
		printf("회문입니다.");
	}
	else{
		printf("회문이 아닙니다.");
	}
	return 0;
}