제네릭 스택

Coddy C 여정의 객체 지향 프로그래밍 섹션에 포함된 레슨. 61개 중 60번째.

챌린지

쉬움

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

Generic Stack을 만들어 보겠습니다. void* 포인터를 사용하여 모든 유형의 데이터를 저장할 수 있는 다목적 자료 구조입니다. 스택은 후입선출 원칙을 따르며, 모든 필수 operation을 포함합니다.

코드를 세 개의 파일로 구성합니다.

stack.h: 세 개의 members를 가진 Stack 구조체를 Define합니다. void** array는 items를 저장하고, int 하나는 top index(다음 빈 슬롯)를 저장하며, 또 다른 int 하나는 capacity를 저장합니다. 스택을 Create하는 function(capacity를 전달받음), item을 추가하는 function, item을 제거하는 function, top item을 확인하는 function, 스택이 empty인지 확인하는 function, 스택을 해제하는 function의 프로토타입을 Declare합니다.
stack.c: Generic Stack을 Implement합니다.
- create_stack: heap에 Stack을 할당하고, given capacity로 items array를 할당하며, top을 0으로 초기화한 후 pointer를 반환합니다.
- push: 공간이 있을 때(top이 capacity보다 작을 때) top에 item을 추가합니다.
- pop: top item을 제거하고 반환하며, 스택이 empty이면 NULL을 반환합니다.
- peek: top item을 제거하지 않고 반환하며, 비어 있으면 NULL을 반환합니다.
- is_empty: 스택에 item이 없으면 1을, otherwise에는 0을 반환합니다.
- free_stack: 먼저 items array를 해제한 다음 Stack 구조체 itself를 해제합니다.
main.c: 수행할 operation의 수를 읽습니다. 그런 다음 각 operation에 대해 command를 읽습니다. command는 정수 값이 뒤따르는 push, pop 또는 peek 중 하나입니다. capacity가 10인 스택을 Create합니다. push의 경우 heap에 integer를 할당하고 해당 pointer를 push합니다. pop의 경우 item을 가져와 그 값을 출력한 다음 integer를 해제합니다. peek의 경우 item을 제거하지 않고 값을 출력합니다. empty 스택에서 pop 또는 peek이 호출되면 empty를 출력합니다. 모든 operation이 끝나면 남아 있는 item과 스택을 해제합니다.

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

operation의 수
각 줄에 하나씩 입력되는 operation(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* 포인터를 저장한다는 점을 기억하세요. 실제 데이터를 할당하고 해제하는 책임은 caller에게 있습니다. pop할 때 반환된 void*를 다시 int*로 cast하여 값에 접근하세요. command 문자열을 비교하려면 <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이 아니면, 값을 출력하고 정수를 free
            // - NULL이면 (빈 스택), "empty" 출력
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: 맨 위 항목을 peek
            // - NULL이 아니면, 값을 출력 (제거하거나 free하지 않음)
            // - NULL이면 (빈 스택), "empty" 출력
        }
    }
    
    // TODO: 스택에 남아 있는 항목들을 free
    // TODO: 스택 자체를 free
    
    return 0;
}