[C] 배열을 이용한 Stack 만들기

www.notion.so/1-6348c7f452b24565adbe1ce197c65f5e

✔︎ 미션 1

1. 미션 제목

배열로 Stack 만들기

2. 지시문

EDWITH CS50 강좌에서 배운 Stack을 C 언어로 구현해 보겠습니다. Stack을 구현하는 방법은 정말 많은데요, 이번 문제에서는 Stack을 배열을 이용해서 구현하는 방법에 대해서 알아보겠습니다. 아래 표에 함수의 주석 처리된 부분들에 여러분의 코드를 채워 넣어주세요.

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

typedef struct stack{
    int top;
    int capacity;
    int* array;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int *)malloc(stack->capacity*sizeof(int));
    return stack;
}

int isFull(Stack* stack) {
    return stack->top == stack->capacity-1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(Stack* stack) {
    // 이곳을 채워주세요!
}

int peek(Stack* stack) {
    // 이곳을 채워주세요!
}

int main() {
    Stack* stack = createStack(100);

    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    push(stack, 40);

    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));

    push(stack, 50);
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    return 0;
}

Main 함수를 실행시키면 Stack 출력 결과가 정상적으로 나와야 합니다.

위의 문제라면

 

10 pushed to stack

20 pushed to stack

30 pushed to stack

40 pushed to stack

40 pop from stack

30 pop from stack

50 pushed to stack

50 pop from stack

20 pop from stack

10 pop from stack

-9999 pop from stack

 

위와 같은 결과가 나오도록 작성해 주세요. 다양한 숫자와 사례를 만들어서 실험해 보세요!

 

3. 핵심 개념

#Stack #배열 #Stack 구현

나의 풀이

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

typedef struct stack {
    int top;
    int capacity;
    int* array;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

int isFull(Stack* stack) {
    return stack->top == stack->capacity - 1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(Stack* stack) {
    // 이곳을 채워주세요!
    if (isEmpty(stack))
        return -9999;
    return stack->array[stack->top--];
}

int peek(Stack* stack) {
    // 이곳을 채워주세요!
		return stack->array[stack->top];
}

int main() {
    Stack* stack = createStack(100);

    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    push(stack, 40);

    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));

    push(stack, 50);
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    return 0;
}

우선 주어진 소스코드를 살펴보면 Stack 구조체에는 top, capacity, array가 있습니다.

 

typedef struct stack {
    int top;
    int capacity;
    int* array;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

top

top은 크게 두 가지로 나눠질 수 있습니다.

하나는 top이 스택의 데이터의 끝을 가리키는 경우. 즉, pop 수행 시 데이터가 출력 될 위치를 가리키는 경우와 top이 스택에서 push를 했을 때 데이터가 삽입 될 위치를 가리키는 경우로 나뉘어집니다.

주어진 소스코드에서 createStack 부분을 보면 stack→top = -1로 초기화 하는 것을 알 수 있습니다. 이 부분으로 짐작해보면 top은 위 두 가지의 경우 중 데이터의 끝을 가리키는 경우로 생각해볼 수 있습니다. 아직 스택에 아무 데이터도 삽입되어 있지 않기 때문에 top은 -1로 초기화가 된 것입니다.

capacity

capacity는 용량. 즉, 스택이 데이터를 수용할 수 있는 크기를 뜻합니다. createStack 함수에서 파라미터로 입력 받아 입력 받은 크기 만큼의 스택을 생성합니다.

array

array는 createStack 함수에서 보면 int* 타입으로 stack→capacity 크기만큼 생성되는 것을 알 수 있습니다. 즉, 실제로 데이터를 저장할. 특히 int형 데이터를 저장할 스택 메모리입니다.

정리해보면 Stack 구조체는 데이터가 저장된 마지막 위치를 가리키는 top, 스택의 크기를 나타내는 capacity, 실제 스택인 array로 구성되어 있습니다.

isFull()

int isFull(Stack* stack) {
    return stack->top == stack->capacity - 1;
}

isFull 함수는 스택이 가득 찼는지 확인하는 함수입니다. 스택의 인덱스는 0부터 시작하기 때문에 스택이 가득 찬 경우에 top은 capacity - 1 을 가리킵니다.

stack→top 과 stack→capacity - 1이 같다면 스택이 가득 한 것이므로 true를 뜻하는 1을 return 합니다.

isEmpty()

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

isEmpty 함수는 스택이 비었는지 확인합니다. 스택이 비었다면 top은 -1을 가리키므로 stack→top 이 -1 라면 true를 뜻하는 1을 return 합니다.

push()

void push(Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

push함수는 스택에 공간이 있다면 스택에 아이템(데이터)를 삽입하는 함수입니다. isFull 함수로 스택이 가득 찼는지 확인한 후 스택에 저장 공간이 있다면 top을 하나 높여서 스택에 아이템을 저장합니다.

이후 메시지를 출력합니다.

pop()

int pop(Stack* stack) {
    if (isEmpty(stack))
        return -9999;
    return stack->array[stack->top--];
}

pop함수는 스택이 비었는지 확인해야 합니다. 이 과정이 없다면 스택에 저장된 아이템(데이터)가 없음에도 스택을 벗어난 메모리에 잘못 접근하여 오류가 발생할 수 있습니다.

isEmpty 함수를 이용하여 스택이 비었다면 -9999를 return 하고 그렇지 않으면 top이 가리키는 부분의 아이템을 return하고 top을 하나 내려줍니다.

작성한 소스코드에서는 후행 감소 연산자를 이용하여 한 줄로 표현했습니다.

main 함수와 결과창