[자료구조] 스택 관련 문제 풀이(과제 1)

스택이란?

스택은 한 쪽 끝에서만 아이템을 삭제하거나 삽입할 수 있는 자료구조이다. 후입선출 자료구조인데, 가장 최근에 들어온 데이터가 가장 먼저 나간다. 스택은 정적 혹은 동적으로 구현해서 사용할 수 있다.

 

 

---

 

스택 기본 코드

#define _CRT_SECURE_NO_WARNINGS
#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)
{
    return (s->top == -1);
}

// 포화 상태 검출 함수
int is_full(StackType* s)
{
    return (s->top == (MAX_STACK_SIZE - 1));
}

// 삽입함수
void push(StackType* s, element item)
{
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;
}

// 삭제함수
element pop(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
element peek(StackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else
        return s->data[s->top];
}

• typedef struct ~ StackType: 스택 구조체 정의
• void init_stack(StackType* s): 스택 초기화 함수
• is_empty(StackType* s)비어있는지 확인해주는 함수
• is is_full(StackType* s)꽉 찼는지 확인해주는 함수
• push(StackType* s, element item): 삽입 함
• pop(StackType* s): 현재 top 위치의 데이터 반환 후 top을 지우는 함수
• peek(StackType* s): 현재 top 위치의 데이터 반환

해당 함수를 메인함수 바깥에 선언을 해주자! 그러면 이제 스택을 편하게 다룰 수 있다.

 

 

---

 

문제 1

 

배열에 들어있는 정수의 순서를 거꾸로 하는 프로그램을 작성해보자. 스택을 사용해서!

(여기서는 위에서 스택을 쓸 때 필요한 모든 처리를 해두었다고 생각하고 메인함수만 작성해보겠다!)

int main(void) {
    StackType s;
    int size;
    int num;

    init_stack(&s);

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

    printf("정수를 입력하시오: ");
    for (int i = 0; i < size; i++) {
        scanf("%d", &num);       // 정수 하나 입력받기
        push(&s, num);           // 스택에 삽입
    }

    printf("반전된 정수 출력: ");
    while (!is_empty(&s)) {
        printf("%d ", pop(&s));  // 스택에서 꺼내면서 출력 (역순)
    }
    printf("\n");

    return 0;
}

 

코드가 어떻게 작동하는가!

• 정수 배열의 크기를 받아 size에 넣고, 이만큼 반복문을 돌리며 num에 정수 입력을 받고, 스택에 계속 푸시한다.
• 반전된 스택은 따로 어디에 저장하라는 이야기가 없었으므로 반복문 돌려 pop() 함수로 스택 안이 빌 때까지 하나씩 꺼내 출력하면 된다.

 

---

 

 

문제 2

수식에 있는 괄호의 번호를 출력하는 프로그램을 작성하라. 왼쪽 괄호가 나올 때마다 괄호 번호는 하나씩 증가한다. 오른쪽 괄호가 나오면 매칭되는 왼쪽 괄호 번호를 출력한다.

void check_matching(char* in) {
	// 스택 생성
    StackType s;
    
    // 스택 초기화
    init_stack(&s);
    
    // 괄호 번호 세는 변수
    int count = 0;

	// 문자열 돌면서 확인
    for (int i = 0; i < len; i++) {
    
    	// 왼쪽 괄호가 들어오면 번호 증가, 새로운 번호 출력 후 스택에 번호 저장
        if (in[i] == '(') {
            count++;
            printf("%d", count);   // 왼쪽 괄호 → 새로운 번호 출력
            push(&s, count);       // 스택에 번호 저장
        }
        // 오른쪽 괄호가 들어오면 가장 최근에 저장된 값 pop으로 꺼내고, 출력
        else if (in[i] == ')') {
            int num = pop(&s);     // 오른쪽 괄호 → 매칭된 번호 출력
            printf("%d", num);
        }
    }
    printf("\n");
}

// 메인 함수
int main(void) {
    char line[100];
    printf("수식 입력: ");
    fgets(line, 100, stdin);

    // fgets는 끝에 '\n'이 포함될 수 있으므로 제거
    line[strcspn(line, "\n")] = '\0';

    check_matching(line);

    return 0;
}

 

코드가 어떻게 작동하는가!

• 스택 기본 코드들을 선언해두고, check_matching 함수를 정의한다.
• check_matching 함수는 문자열 in을 입력받고, 문자열을 읽으면서 괄호의 매칭 번호를 출력한다.
• 왼쪽 괄호가 나올 때마다 번호를 증가시켜 해당 번호를 스택에 저장하고, 오른쪽 괄호가 나올 때는 번호를 스택에서 하나씩 꺼내 출력한다.

 

 

---

 

 

문제 3

문자열을 압축하는 프로그램을 작성하라.

Ex) 입력: aaaAbBb, 출력: 4a3b

int main(void)
{
    char line[100];       // 입력 문자열 저장
    StackType s;          
    init_stack(&s);       // 스택 초기화

    printf("문자열: ");
    if (!fgets(line, sizeof(line), stdin)) return 0;           // 문자열 입력
    line[strcspn(line, "\n")] = '\0';                          // 개행 제거

    // 전체 문자열을 소문자로 변환
    for (int i = 0; line[i]; i++)
        line[i] = (char)tolower((unsigned char)line[i]);

    printf("압축된 문자열: ");

    // 문자열 순회
    for (int i = 0; line[i]; i++) {
        char curr = line[i];        // 현재 문자

        if (is_empty(&s)) {
            push(&s, curr);         // 스택에 문자 push
            push(&s, 1);            // 연속 개수 1 push
        } else {
            int count = pop(&s);         // 이전 문자 개수 pop
            char ch = (char)pop(&s);     // 이전 문자 pop

            if (ch == curr) {            // 이전 문자와 현재 문자 같으면
                count++;                 // 개수 증가
            } else {                      // 다르면 이전 구간 출력
                printf("%d%c", count, ch); 
                count = 1;                // 새 문자는 개수 1로 시작
                ch = curr;                // 문자 갱신
            }

            push(&s, ch);                 // 문자 다시 push
            push(&s, count);              // 개수 다시 push
        }
    }

    // 마지막 남은 문자 출력
    if (!is_empty(&s)) {
        int count = pop(&s);
        char ch = (char)pop(&s);
        printf("%d%c", count, ch);
    }

    printf("\n");
    return 0;
}

 

 

코드가 어떻게 작동하는가!

• 스택 기본 코드들을 선언해두고, 문자열을 받는다.
• 내 컴퓨터에서는 gets_s를 못 써서 fgets로 대신 문자열 입력을 받았다.
• 소문자와 대문자 구분을 하지 않으므로 tolower을 이용해 전부 소문자로 만든다. tolower 함수를 쓰려면 #include <ctype.h> 을 선언해야한다.
• 문자열을 순회하며 현재 문자가 이전 문자와 같으면 개수 증가, 다르면 이전에 셌던 수 만큼 출력하고 새 문자를 시작한다.
• 마지막 남은 문자는 루프 종료 후 pop으로 꺼내 출력한다.

 

 

 

---

마치며

파이썬이 익숙한 나에게는 구조체로 스택 만들어 선언하고 쓰는 일이 다소 힘들게 느껴지지만(파이썬은 list 자료구조에서 append, pop 등을 지원해준다!) 컴공 2학년이면 꼭 들어야 하는 과목이니 즐겁게 해보자 ^^ .. ㅜㅜ