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

1. (4)   ∵ top은 항상 마지막 원소의 인덱스를 카리킨다.
   
   

2. (2)   ∵ 후입선출에 의해 역순으로 출력이 된다.
   
   

3. 10, 20

↓ 각 연산 후 스택의 단계

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]
				50
			40	40	40
		30	30	30	30	30
	20	20	20	20	20	20	20
10	10	10	10	10	10	10	10

4. (4)   ∵ top은 마지막 원소의 인덱스를 카리키므로, 0~3 = 4개이다.
   
   

5. (1)
   
   

6. (1)   ∵ 삽입, 삭제 연산은 단순히 top의 값을 증감 후 그 위치에 값을 넣어주기만 하면된다.

7. (1)

↓ 각 연산 후 스택의 단계

[1]	[2]	[3]	[4]	[5]	[6]	[7]
		E		D
	B	B	B+E	B+E	D*(B+E)
A	A	A	A	A	A	A-D*(B+E)

8. ↓ 각 연산 후 스택의 단계

[1]	[2]	[3]	[4]	[5]	[6]	[7]
					5
		3		4	4	4
	2	2	2	2	2	2
1	1	1	1	1	1	1
top=0	top=1	top=2	top=1	top=2	top=3	top=2

9. ↓ 각 연산 후 스택의 단계

스택A	[1]	[2]	[3]	[4]	[5]	스택B	[1]	[2]	[3]	[4]
			c		c
		b	b	b	b			c
	a	a	a	a	a		d	d	d

int main(void) {
	int num, value;
	stack* s = (stack*)malloc(sizeof(stack));
	init(s);

	printf("정수 배열의 크기: ");
	scanf("%d", &num);

	printf("정수 입력: ");
	for (int i = 0; i < num; i++) {
		scanf("%d", &value);
		push(s, value);
	}

	printf("반전된 정수 배열: ");
	while (!empty(s))
		printf("%d ", pop(s));
}

void count(char* exp) {
	int c = 1;
	stack* s = (stack*)malloc(sizeof(stack));
	init(s);

	while (*exp) {
		char ch = *exp++;

		switch (ch) {
		case '(':
			printf("%d ", c);
			push(s, c++);
			break;
		case ')':
			printf("%d ", pop(s));
			break;
		}
	}
}

12.

void zip(char* str) {
	stack* s = (stack*)malloc(sizeof(stack));
	init(s);
	int ch, out, count = 0;

	while (*str) {
		ch = tolower(*str++);

		if (empty(s) || (ch == peek(s))) {
			push(s, ch);
			count++;
		}
		else {
			while (!empty(s))
				out = pop(s);
			printf("%d%c", count, out);
			push(s, ch);
			count = 1;
		}
	}
	printf("%d%c", count, pop(s));
}

13.

void eliminate(char* str) {
	stack* s = (stack*)malloc(sizeof(stack));
	init(s);

	while (*str) {
		char ch = *str++;

		if (empty(s) || (peek(s) == ch))
			push(s, ch);
		else {
			char out;
			while (!empty(s))
				out = pop(s);
			printf("%c", out);
			push(s, ch);
		}
	}
	printf("%c", pop(s));
}

14.

int size(stack* s) {
	int count = 0;

	while (!empty(s)) {
		pop(s);
		count++;
	}
	return count;
}

15. 생략

16. (스택을 3개 이용, s3는 역순 저장용)

int check(char* str) {
	stack* s1 = (stack*)malloc(sizeof(stack));
	stack* s2 = (stack*)malloc(sizeof(stack));
	stack* s3 = (stack*)malloc(sizeof(stack));
	init(s1); init(s2); init(s3);

	while (*str) {
		char ch = *str++;

		if (isalpha(ch)) {
			push(s1, tolower(ch));
			push(s2, tolower(ch));
		}
	}

	while (!empty(s1))
		push(s3, pop(s1));

	while (!empty(s3)) {
		if (pop(s3) != pop(s2))
			return 0;
	}
	return 1;
}