스택 연결리스트로 구현하기 (C)

이번 포스팅에서는 C코드를 통해서 위에서 설명한 스택을 간단하게 구현해보겠습니다.

스택을 구현함에 있어서 배열을 사용할 수도 있고, 연결 리스트를 활용할 수 있습니다.
우리는 이 중에서 단일 연결리스트만을 활용하도록 하겠습니다.

 

---

스택을 구현하기에 앞서 간단하게 어떠한 구조와 기능을 구현해야하는지 살펴봐야합니다.
이러한 정보는 스택 ADT에 명시되어 있습니다. 

이 스택 ADT에서는 저번 포스팅에서 다루었으니 보고 참고하시길 바랍니다.

 

• 구조체

크게 데이터를 저장할 연결리스트(스택 노드)와, 저장된 데이터를 관리하는 중추가 되는 스택을 정의합니다.

• 기능(연산)

void Push(Stack *stack, void *dataPtr) 스택에 데이터 입력

 

void Pop(Stack *stack) 스택에서 가장 위에 놓인 데이터 삭제

 

void* peek(STACK* stack) 스택의 가장 위에 놓인 데이터의 포인터 반환

 

Stack *createStack(void) 스택 생성

 

void destroyStack(Stack *stack) 스택 제거

 

Boolean isEmptyStack(Stack *stack) 스택이 비어있는지 확인

 

int countStack(Stack *stack) 스택이 저장하는 데이터의 개수 반환

---

구조체 정의

 

1. 연결리스트 

스택을 연결리스트로 구현하는 것이기 때문에 자연스럽게 데이터를 저장하는 노드 구조체를 정의해야 합니다. 그리고 연결관계를 구현하기 위해서는 해당 노드의 다음 노드가 어떠한 노드인지, 즉 해당 노드의 포인터를 기억해둬야 합니다.

일반적인 연결리스트 구현하듯이 아래와 같이 구현하면 됩니다.

 

typedef struct node
{
    void* dataPtr;
    struct node* next;
} STACK_NODE;

 

2.  스택 구조체

스택은 선입후출의 성질을 갖는 자료구조라 하였습니다. 이러한 성질을 반영하기 위에서는 연결리스트 중, 어떠한 노드가 top에 대응하는 노드인지를 확인해야 합니다. 따라서 이러한 속성(attribute)을 스택 구조체에 미리 지정합니다.

 

추가로 count라는 속성값을 정의합니다. 이를 통해 스택 연결리스트가 저장에 활용하고 있는 노드의 개수, 즉 입력된 데이터의 개수를 알 수 있습니다.

 

typedef struct
{
    int count;
    STACK_NODE* top;
} STACK;

---

기능(연산)의 정의

1. void Push(Stack *stack, void *dataPtr)

Push함수를 실행하면 두 가지의 변화가 생깁니다.

 

1. 전달한 데이터 포인터를 지닌 노드를 기존의 연결리스트에 연결하는 것 입니다.
2. 새롭게 추가된 노드가 해당 스택의 top으로써 기능합니다.

void pushStack(STACK* stack, void* dataInPtr) {
    STACK_NODE* pNewNode = (STACK_NODE*)malloc(sizeof(STACK_NODE));
    
    if (pNewNode == NULL)return;//동적할당을 할 때에는 메모리할당에 오류가 났는지를 확인해야 합니다.

    pNewNode->dataPtr = dataInPtr;
    pNewNode->next = stack->top;//기존의 연결리스트에 새로운 연결관계를 정의합니다.
    stack->top = pNewNode;// 스택의 top 포인터를 새로운 노드의 주소로써 새로 할당합니다.
    stack->count++;
}

2. void Pop(Stack *stack)

pop 함수를 실행하면 두 가지 변화가 생깁니다.

1. top 포인터에 해당하는 노드를 삭제합니다.

2. top 포인터는 그 다음으로 최근에 추가한 노드를 가리킵니다.

노드를 삭제를 할 때 한 가지 먼저 확인할 사항이 있습니다. 바로 삭제할 노드가 있기는 한 지 입니다. 이는 isEmpty()함수를 통해서 간단하게 확인이 가능합니다.

