[자료구조] 2020.07.27

1. 배열을 이용하여 스택 구현(인덱스 개수 -1 시작)

#include <stdio.h>
#define MAX 5

int stack[MAX];
int index = -1;	// 인덱스는 0번째부터 시작하기 때문에 -1을 index에 저장
		// 책에 따라, 상황에 따라 index 시작점은 다를 수 있다

int isFull() {
	if (index == MAX - 1) {	// MAX-1을 하는 이유는 검사 후 저장해야하기 때문에
				// MAX로 한다면 이미 꽉 찬 상태에서 저장을 하려고 하기 때문에 문제가 생김
		return 1;	// 스택이 가득차 있을 때 1을 리턴!
	}
	return 0;
}
void push(int data) {
	index++;
	stack[index] = data;
}

int isEmpty() {
	if (index < 0) {	// index가 0보다 작다는 것은 데이터가 없다는 뜻
				// 저장된 데이터가 없는 상태에서 삭제한다면 문제가 생김
		return 1;	// 스택이 텅 비어 있을 때 1을 리턴
	}
	return 0;
}
int pop() {
	// 가리키고 있는 데이터를 출력 후 index - 1을 해줘야 한다.
	// index - 1의 의미? 그 데이터를 삭제한다는 뜻..!!
	// 그렇기 때문에 후취 연산자가 적합하다.
	return stack[index--];
}

// 가장 위의 값을 삭제
int peek() {
	return stack[index];
}

// 데이터 개수
int size() {
	return index + 1;
}

int main() {
	int act;

	while (1) {
		printf("1.push() 2.pop() 3.peek() 4.size() 5.종료\n");
		printf("번호 입력 : ");
		scanf("%d", &act);

		// 데이터를 스택에 입력하는 액션
		if (act == 1) {
			if (isFull()) {
				printf("가득차서 입력 불가\n");
				continue;
			}
			printf("데이터 입력 : ");
			int data;
			scanf("%d", &data);
			push(data);
		}

		// 가장 위의 값을 삭제
		else if (act == 2) {
			if (isEmpty()) {
				printf("텅 비어서 출력 불가\n");
				continue;
			}
			printf("pop() 수행 %d\n", pop());
		}

		// 가장 위의 값을 반환
		else if (act == 3) {
			if (isEmpty()) {
				printf("텅 비어서 출력 불가\n");
				continue;
			}
			printf("peek() 수행 %d\n", peek());
		}

		// 스택에 들어있는 데이터의 개수
		// 수위, LEVEL, 높이
		else if (act == 4) {
			printf("데이터 개수는 %d개 입니다.\n", size());
		}

		// 프로그램 종료
		else {
			printf("종료\n");
			break;
		}

	} // end while()

	return 0;
}

 

 

2. 배열을 이용하여 스택 구현(인덱스 개수 0 시작)

#include <stdio.h>
#define MAX 5
int stack[MAX];

int index = 0;

int isFull() {
	if (index == MAX) {
		return 1;
	}
	return 0;
}
void push(int data) {
	stack[index++] = data;
}

int isEmpty() {
	if (index - 1 < 0) {
		return 1;
	}
	return 0;
}
int pop() {
	return stack[--index];
}

int peek() {
	return stack[index - 1];
}

int size() {
	return index;
}

int main() {
	int act;

	while (1) {
		printf("1.push() 2.pop() 3.peek() 4.size() 5.종료\n");
		printf("번호 입력 : ");
		scanf("%d", &act);

		// 데이터 추가
		if (act == 1) {
			printf("데이터 입력 : ");
			int data;
			scanf("%d", &data);
			push(data);
		}

		// 가장 위의 값을 삭제
		else if (act == 2) {
			if (isEmpty()) {
				printf("텅 비어서 출력 불가!\n");
				continue;
			}
			printf("pop() 수행 %d\n", pop());
		}

		// 가장 위의 값을 반환
		else if (act == 3) {
			if (isEmpty()) {
				printf("텅 비어서 출력 출가\n");
				continue;
			}
			printf("peek() 수행 %d\n", peek());
		}

		// 데이터 개수
		else if (act == 4) {
			printf("데이터 개수는 %d개 입니다\n", size());
		}

		// 프로그램 종료
		else {
			printf("종료\n");
			break;
		}
	}

	return 0;
}

 

 

3. 동적 할당을 이용한 스택 구현

