스택(Stack)의 개념 및 배열로 구현하는 스택

스택(Stack)의 개념 및 배열로 구현하는 스택

스택 주차장

주차장 내 차

차를 몰고 여기저기 돌아다니다가 식사를 위해 주차장에 주차를 한 뒤 식당에 들어갔습니다. 식당에 들어갈 때에는 손님이 거의 없었지만 식사를 마치고 나올 쯤에는 손님들로 식당이 꽤 붐볐습니다.

이 때문에 주차한 차를 빼는 데에 문제가 생겼습니다. 식당의 주차장이 독특하게 생긴데다 열악했기 때문인데요. 폭이 좁고 긴 공터를 주차장으로 사용하고 있었기 때문입니다.

손님이 없을 때에 주차를 했기 때문에 가장 안쪽에 주차한 것이 화근이었습니다. 제 차 앞에 세 대의 차가 더 주차되어 있었기 때문이었습니다. 식사 중인 손님들을 방해하고 싶지는 않았지만 식당의 지배인을 통해 차 주인들을 모두 불러 앞의 차들을 모두 빼낸 다음에야 차를 빼고 나설 수 있었습니다.

이 식당의 주차장은 '가장 먼저 들어간 차가 가장 마지막에 나오는 구조'로 되어 있었는데, 스택(Stack)이 바로 이런 형태의 자료구조입니다. 스택은 영어로 뭔가를 쌓아놓은 더미를 뜻합니다. 예를 들어 건초더미, 서류더미와 같은 것 말입니다.

스택은 앞에서 말한 예시처럼 처음에 들어간 것이 가장 마지막에 나오도록 되어있는 구조를 가지고 있습니다. 이러한 구조를 FILO(First In, Last Out) 또는 LIFO(Last In, First Out)라고 부르는데, 이는 데이터의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 것이 특징입니다.

스택은 큐와 함께 소프트웨어 분야에서 굉장히 중요한 역할을 담당하고 있습니다. 자동 메모리가 스택을 기반으로 동작하고, 대부분의 네트워크 프로토콜 또한 스택을 기반으로 구성되어 있습니다. 각종 텍스트 분석 프로그램도 마찬가지로 스택을 이용하고 있습니다.

스택의 주요 기능: 삽입과 제거

스택의 주요기능은 '삽입(Push)'과 '제거(Pop)' 두 가지입니다. 그 이외의 기능들은 이 두 개의 연산을 위한 보조 연산일 뿐입니다.

삽입 연산은 스택 위에 새로운 노드(또는 요소)를 '쌓는' 작업입니다. 다음의 그림처럼 말입니다.

스택 삽입

반면에 제거 연산은 스택에서 최상위 노드를 '걷어내는' 작업입니다.

스택 삭제

배열로 구현하는 스택

스택을 구현하는 방법으로는 배열을 이용하거나 링크드 리스트를 이용하는 두 가지 방법이 대표적입니다. 그 중 해당 포스팅에서는 배열을 이용하는 방법에 대해 설명하려고 합니다.

먼저, 배열을 이용한 구현은 동적으로 스택의 용량을 조절하기가 어렵다는 단점이 있지만 구현이 간단하다는 장점이 있습니다. 배열 기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신 스택 생성 초기에 사용자(프로그래머)가 부여한 용량만큼의 노드를 한꺼번에 생성합니다. 그리고 최상위 노드의 위치를 나타내는 변수를 이용하여 삽입과 제거 연산을 수행합니다.

스택과 스택의 노드 표현하기

먼저 스택의 각 층을 구성하는 노드의 모습은 어떨까요? 배열을 기반으로 구현되는 스택의 노드는 다음과 같이 데이터만 담는 구조체로 표현됩니다. 노드가 존재하는 위치는 배열의 인덱스로 알 수 있기 때문에 링크드 리스트처럼 앞이나 뒷 노드에 대한 포인터는 필요 없습니다.

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
    Node;
}

이번에는 스택 구조체를 보도록 하겠습니다. 배열 기반의 스택은 다음 세 가지 필드를 가지고 있어야 합니다.

• 용량
• 최상위 노드의 위치
• 노드 배열

위 세 가지 중에 용량은 스택이 얼마만큼의 노드를 가질 수 있는지에 대한 한계를 알기 위해 사용됩니다. 최상위 노드의 위치는 삽입/제거 시에 최상위 노드에 접근할 수 있게 돕습니다. 그리고 노드 배열은 스택에 쌓이는 노드를 보관하는 데에 사용됩니다. 다음의 ArrayStack 구조체는 이러한 필드의 요구사항을 반영하여 선언되었습니다.