노드를 삭제할 때에는 노드를 생성할 때 사용한 malloc에 대응해 free를 잊지 않고 해야합니다.

 

void popStack(STACK* stack) {
    if (isEmptyStack(stack))return;
    STACK_NODE* pOldTop = stack->top;
    stack->top = pOldTop->next;
    free(pOldTop);
    stack->count--;
}

3. void* peek(STACK* stack)

peek이라는 단어에서도 알 수 있듯이 스택에 어떠한 값들이 저장되었는지 몰래 한 번 들여다 보는 것입니다. 대신에 가장 위에 노출된 노드의 데이터만 볼 수 있는 것이지요.

 

구현은 정말 간단합니다. top포인터가 가리키고 있는 노드의 dataPtr을 반환하면 되겠습니다.

 

void* peek(STACK* stack) {
    if (stack->top == NULL)return NULL;
    return stack->top->dataPtr;
}

4. Stack *createStack(void)

Stack형 포인터를 동적할당을 통해 생성하는 함수입니다.

새로 만들어진 스택에는 어떠한 데이터도 저장되지 않은 상태이므로 초기값을 설정해야 합니다.
그리고 값으로써 설정할 수 있는 것은 count, top포인터입니다.

STACK* createStack() {
    STACK* pStack = (STACK*)malloc(sizeof(STACK));
    if (pStack == NULL) return NULL;//동적할당이 잘 되어있는지 확인합니다.
    pStack->count = 0;//저장된 데이터가 없으니 count변수는 0으로 초기화합니다.
    pStack->top = NULL;//저장된 데이터가 없으니 top 포인터는 아무것도 가리키고 있지 않습니다.
}

5. void destroyStack(Stack *stack)

스택을 제거하는 destroyStack함수입니다. 스택을 제거하기 위해서는

1. 스택 포인터가 관할하는 연결리스트를 삭제해야 합니다.

2. 스택 포인터를 삭제해야합니다.

위의 두 단계에서의 삭제할 대상은 모두 동적할당을 통해 생성됩니다.그렇기 때문에 그에 대응되고 대칭적이게 free함수를 통해 적절히 구현하면 되겠습니다.

void destroyStack(STACK* stack) {
    STACK_NODE* temp = NULL;
    if (stack != NULL) {
        while (stack->top != NULL) {
            temp = stack->top;
            stack->top = temp->next;
            free(temp);
        }
        free(stack);
    }
    return;
}

6. bool isEmpty(Stack *stack)

Boolean을 반환하는 함수를 구현할 때에는 두 가지 방법이 있습니다. 헤더파일을 사용하는 방법과 그냥 int 반환형으로 구현하는 방법입니다.

 

C 컴파일러는 0을 False, 그 외의 값을 true로 인식하기 때문에 조건이 참이면 1을, 거짓이면 0을 반환하는 함수를 만들면 되겠습니다.

반대로 표준 라이브러리에 정의된 stdbool.h함수를 #include<stdbool.h>을 통해 참조하면 bool 자료형으로 표현가능합니다.

 

스택이 비어있다는 것은 스택의 count 속성값이 0이라는 것과 동치입니다. 따라서 아래와 같이 간단하게 구현할 수 있습니다.

bool isEmptySTack(STACK* stack) {
    return(stack->count == 0);
}

7. int countStack(Stack *stack) 

스택이 저장하는 자료의 개수는 이미 stack의 count에 저장되어 있습니다. 따라서 그 값을 그대로 반환만 하면 되겠습니다.

 

int countStack(STACK* stack) {
    return(stack->count);
}

 

---

이번 포스팅에서는 C코드를 통해서 위에서 설명한 스택을 간단하게 구현해보았습니다. 선입후출의 특징을 가진 스택의 자료의 관리방식을 연결 리스트를 통해 보다 더 유연하게 구현하였습니다. 대신 그만큼 메모리 해제에 신경쓰시면 되겠습니다. 다음 포스팅에서는 stack을 활용해 해결할 수 있는 문제들을 소개해보겠습니다. 감사합니다.