제네릭 스택

Coddy C 여정의 Object Oriented Programming 섹션에 포함된 레슨 — 61개 중 60번째.

챌린지

쉬움

스택(stack)은 후입선출(LIFO, Last-In-First-Out) 원칙을 따르는 기본적인 자료 구조로, 마지막에 추가된 요소가 가장 먼저 제거됩니다. 접시 더미를 생각해보세요. 맨 위에 접시를 쌓고, 맨 위에서부터 접시를 꺼냅니다.

void* 포인터를 사용하여 어떤 유형의 데이터든 저장할 수 있는 다재다능한 자료 구조인 제네릭 스택(Generic Stack)을 만들어 봅시다. 여러분의 스택은 후입선출 원칙을 따르며, 모든 필수 연산을 포함하게 됩니다.

코드는 다음 세 개의 파일로 구성합니다:

stack.h: 세 개의 멤버를 가진 Stack 구조체를 정의합니다. 아이템을 위한 void** 배열, 다음 빈 슬롯을 가리키는 int형 top 인덱스, 그리고 int형 용량(capacity)입니다. 스택 생성(용량을 인자로 받음), 아이템 push, 아이템 pop, 맨 위 아이템 peek, 스택이 비었는지 확인, 그리고 스택 메모리 해제를 위한 함수 프로토타입을 선언합니다.
stack.c: 제네릭 스택을 구현합니다:
- create_stack — 힙(heap)에 Stack을 할당하고, 주어진 용량으로 items 배열을 할당하며, top을 0으로 초기화한 후 포인터를 반환합니다.
- push — 공간이 있다면(top이 capacity보다 작을 때) 맨 위에 아이템을 추가합니다.
- pop — 맨 위의 아이템을 제거하고 반환하며, 스택이 비어 있으면 NULL을 반환합니다.
- peek — 맨 위의 아이템을 제거하지 않고 반환하며, 비어 있으면 NULL을 반환합니다.
- is_empty — 스택에 아이템이 없으면 1을, 그렇지 않으면 0을 반환합니다.
- free_stack — items 배열을 먼저 해제한 다음, Stack 구조체 자체를 해제합니다.
main.c: 수행할 연산의 개수를 읽습니다. 그런 다음 각 연산에 대해 명령어를 읽습니다: 정수 값이 뒤따르는 push, pop, 또는 peek입니다. 용량이 10인 스택을 생성합니다. push의 경우, 힙에 정수를 할당하고 그 포인터를 push합니다. pop의 경우, 아이템을 가져와서 값을 출력하고 정수 메모리를 해제합니다. peek의 경우, 제거하지 않고 값을 출력합니다. 비어 있는 스택에 pop 또는 peek이 호출되면 empty를 출력합니다. 모든 연산이 끝나면 남아 있는 아이템들과 스택을 해제합니다.

프로그램은 다음을 입력받습니다:

연산의 개수
각 줄에 하나씩의 연산 (push X, pop, 또는 peek)

입력이 5이고, 이어서 push 10, push 20, peek, pop, pop인 경우의 예시 출력:

20
20
10

입력이 3이고, 이어서 pop, push 42, peek인 경우의 예시 출력:

empty
42

입력이 4이고, 이어서 push 5, push 15, pop, pop인 경우의 예시 출력:

15
5

스택은 void* 포인터를 저장하므로, 실제 데이터를 할당하고 해제하는 책임은 호출자에게 있음을 기억하세요. pop할 때는 반환된 void*를 int*로 다시 캐스팅하여 값에 접근하십시오. 명령어 문자열을 비교하려면 <string.h>의 strcmp를 사용하세요.

직접 해보기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: 용량이 10인 스택 생성
    
    // TODO: 각 연산 처리
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: 힙에 정수를 할당하고 그 포인터를 push
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: 아이템을 pop
            // - NULL이 아니면, 값을 출력하고 정수 메모리 해제
            // - NULL이면 (빈 스택), "empty" 출력
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: 맨 위 아이템을 peek
            // - NULL이 아니면, 값을 출력 (제거하거나 해제하지 않음)
            // - NULL이면 (빈 스택), "empty" 출력
        }
    }
    
    // TODO: 스택에 남아 있는 모든 아이템의 메모리 해제
    // TODO: 스택 자체의 메모리 해제
    
    return 0;
}