[자료구조] Stack(스택) 구현하기

Stack(스택)은 모든 원소들의 삽입과 삭제가 한쪽 끝에서만 수행되는 선형 자료구조를 말합니다.
삽입/삭제가 일어나는 부분을 top이라고 하며, 이 부분에서 삽입(Push)과 삭제(Pop)이 일어난다. Peek은 top의 데이터를 확인하는 연산.
후입선출(LIFO; Last In First Out), 나중에 들어온 데이터가 먼저나가는 자료구조입니다.

아래 그림고 같이 'Top'에서 Push와 Pop 연산이 일어나며, 각 노드는 이전의 노드를 가르키고 있게 구현하면 됩니다.

스택을 배열로 구연할 경우는 간단합니다.
배열을 하나 생성 후, top이라는 변수를 통해 삽입/삭제 시 top을 통해 데이터에 접근하면 됩니다.

동적 할당으로 구현하기, 결국엔 연결리스트를 잘 활용하면 스택/큐의 구현은 쉽습니다 -> 연결리스트 구현하기

먼저, 각 데이터가 될 Node와 Stack을 만듭니다.
각 노드는 이전 노드를 가르키게 prev값을 갖고, Stack은 상단을 가르킬 수 있게 top값을 갖고 있습니다.

typedef struct Node
{
    int data;
    Node* prev;
}Node;
 
typedef struct Stack
{
    Node* top;
}Stack;
 

다음, Stack을 초기화 해줄 InitStack()함수를 생성합니다.
간단히 malloc으로 메모리를 할당해 준 후, top의값을 NULL로 초기화해줍니다.

void InitStack(Stack** s)
{
    (*s) = (Stack*)malloc(sizeof(Stack));
    (*s)->top = NULL;
}Colored by Color Scripter

데이터를 추가해주는 Push()함수
Push할 경우 새로 추가된 노드의 prev는 top을 가르키게 한 후, top은 새로추가된 노드를 가르키게 합니다.

Node* CreateNode(int data)
{
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data;
    n->prev = NULL;
    return n;
}
 
void PushNode(Stack** stack, Node * node)
{
    if ((!stack)) return;
 
    node->prev = (*stack)->top;
    (*stack)->top = node;
}
//호출은 PushNode(&myStack, CreateNode(5));

Pop/Peek 함수,
데이터가 없을 경우 NULL을 리턴해주고, 데이터가 있다면 stack의 top의 값을 리턴해줍니다.
Pop의 경우엔 top->prev값을 top으로 바꿔주고, Peek()은 아무런 변경 없이 리턴해줍니다.

Node* PopNode(Stack** stack)
{
    if (!(*stack) || !((*stack)->top)) return NULL;
 
    Node * n = (*stack)->top;
    (*stack)->top = n->prev;
    return n;
}
 
Node* PeekNode(Stack** stack)
{
    if (!(*stack) || !((*stack)->top)) 
        return NULL;
 
    return ((*stack)->top);
}

Stack의 메모리 해제를 해주는 Destroy()함수, Stack의 남아있는 Node들을 전부 Pop해주어 free(),해주면 됩니다.

void DestroyStack(Stack** stack)
{
    if (!(*stack))return;
    Node * n = PopNode(&(*stack));
    while (n != NULL)
    {
        cout << "Destroy Node:" << n->data << endl;
        free(n);
        n = PopNode(&(*stack));
    }
 
    (*stack) = NULL;
    free((*stack));
}

아래같이 테스트해보면 됩니다.

int main()
{
    Stack * stack = NULL;
    InitStack(&stack);
    PushNode(&stack, CreateNode(1));
    PushNode(&stack, CreateNode(2));
    PushNode(&stack, CreateNode(3));
    PushNode(&stack, CreateNode(4));
    PushNode(&stack, CreateNode(5));
    PushNode(&stack, CreateNode(6));
    PushNode(&stack, CreateNode(100));
    PushNode(&stack, CreateNode(101));
    PushNode(&stack, CreateNode(102));
    PushNode(&stack, CreateNode(103));
 
    for (int i = 0; i < 5; i++)
    {
        Node * n = PopNode(&stack);
        cout << n->data << endl;
        free(n);
    }
    DestroyStack(&stack);
    return 0;
}