#include <stdio.h>
#include <stdlib.h>

void push(int data, int* stack, int index) {
	stack[index] = data;
}

int main() {
	printf("스택의 크기를 입력하세요 : ");
	int num;
	scanf("%d", &num);

	int* stack = (int*)malloc(num * sizeof(int));
	int index = 0;

	int act;
	while (1) {
		printf("1.push() 2. pop 3.peek 4.size 5.종료\n");

		printf("번호 입력 : ");
		scanf("%d", &act);
		if (act == 1) {
			if (index == num) {
				printf("가득차서 입력 불가\n");
				continue;
			}
			printf("데이터 입력 : ");
			int data;
			scanf("%d", &data);
			push(data, stack, index);
			index++;
		}
		else if (act == 2) {
			if (index == 0) {
				printf("텅 비어서 출력 불가\n");
				continue;
			}
			printf("pop 수행 %d\n", stack[--index]);
		}
		else if (act == 3) {
			if (index == 0) {
				printf("텅 비어서 출력 불가\n");
				continue;
			}
			printf("peek 수행 %d\n", stack[index - 1]);
		}
		else if (act == 4) {
			printf("데이터의 개수는 %d개 입니다\n", index);
		}
		else {
			printf("종료\n");
			break;
		}
	}

	return 0;
}

 

 

4. action을 문자로 받는 스택 구현

#include<stdio.h>
#include<string.h>

#define MAX 5
int stack[MAX];

int index = -1;

int isFull() {
	if (index == MAX - 1) {
		return 1;
	}
	return 0;
}
int isEmpty() {
	if (index < 0) {
		return 1;
	}
	return 0;
}

void push(int data) {
	stack[++index] = data;
}
int pop() {
	return stack[index--];
}
int peek() {
	return stack[index];
}
int size() {
	return index + 1;
}

int main() {
	char act[10];
	
	while (1) {
		printf("push, pop, peek, size : ");
		scanf("%s", act);

		if (strcmp(act, "push") == 0) {
			int data;
			printf("데이터 입력 : ");
			scanf("%d", &data);
			if (isFull()) {
				printf("[가득차서 push불가!]\n");
				continue;
			}
			push(data);
		}
		else if (strcmp(act, "pop") == 0) {
			if (isEmpty()) {
				printf("[텅 비어서 pop 불가!]\n");
				continue;
			}
			printf("[%d]\n", pop());
		}
		else if (strcmp(act, "peek") == 0) {
			if (isEmpty()) {
				printf("[텅 비어서 peek 불가!]\n");
				continue;
			}
			printf("[%d]\n", peek());
		}
		else if (strcmp(act, "size") == 0) {
			printf("level : %d\n", size());
		}
		else {
			printf("\nBye...\n\n");
			break;
		}
	}
	return 0;
}

 

 

5. 문제를 풀면서 입출력 개수 헷갈리지 않게 조심하기..!!

 

 

6. [스택 응용 문제] 입출력의 개수를 맞추자!
예) 정수 1개 입력 : 10
     2 3 -2 0 10 0 0 4 5 0
     [ 2 4 ] -> 6

#include <stdio.h>
#include <stdlib.h>

int main() {

	int n;
	printf("몇 개의 정수를 입력 받을지 입력하세요 : ");
	scanf("%d", &n);

	int* s = (int*)malloc(n * sizeof(int));
	int index = 0;

	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);

		if (num) {
			// 0이 아닐때 puch를 진행
			s[index++] = num;
		}
		else {
			// pop
			index--;
		}
	}
	int sum = 0;
	for (int i = 0; i < index; i++) {
		printf("%d ", s[i]);
		sum += s[i];
	}
	printf("\n%d\n", sum);

	return 0;
}

 

 

7. 스택 응용 문제
   입력 : ()(), 출력 : o
   입력 : ))((, 출력 : x  
   입력 : (()), 출력 : o
   입력 : (()()), 출력 : o
   입력 : (()()(), 출력 : x

#include<stdio.h>
#include<string.h>

int main() {

	char str[10];
	scanf("%s", str);

	int index = strlen(str) - 1;
	int sum = 0;

	while (index != -1) {
		if (str[index] == ')') {
			sum++;
		}
		else {
			sum--;
		}
		if (sum < 0) {
			break;
		}
		index--;
	}
	if (sum) {
		printf("X");
	}
	else {
		printf("O");
	}

	return 0;
}