typedef struct tagArrayStack
{
    int        Capacity;    /* 용량 */
    int        top;        /* 최상위 노드의 위치 */
    Node*    Nodes;        /* 노드 배열 */
}    ArrayStack;

노드 배열 필드인 Nodes를 보면 포인터로 선언되어 있습니다. 이는 포인터를 배열로 사용할 수 있는 C 언어의 특성 때문에 가능한 것입니다. 노드 배열을 자유 저장소에 할당하고 Nodes 포인터는 아래 그림과 같이 자유 저장소에 할당된 배열을 가리키는 데 사용될 것입니다.

Nodes 포인터와 자유저장소

스택의 기본 연산 구현하기

스택은 가장 위에 있는 노드 위에 새로운 노드를 얹는 '삽입'과 '삭제' 연산을 반드시 수행해야 합니다.

스택의 생성과 소멸

스택을 생성하고 노드를 받아들일 수 있게 준비하는 AS_CreateStack() 함수는 다음과 같이 구현합니다. 여기서 AS_라는 접두사는 ArrayStack의 약자입니다.

void  AS_CreateStack(ArrayStack** Stack, int Capacity)
{
    /*  스택을 자유저장소에 생성 */
    (*Stack)           = (ArrayStack*)malloc(sizeof(ArrayStack));

    /*  입력된 Capacity만큼의 노드를 자유저장소에 생성 */
    (*Stack)->Nodes    = (Node*)malloc(sizeof(Node)*Capacity);

    /*  Capacity 및 Top 초기화 */
    (*Stack)->Capacity = Capacity;
    (*Stack)->Top = 0;
}

AS_CreateStack() 함수의 매개 변수는 두 개입니다. 첫 번째는 ArrayStack 구조체고 두 번째는 스택의 용량을 결정하는 수입니다. 함수 내부로 들어가서 보면 malloc() 함수가 두 번이나 호출 된 것을 볼 수 있습니다. 처음에 호출된 malloc()은 ArrayStack을 자유저장소에 올리기 위해 사용되었고 그 다음에는 스택 내에 있는 노드를 매개 변수로 입력된 용량만큼 자유 저장소에 생성하는 데 사용됐습니다.

한편, ArrayStack의 Capacity에는 배열의 용량을 저장하고 최상위 노드의 위치를 가리키는 Top은 0으로 초기화합니다. Top은 노드가 쌓일 때마다 1씩 증가하고 노드가 제거될 때마다 1씩 감소할 것입니다. 현재는 노드가 없기 때문에 0 입니다.

자유 저장소 메모리에 무언가를 얹어놓으면 사용이 끝난 후에는 반드시 제거해야 합니다. 다음에서 AS_DestroyStack() 함수는 스택 내의 노드와 스택을 제거하는 임무를 수행합니다.

void AS_DestroyStack(ArrayStack* Stack)
{
    /*  노드를 자유 저장소에서 해제 */
    free(Stack->Nodes);

    /*  스택을 자유 저장소에서 해제 */
    free(Stack);
}

삽입(Push) 연산

사실 삽입과 삭제 연산을 구현하는 일은 그리 복잡하지 않습니다. 특히 배열 기반의 스택에서 삽입 연산은 최상위 노드의 위치(Top)에 1을 더한 곳에 새 노드를 놓기만 하면 됩니다. 단, C 언어에서는 수가 0부터 시작하기 때문에 코드에서는 Top의 값 그대로를 새 노드의 인덱스로 사용하고 새 노드를 스택에 올린 후에 Top의 값을 1만큼 증가시켜줍니다.

삽입 연산을 담당하는 AS_Push() 함수는 다음과 같습니다.

void AS_Push(ArrayStack* Stack, ElementType Data)
{
    int Position = Stack->Top;

    Stack->Nodes[Position].Data = Data;
    Stack->Top++;
}

제거(Pop) 연산

삽입에서 최상위 노드의 인덱스(Top)의 값을 1만큼 올렸던 것과는 반대로, 제거 연산에서는 이 값을 하나 낮추면 됩니다. 한 가지 잊지 않아야 할 것은 제거 연산의 경우 최상위 노드의 데이터를 호출자에게 반환해야 한다는 것입니다.

