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

01 (a)

02 front는 첫 번째 요소의 바로 앞을 가리키기 때문에 인덱스 4, 5 에만 요소가 저장돼있으므로 (b) 

03 40,50 

04 (c)

05 (2)

06    | 0   1   2    3   4  |

         ㅡ  ㅡ  ㅡ  ㅡ  ㅡ  

        |           C   A   D  |

07  q->data[index] 와 같이 index로 바로 접근하므로 O(1)의 시간복잡도를 가진다. (a)

08  

element get_count(QueueType *q){
	element count=0;
	if(q->front < q->rear){
		count = (q->rear - q->front);
	}
	else if(q->front > q->rear){
		count = MAX_QUEUE_SIZE - (q->front - q->rear);
	}
	return count;
}

09

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct{
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

void init_stack(StackType *s){
	s->top=-1;
}

int is_empty(StackType *s){
	if(s->top == -1){
		return 1;
	}
	else return 0;
}

int is_full(StackType *s){
	if(s->top == (MAX_STACK_SIZE-1)){
		return 1;
	}
	else return 0;
}

void push(StackType *s,element item){
	if(is_full(s)){
		fprintf(stderr,"스택 가득참");
		exit(1);
	}
	s->top ++;
	s->data[(s->top)]= item;
}

element pop(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	
	return s ->data[(s->top)--];
}

element peek(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	return s->data[(s->top)];
}

int main(){
	StackType *s1;
	StackType *s2;
	s1 = (StackType*)malloc(sizeof(StackType));
	s2 = (StackType*)malloc(sizeof(StackType));
	init_stack(s1);
	init_stack(s2);
	char input;
	printf("입력을 원하면 i을, 출력을 원하면 o를, 종료를 원하면 e을 입력하세요\n");
	scanf("%c", &input);
	while(input != 'e'){
		if(input =='i'){
			element p;
			printf("정수를 입력하세요:");
			scanf("%d",&p);
			push(s1,p);
			peek(s1);
		}
		else if(input =='o'){
			if(is_empty(s2)){
				while(!is_empty(s1)){
					push(s2,pop(s1));
				}
			}
			printf("%d\n", pop(s2));
			
		}
		scanf("%c",&input);
	}  
    free(s1);
    free(s2);
	return 0;
}

10

element get_rear(QueueType *q){
	if(is_empty(q)){
		error("큐가 빔");
		return -1;
	}
	return q->data[q->rear];
}

element get_front(QueueType *q){
	if(is_empty(q)){
		error("큐가 빔");
		return -1;
	}
	return q->data[q->front+1];
}



element fibo(QueueType *q,element n){
	if(n==0) return 0;
	if(n==1) return 1;
	enqueue(q,0);
	enqueue(q,1);
	for(int i=1;i<n;i++){
		enqueue(q,dequeue(q)+get_rear(q));
	}
	return get_rear(q);
}

int main(){
	QueueType q;
	init_queue(&q);
	element a;
	printf("정수를 입력하시오\n");
	scanf("%d",&a);
	printf("n의 피보나치 수열 F(n)은 %d\n", fibo(&q,a));
	return 0;
}

11

int main(){
	DequeType q;
	init_deque(&q);
	
	char exp[100];
	scanf("%[^\n]s",exp);   
	// 공백을 포함해서 문자열을 입력받기 위해 [^/n]추가
	char ch;
	
	for(int i=0;i<strlen(exp);i++){
		ch=exp[i];
		if(ch<='Z'&&ch>='A'){
			ch = ch+('a'-'A');
			exp[i]=ch;
		}
	}
	for(int i=0;i<strlen(exp);i++){
		ch=exp[i];
		if(ch<='z'&&ch>='a'){
			add_front(&q,ch);
		}
	}
	if(strlen(exp)%2 ==0){
		int count =0;
		while(!is_empty(&q)){
			if(delete_front(&q)==delete_rear(&q)){
				count++;
			}
		}
		if(count==(strlen(exp)/2)){
			printf("회문입니다\n");
		}
		else printf("회문이 아닙니다\n");
	}
	else{
		int count =0;
		while(get_count(&q)!=1){
			if(delete_front(&q)==delete_rear(&q)){
				count++;
			}
		}
		if(count==(strlen(exp)/2)){
			printf("회문입니다\n");
		}
		else printf("회문이 아닙니다\n");
		
	}
	return 0;
}