스택

스택Stack은 쉽게 말하면, '쌓여있는 책더미'다. 각각의 책은 아주 무거워서 맨 위에 올리거나 맨 위의 책 한 권을 빼는 것밖에 하지 못한다. 우리는 현실에서 쌓여있는 책 중 원하는 책을 꺼낼 때, 그 책이 책더미 중간에 있으면 위의 책들을 한 손으로 받치고 다른 한 손으로 원하는 책을 꺼낸다. 하지만 스택 구조에서는 각각의 책이 너무 무거워서 우리가 다룰 수 있는 것은 쌓여있는 책들 중 맨 위의 책뿐이다.

이런 자료구조를 LIFO(Last In-First Out) 혹은 FILO(First In-Last Out)라고 부른다. 구조가 단순한 탓에 구현하기 쉽다. 자료구조 맨 위에 데이터를 저장하고, 맨 위의 데이터만 다루면(꺼내기) 되므로 저장하는 속도와 읽는 속도가 빠르다. 다만 데이터의 capacity(저장될 수 있는 최대 갯수)를 미리 정해야 하다 보니 저장 공간을 효율적으로 사용하기 어렵다는 단점이 있다.

스택이 쓰이는 곳은 너무 많다. 우리는 사실 알게 모르게 스택을 사용해왔다. 함수의 호출 방식(Call Stack), 컴파일러의 에러 출력 방식, 편집 프로그램에 있는 되돌리기 기능 등이 그 예시다.

ADT도 간단하다. 우리가 배열의 메서드에서 볼 수 있는 push와 pop만 구현하면 된다(물론 스택 자체의 생성/소멸 연산은 기본이다). 링크드 리스트에 비하면 아주 마음이 가볍다 :)

배열 기반 스택

모두에게 익숙한 배열Array을 가지고 스택을 만들어보자. 배열을 활용해야 하다보니 미리 용량capacity을 정해야 한다.

(ArrayStack.c)

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

typedef int Element;

typedef struct _ASNode
{
    Element Data;
} ASNode;

typedef struct _ArrayStack
{
    int Capacity;
    int Top;
    ASNode* Nodes;
} ArrayStack;

void CreateAS( ArrayStack** Stack, int capacity )
{
    (*Stack) = (ArrayStack*)malloc( sizeof( ArrayStack ) );

    (*Stack)->Nodes = (ASNode*)malloc( sizeof( ASNode ) * capacity );

    (*Stack)->Capacity = capacity;
    (*Stack)->Top = -1;
}

void ASPush( ArrayStack* Stack, Element data )
{
    Stack->Top++;
    Stack->Nodes[Stack->Top].Data = data;
}
Element ASPop( ArrayStack* Stack )
{
    int idx = Stack->Top--;
    return Stack->Nodes[idx].Data;
}

void DestroyAS( ArrayStack* Stack )
{
    free( Stack->Nodes );
    free( Stack );
}

링크드 리스트 기반 스택

스택은 capacity를 미리 지정해주어야 한다는 것이 단점이었다. 이를 보완하고자 링크드 리스트Linked List를 활용한다. 대신 trade-off로 구현은 좀 더 까다롭다.

(LinkedListStack.c)

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

typedef struct _LLSNode
{
    char* Data;
    struct _LLSNode* NextLLSNode;
} LLSNode;

typedef struct _LLStack
{
    LLSNode* List;
    LLSNode* Top;
} LLStack;

void CreateLLS( LLStack** Stack )
{
    (*Stack) = (LLStack*)malloc( sizeof( LLStack ) );

    (*Stack)->List = NULL;
    (*Stack)->Top = NULL;
}
LLSNode* CreateLLSNode( char* data )
{
    LLSNode* New = (LLSNode*)malloc( sizeof( LLSNode ) );
    
    New->Data = (char*)malloc( sizeof( data ) + 1 );
    strcpy( New->Data, data );

    New->NextLLSNode = NULL;

    return New;
}

void LLSPush( LLStack* Stack, LLSNode* New )
{
    if ( Stack->List == NULL )
        Stack->List = New;
    else
        Stack->Top->NextLLSNode = New;

    Stack->Top = New;
}
LLSNode* LLSPop( LLStack* Stack )
{
    LLSNode* TopLLSNode = Stack->Top;

    if ( Stack->List == Stack->Top )
    {
        Stack->List = NULL;
        Stack->Top = NULL;
    }
    else
    {
        LLSNode* Candidate = Stack->List;
        while ( Candidate != NULL && Candidate->NextLLSNode != Stack->Top )
            Candidate = Candidate->NextLLSNode;

        Stack->Top = Candidate;
        Stack->Top->NextLLSNode = NULL;
    }

    return TopLLSNode;
}

int LLSIsEmpty( LLStack* Stack )
{
    return (Stack->List == NULL);
}

void DestroyLLSNode( LLSNode* Target )
{
    free( Target->Data );
    free( Target );
}
void DestroyLLS( LLStack* Stack )
{
    while ( LLSIsEmpty( Stack ) )
    {
        LLSNode* Popped = LLSPop( Stack );
        DestroyLLSNode( Popped );
    }

    free( Stack );
}

위의 코드는 pop 연산을 하는 경우, 스택의 최상단 바로 전 요소까지 접근하느라 while문이 너무 오래 돈다. 따라서 이를 이중 연결 리스트Double Linked List로 구현하여 해결할 수도 있다.

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

typedef struct _LLSNode
{
    char Data;
    struct _LLSNode* NextLLSNode;
    struct _LLSNode* PrevLLSNode;
} LLSNode;

typedef struct _LLStack
{
    LLSNode* List;
    LLSNode* Top;
} LLStack;

void CreateLLS( LLStack** Stack )
{
    (*Stack) = (LLStack*)malloc( sizeof( LLStack ) );

    (*Stack)->List = NULL;
    (*Stack)->Top = NULL;
}
LLSNode* CreateLLSNode( char data )
{
    LLSNode* New = (LLSNode*)malloc( sizeof( LLSNode ) );
    
    New->Data = data;
    New->NextLLSNode = NULL;
    New->PrevLLSNode = NULL;

    return New;
}

void LLSPush( LLStack* Stack, LLSNode* New )
{
    if ( Stack->List == NULL )
        Stack->List = New;
    else
    {
        New->PrevLLSNode = Stack->Top;
        Stack->Top->NextLLSNode = New;
    }

    Stack->Top = New;
}
LLSNode* LLSPop( LLStack* Stack )
{
    LLSNode* TopLLSNode = Stack->Top;

    if ( Stack->List == Stack->Top )
    {
        Stack->List = NULL;
        Stack->Top = NULL;
    }
    else
    {
        LLSNode* Candidate = Stack->Top->PrevLLSNode;

        Stack->Top = Candidate;
        if ( Stack->Top != NULL )
            Stack->Top->NextLLSNode = NULL;
    }

    return TopLLSNode;
}

int LLSIsEmpty( LLStack* Stack )
{
    return (Stack->List == NULL);
}

void DestroyLLSNode( LLSNode* Target )
{
    free( Target );
}
void DestroyLLS( LLStack* Stack )
{
    while ( LLSIsEmpty( Stack ) )
    {
        LLSNode* Popped = LLSPop( Stack );
        DestroyLLSNode( Popped );
    }

    free( Stack );
}

참고 서적:
박상현, 2022, 한빛미디어, 『이것이 자료구조+알고리즘이다』

참고 사이트:
나무위키: 스택(자료구조)
잔재미코딩 - 대표적인 자료구조: 스택