제거 연산을 수행하는 AS_Pop() 함수는 다음과 같습니다.

ElementType AS_Pop(ArrayStack* Stack)
{
    int Position = --( Stack->Top );

    return Stack->Nodes[Position].Data;
}

위 코드에서 기억해야 할 점은 Top이 가지고 있는 값은 실제 최상위 노드가 배열 내에서 위치하는 인덱스 값보다 1만큼 더 크다는 것입니다. 따라서 "최상위 노드의 인덱스 == Top-1" 입니다.

배열로 구현하는 스택 예제 프로그램

이 예제에서는 앞에서 설명하지 않은 몇 가지 함수가 더 포함되어 있습니다. 예를 들어 제거는 하지 않고 최상위 노드의 데이터만 반환하는 Top() 함수, 스택이 비어 있는지 여부를 검사하는 IsEmpty() 함수 등입니다. 이 함수들은 구현이 간단하여 개별적으로 설명이 없지만 아래 소스 코드를 보면 충분히 이해할 수 있을 것입니다.

프로그램을 구성하는 소스 코드 파일은 총 세 개입니다. 그 중 둘은 스택 연산을 구현하는 ArrayStack.h와 ArrayStack.c, 나머지 하나는 이들을 테스트하는 Test_ArrayStack.c 입니다.

/****************/
/* ArrayStack.h */
/****************/

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H

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

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
} Node;

typedef struct tagArrayStack
{
    int   Capacity;
    int   Top;
    Node* Nodes;
} ArrayStack;

void        AS_CreateStack(ArrayStack** Stack, int Capacity);
void        AS_DestroyStack(ArrayStack* Stack);
void        AS_Push(ArrayStack* Stack, ElementType Data);
ElementType AS_Pop(ArrayStack* Stack);
ElementType AS_Top(ArrayStack* Stack);
int         AS_GetSize(ArrayStack* Stack);
int         AS_IsEmpty(ArrayStack* Stack);

#endif ARRAYSTACK_H

/****************/
/* ArrayStack.c */
/****************/

#include "ArrayStack.h"

void  AS_CreateStack(ArrayStack** Stack, int Capacity)
{
    /*  스택을 자유저장소에 생성 */
    (*Stack)           = (ArrayStack*)malloc(sizeof(ArrayStack));

    /*  입력된 Capacity만큼의 노드를 자유저장소에 생성 */
    (*Stack)->Nodes    = (Node*)malloc(sizeof(Node)*Capacity);

    /*  Capacity 및 Top 초기화 */
    (*Stack)->Capacity = Capacity;
    (*Stack)->Top = 0;
}

void AS_DestroyStack(ArrayStack* Stack)
{
    /*  노드를 자유 저장소에서 해제 */
    free(Stack->Nodes);

    /*  스택을 자유 저장소에서 해제 */
    free(Stack);
}

void AS_Push(ArrayStack* Stack, ElementType Data)
{
    int Position = Stack->Top;

    Stack->Nodes[Position].Data = Data;
    Stack->Top++;
}

ElementType AS_Pop(ArrayStack* Stack)
{
    int Position = --( Stack->Top );

    return Stack->Nodes[Position].Data;
}

ElementType AS_Top(ArrayStack* Stack)
{
    int Position = Stack->Top - 1;

    return Stack->Nodes[Position].Data;
}

int AS_GetSize(ArrayStack* Stack)
{
    return Stack->Top;
}

int AS_IsEmpty(ArrayStack* Stack)
{
    return (Stack->Top == 0);
}

/*********************/
/* Test_ArrayStack.c */
/*********************/

#include "ArrayStack.h"

int main( void )
{
    int i= 0;
    ArrayStack* Stack = NULL;

    AS_CreateStack(&Stack, 10);

    AS_Push(Stack, 3);
    AS_Push(Stack, 37);
    AS_Push(Stack, 11);
    AS_Push(Stack, 12);

    printf( "Capacity: %d, Size: %d, Top: %d\n\n", 
        Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack) );

    for ( i=0; i<4; i++ )
    {
        if ( AS_IsEmpty(Stack) )
            break;

        printf( "Popped: %d, ", AS_Pop(Stack) );

        if ( ! AS_IsEmpty(Stack) )
            printf( "Current Top: %d\n", AS_Top(Stack) );
        else
            printf( "Stack Is Empty.\n" );
    }

    AS_DestroyStack(Stack);

    return 0;
}