C언어로 쉽게 풀어쓴 자료구조 [연습문제 5장]

1. (a)   ∵ 큐는 선입선출이므로, 들어온 순서 그대로 출력된다.
   
   

2. (2)   ∵ 5(rear) - 3(front) = 2개
   
   

3. 40, 50

↓각 단계 후의 큐 상태변화

큐
10
10	20
10	20	30
10	20	30	40
10	20	30	40	50
	20	30	40	50
		30	40	50
			40	50

4. (a)
   
   

5. (2)   ∵ 새로운 항목 삽입시 rear만 1 증가한다.
   
   

↓각 단계 후의 큐 상태변화

큐	0	1	2	3	4
(a)		B	C	A
(b)		B	C	A	D
(c)			C	A	D

7. (a)   ∵ 삽입, 삭제는 rear와 front를 1씩 증가하는 연산만 필요하다.
   
   

int get_count(queue* q) {
	if (q->rear >= q->front)
		return (q->rear - q->front);
	else
		return (SIZE - (q->front - q->rear));
}

int main(void) {
	stack* s1 = (stack*)malloc(sizeof(stack));
	stack* s2 = (stack*)malloc(sizeof(stack));
	init(s1); init(s2);

	while (1) {
		int num;
		printf("deque(0), enque(1): ");
		scanf("%d", &num);

		if (num) {
			printf("value: ");
			scanf("%d", &num);
			push(s1, num);
		}
		else {
			if (empty(s2)) {
				while (!empty(s1))
					push(s2, pop(s1));
			}
			printf("deque: %d\n", pop(s2));
		}
	}
}

int fib(int n) {	// n번째 피보나치 값을 반환하는 함수
	queue* q = (queue*)malloc(sizeof(queue));
	init(q);
	enque(q, 0); enque(q, 1);

	for (int i = 1; i <= n; i++)
		enque(q, deque(q) + peek(q));
	return peek(q);
}

int check(char* in) {	// 회문이면 1, 아니면 0을 반환하는 함수
	queue* q = (queue*)malloc(sizeof(queue));
	init(q);

	while (*in) {
		char ch = *in++;
		if (isalpha(ch))	// 문자가 알파벳인 경우에만
			add_front(q, tolower(ch));	// 소문자로 변환후 front에 삽입
	}

	while (!empty(q)) {
		char front = delete_front(q);
		if (empty(q))	// front에서 deque 후에 원소가 없는 경우 회문이므로 1 반환
			return 1;	

		char rear = delete_rear(q);

		if (front != rear)	// front에서의 deque값과, rear에서의 deque값이 다르면 0 반환
			return 0;
	}
	return 1;
}

12. 생략